从位图到布隆过滤器

位图



位图法就是bitmap的缩写，所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断大数据量级下某个数据存不存在的。



给定一个场景：有40亿个用户，判断某个用户是否存在这40亿当中。假设我们查询的数据对象的ID本身是正整数，我们可以申请一个空间大于40亿的数组int[40亿]，并将数组中每个元素初始化为0。对于存在的用户，将用户ID对应作为数组index，将此index下的值设为1即可。



上面看起来没什么问题。实际上40亿int数组占用空间还是很大的， 40亿大小的int32数组占用空间大约有15GB，一般的小型机很难一次性存放。即使是使用1字节的char类型数组，占用空间也有3.8G。



我们关心一个用户存不存在（1和0）的状态，实际上只用1bit就够了。如果我们能以bit为单位来构建这个数组，那使用空间就是 int 32 数组的 1/32，可以大幅减少存储使用的内存空间。



有些编程语言没有bitmap数据类型，但是并不影响我们进行位运算。实际上，使用int32类型的数组，512M的内存就够了，因为512M = 512*1024*1024*8 bit > 40亿 bit。剩下的就是位运算的事情了。



位图的其他使用场景可以参考位图法



我们已经将每个元素大小压缩到了最小单位 1 个 bit了，那还有没有继续优化的空间呢？可以想到只能从缩小数组大小入手了。接下来就需要借助布隆过滤器来实现。

布隆过滤器

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。



布隆过滤器的原理是，当一个元素被加入集合时，通过K个Hash函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。



布隆过滤器最大的特点，就是对一个对象使用多个哈希函数。如果我们使用了 k 个哈希函数，就会得到 k 个哈希值，也就是 k 个下标，我们会把数组中对应下标位置的值都置为 1。布隆过滤器和位图最大的区别就在于，我们不再使用一位来表示一个对象，而是使用 k 位来表示一个对象。这样两个对象的 k 位都相同的概率就会大大降低，不仅能够解决单哈希容易造成冲突的问题，还能有效减少内存空间的使用。



前面介绍提到，布隆过滤器的查询有一个特点---误识别率。就是即使任何两个元素的哈希值不冲突，而且我们查询对象的 k 个位置的值都是 1，查询结果为存在，这个结果也可能是错误的。下图举一个例子。我们可以看到，布隆过滤器中存储了 x 和 y 两个对象，它们对应的 bit 位被置为 1。当我们查询一个不存在的对象 z 时，如果 z 的 k 个哈希值的对应位置的值正好都是 1，z 就会被错误地认定为存在。而且，这个时候，z 和 x，以及 z 和 y，两两之间也并没有发生哈希冲突。





即使存在误判的可能，但是并不影响布隆过滤器的广泛使用。比如场景：我们希望用更小的代价快速判断 ID 是否已经被注册了。在这个使用场景中，只要有一位的值为0，可以肯定用户是不存在的；对于哈希值对应的bit全部是1的情况，就算我们无法肯定确认 ID 是否已经被注册了，让用户再换一个 ID 注册，这也不会损害新用户的体验。在系统不要求结果 100% 准确的情况下，我们可以直接当作这个用户 ID 已经被注册了就可以了。这样，我们使用布隆过滤器就可以快速完成“是否存在”的检索。



除此之外，对于布隆过滤器而言，如果哈希函数的个数不合理，比如哈希函数特别多，布隆过滤器的错误率可能就会变大。因此，除了使用多个哈希函数避免哈希冲突以外，我们还要控制布隆过滤器中哈希函数的个数。有这样一个计算最优哈希函数个数的数学公式:



# 哈希函数个数 
k = (m/n) * ln(2)



其中 m 为 bit 数组长度，n 为要存入的对象的个数。 实际上，如果哈希函数个数为 1，且数组长度足够，布隆过滤器就可以退化成一个位图。所以，我们可以认为“位图是只有一个特殊的哈希函数，且没有被压缩长度的布隆过滤器”。