使用布隆过滤器判断元素是否存在,

　　00-1010 1.什么是布鲁姆过滤器2、实现原理3、功能4、具体实现5、代码实现6、实战7。总结如何快速判断一个元素是否在集合中？这个话题是我最近采访中经常被问到的问题。不同的人对这个问题有许多不同的答案。

　　今天要介绍一个很少有人会提到的方案，就是借助Bloom filter。

　　00-1010布鲁姆滤镜是一个叫布鲁姆的大哥在1970年提出的。

　　实际上可以看作是由二进制向量(或位数组)和一系列随机映射函数(哈希函数)组成的数据结构。

　　它的优点是空间效率和查询时间比一般算法好很多，缺点是有一定的误识率和删除难度。

　　00-1010先来张图。

　　Bloom filter算法的主要思想是用n个哈希函数进行哈希，然后得到不同的哈希值，根据哈希映射到一个数组的不同索引位置(这个数组的长度可能很长)，然后将对应索引位置的值设置为1。

　　判断元素是否出现在集合中，就是用k个不同的哈希函数计算哈希值，看哈希值对应的索引位置上面的值是否为1。如果one不为1，则表示该元素不存在于集合中。

　　但是，也可以判断该元素在集合中，但不在集合中。这个元素的1 above all index positions是由其他元素设置的，导致了一定的误判概率(这是上面是住在一个集合里的可能性的根本原因，因为会有一定的哈希冲突)。

　　注意：误判率越低，对应的性能越低。

　　00-1010 Bloom filter可以用来判断一个元素是否(可能)在一个集合中，与其他数据结构相比，Bloom filter在空间和时间上都有很大的优势。

　　注意上面那个字：可能。这里先保留一个悬念，下面详细分析。

　　判断给定数据是否存在

　　防止缓存穿透(判断请求的数据是否有效以避免直接绕过缓存请求数据库)等。邮箱的垃圾邮件过滤、黑名单功能等。

　　00-1010看完Bloom filter的算法思路，然后开始讲解具体实现。

　　我给你举个例子。让我们假设有两根弦，王采和萧蔷。它们分别经过了三次哈希算法，然后根据哈希结果将对应数组的索引位置的值(假设数组长度为16)设置为1。让我们先来看看王采360这个短语。

　　经过三次哈希运算后，王采的值分别是2、4和6。根据可用的索引值，它们分别是2、4和6。因此，该数组的索引(2、4和6)的值被设置为1，其余的被视为0。现在，人们认为有必要找到王采。经过同样的三次哈希，发现索引2、4、6对应位置的值都是1，可以判断王采是可能的。

　　然后，萧蔷被插入布隆过滤器。实际过程同上，假设得到的下标是1，3，5。

　　抛开王采的存在，此时的萧蔷在布鲁姆过滤器中是这样的，实际组合王采和萧蔷的数组是这样的：

　　现在有一个数据：9527。现在的要求是判断9527是否存在。假设9527经过三次哈希后的下标分别是：5，6，7。结果下标为7的位置的值为0，可以明确判断9527不存在。

　　然后来了一部国产007。在三次散列之后，下标分别是2、3和5。发现下标2、3、5对应的值都是1，可以大致判断国产007可能存在。但实际上，经过我们刚才的演示，国产007根本不存在。索引位置2、3和5的值为1的原因是因为其他数据设置。

　　说到这里，不知道大家有没有了解过Bloom filter的作用。

　　00-1010作为java程序员，我们真的很幸福。我们用很多框架和工具，基本都是打包的。Bloom filter，我们使用google打包的工具类。当然，还有其他方法，你可以探索。

　　首先添加依赖项。

　　!-Bloom Filter Dependency-Dependency groupIdcom.google.guava/groupId artifactid guava/artifactid Version 25.1-JRE/Version/Dependency代码实现

　　导入com。

　　google.common.hash.BloomFilter;import com.google.common.hash.Funnels;import java.nio.charset.Charset;public class BloomFilterDemo { public static void main(String[] args) { /** * 创建一个插入对象为一亿，误报率为0.01%的布隆过滤器 * 不存在一定不存在 * 存在不一定存在 * ---------------- * Funnel 对象：预估的元素个数，误判率 * mightContain ：方法判断元素是否存在 */ BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 100000000, 0.0001); bloomFilter.put("死"); bloomFilter.put("磕"); bloomFilter.put("Redis"); System.out.println(bloomFilter.mightContain("Redis")); System.out.println(bloomFilter.mightContain("Java")); }}具体的解释已经写在注释中了。到这里相信大家一定明白了布隆过滤器和其怎么使用了。

6、实战

我们来模拟这样的场景：通过布隆过滤器来解决缓存穿透。

　　首先你的知道什么叫缓存穿透吧？

　　缓存穿透是指用户访问一个缓存和数据库中都没有的数据，因为缓存中不存在，所以就会去访问数据库，如果并发很高。很容易会击垮数据库

　　那布隆过滤器是如何解决这个问题的呢？他

　　的原理是这样子的：将数据库中所有的查询条件，放入布隆过滤器中，当一个查询请求过来时，先经过布隆过滤器进行查，如果判断请求查询值存在，则继续查；如果判断请求查询不存在，直接丢弃。

　　其代码如下：

String get(String key) { String value = redis.get(key); if (value == null) { if(!bloomfilter.mightContain(key)){ return null; }else{ value = db.get(key); redis.set(key, value); } } return value；}

7、小结

本文详细介绍了布隆过滤器是什么？有什么作用？实现原理以及从代码层面多方面来阐述布隆过滤器。希望能为各位在学习进阶的路上添砖加瓦。

　　以上就是布隆过滤器面试如何快速判断元素是否在集合里的详细内容，更多关于布隆过滤器面试判断元素是否在集合里的资料请关注盛行IT其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。