面试题，如何在千万级的数据中判断一个值是否存在？

当你看到这个标题的时候，你也许会想我可以使用hashmap之类的来存储值，然后get就是了。又或者把数据存在数据库里然后去判断就可以了。

但你有没有想过数据量那么大全部存储起来是不是有点太重了。为了判断是否存在得把所有的数据都存储起来，这个数据量得有多大。

所以我们先把map这种数据结构先排除掉，去看看本期的主角：Bloom Filter。

Bloom Filter初识

在东方大地，它的名字叫：布隆过滤器。该过滤器在一些分布式数据库中被广泛使用，比如我们熟悉的hbase等。它在这些数据库中扮演的角色就是判断一个值是否存在。这些分布式数据库之所以青睐它，就是因为它有很强大的性能，而且存储空间又小。

布隆过滤器核心就是两点，bit数组和hash。

你听到这里是不是表示不屑，废话，map还不是一个数组和hash。没错，存放数据无非就是个数组和hash。但布隆过滤器的数组和hash有点不一样。

它的数组里的值只有两种可能，要么是1，要么是0，没有其他第三个值。1表示存在，0表示不存在。

它的hash有多个hash。注意，可以是多个hash，不是一个hash。

那布隆过滤器数据结构究竟是怎么存储的呢？我们简单的画个图你就明白了。

没错，就是一个数组，然后里边的值都是一些0和1。数组的初始状态是全部为0。然后每插入一个值，就会把该值的几个hash后的映射值改为1。如上图所示。

那如何去添加一个值进去呢？然后又如何判断该值是否存在呢？现在需要确定位置，这个道理和hashmap的道理是一样的，使用hash来确定位置。

比如我要判断x是否存在，那么我就通过生成的三个hash函数来分别hash到数组的三个位置去，然后获取这个三个位置的值是否都为1，如果是，就认为x是存在（极有可能）的。反之，如果有一个位置的值为0，那么x必然不存在。

那么你现在肯定纳闷，这个hash函数是固定几个hash函数吗？还是怎么样？

hash生成的规则

嗯，这是布隆过滤器核心思想之一，通过查找布隆过滤器的论文可知，它有一个公式，通过这个公式来计算hash。

gi(x) = h1(x) + i*h2(x);

首先是要有两个初始hash，分别为h1和h2，然后通过h1和h2生成新的hash。i表示hash函数个数。

在google guava库里的BloomFilter中就是按照这个公式来生成hash的。

另外可以看到hash1和hash2的生成规则，hash1是通过murmur算法来生成一个long值，然后通过转int来得到hash1，然后通过位运算得到hash2。

合适的数组大小和hash数量

此时你也许会纳闷一个事情，你不是说千万级数据量，那么hash后取模落到数组中，如果数组比较小，是不是就会重叠，那么此时即使每个hash函数查出来都为1也不一定就表示某值存在啊？

没错，确实有这个问题。为了解决这个问题，布隆过滤器引入了误报率这个概念，说的就是这个问题。

所以数组的大小至关重要。另外hash functions的个数也至关重要。既然这么重要，怎么才能计算出合适的数量呢？有下面两个公式，分别用来计算推荐的数组size以及hash functions的个数。这里数组的大小用m表示，hash functions的个数用k来表示。n则表示数据量的大小。

选择合适的hash算法

另外选择一个好的hash算法也是至关重要的，好的hash算法可以确保hash值比较均匀的分布。guava里的Bloom Filter使用的就是Murmur哈希算法。

MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。由Austin Appleby在2008年发明，并出现了多个变种，都已经发布到了公有领域(public domain)。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。

总之，Bloom Filter就三点：数组、hash生成规则、hash算法（Murmour）。

上代码

通过上面的介绍，相信你应该知道了布隆过滤器的基本原理，现在我们就以guava的Bloom Filter为例，体验一下，千万级的感觉吧：

返回结果：

上面的代码中我们设置了误报率以及预估数据量，然后生成了Bloom Filter实例，然后插入一个“importsource”字符串，然后判断是否存在，最后返回结果是存在。

使用场景

主要使用场景：

1、黑名单。如果某个IP或账号不存在，则允许通过；否则不让通过。

2、爬虫重复URL检测。爬取数据时，需要检测某个url是否已被爬取过。

3、字典纠错。检测单词是否拼写正确。

4、磁盘文件检测。检测要访问的数据是否在磁盘或数据库中。

5、CDN缓存。先查找本地有无cache，如果没有则到其他兄弟cache服务器上去查找。为了避免无谓的查询，在每个cache服务器上保存其兄弟服务器的缓存关键字，以bloomfilter方式存储。在去指定兄弟服务器查找之前，先检查boomfilter中是否有url，如果有，再去对应服务器查找。

总结

Bloom Filter核心就是数组和hash。数组中1表示存在，0表示不存在。Bloom Filter有一定的误报率。多个hash映射都为1，表示指定值极有可能存在（也有可能不存在），多个hash映射有一个为0，则该值必定不存在。选择合适的hash function数量以及数组大小以及合适的hash算法对于准确率至关重要。

误报率在线计算：https://hur.st/bloomfilter/

论文：http://www.eecs.harvard.edu/~michaelm/postscripts/tr-02-05.pdf

在线体验示例：https://llimllib.github.io/bloomfilter-tutorial/