关于布隆过滤器:你永远可以相信布隆

明天的文章和大家一起来学习大数据畛域一个常常用到的算法——布隆过滤器。如果看过《数学之美》的同学对它应该并不生疏，它常常用在汇合的判断上，在海量数据的场景当中用来疾速地判断某个元素在不在一个宏大的汇合当中。它的原理不难，然而设计十分奇妙，。

欢送各位进群 973961276 一起聊聊技术吹吹牛，每周都会有几次抽奖送专业书籍的流动，奖品虽不甚值钱，但也算个彩头不是

原理

在我之前的了解当中，如果想要判断某个元素在不在汇合当中，经典的构造应该是均衡树和 hash table。然而无论是哪一种办法，都逃不开一点，都须要存储原值。

比方在爬虫场景当中，咱们须要记录下之前爬过的网站。咱们要将之前的网址全副都存储在容器里，而后在遇到新网站的时候去判断是否曾经爬过了。在这个问题当中，咱们并不关怀之前爬过的网站有哪些，咱们只关怀当初的网站有没有在之前呈现过。也就是说之前呈现过什么不重要，当初的有没有呈现过才重要。

咱们利用均衡树或者是 Trie 或者是 AC 自动机等数据结构和算法能够实现高效的查找，然而都离不开存储下所有的字符串。设想一下，一个网址大略上百个字符，大概 0.1KB，如果是一亿个网址，就须要 10GB 了，如果是一百亿一千亿呢？显然这么大的规模就很麻烦了，明天要介绍的布隆过滤器就能够解决这个问题，而且不须要存储下原值，这是一个十分奇妙的做法，让咱们一起来看下它的原理。

布隆过滤器自身的构造非常简单，就是一个一维的 bool 型的数组，也就是说每一位只有 0 或者 1，是一个 bit，这个数组的长度是 m。对于每个新增的项，咱们应用 K 种不同的 hash 算法对它计算 hash 值。所以咱们能够失去 K 个 hash 值，咱们用 hash 值对 m 取模，假如是 x。刚开始的时候数组内全部都是 0，咱们把所有 x 对应的地位标记为 1。

举个例子，假如咱们一开始 m 是 10，K 是 3。咱们遇到第一个插入的值是”线性代数“，咱们对它 hash 之后失去 1，3，5，那么咱们将对应的地位标记成 1.

而后咱们又遇到了一个值是”高等数学“，hash 之后失去 1，8，9，咱们还是将对应地位赋值成 1，会发现 1 这个地位对应的值曾经是 1 了，咱们疏忽就好。

如果这个时候咱们想要判断”概率统计”有没有呈现过，怎么办？很简略，咱们对“概率统计”再计算 hash 值。假如失去 1，4，5，咱们去遍历一下对应的地位，发现 4 这个地位是 0，阐明之前没有增加过“概率统计”，显然“概率统计”没有呈现过。

然而如果“概率统计”hash 之后的后果是 1，3，8 呢？咱们判断它呈现过就错了，答案很简略，因为尽管 1，3，8 这个 hash 组合之前没有呈现过，然而对应的地位都在其余元素中呈现过了，这样就呈现误差了。所以咱们能够晓得，布隆过滤器对于不存在的判断是精确的，然而对于存在的判断是有可能有谬误的。

零根底和大三大四的敌人看这里 >>c/c++ 企业级我的项目实战
曾经工作了想持续自我晋升跳槽涨薪的工程师看这里 >>c/c++ linux 服务器高级架构师学习

代码

布隆过滤器的原理很简略，明确了之后，咱们很容易写出代码：

# 插入元素
def BloomFilter(filter, value, hash_functions):
    m = len(filter)
    for func in hash_functions:
        idx = func(value) % m
        filter[idx] = True
    return filter
    
# 判断元素
def MemberInFilter(filter, value, hash_functions):
    m = len(filter)
    for func in hash_functions:
        idx = func(value) % m
        if not filter[idx]:
            return False
    return True 

错误率计算

之前的例子当中应该展现得很明确了，布隆过滤器尽管好用，然而会存在 bad case，也就是判断谬误的状况。那么，这种错误判断产生的概率有多大呢？

这个概率的计算也不难：因为数组长度是 mm，所以插入一个 bit 它被置为 1 的概率是 1m1m，插入一个元素须要插入 k 个 hash 值，所以插入一个元素，某一位没有被置为 1 的概率是(1−1m)k(1−1m)k。插入 n 个元素之后，某一位仍旧为 0 的概率是(1−1m)nk(1−1m)nk，它变成 1 的概率是 1−(1−1m)nk1−(1−1m)nk。

如果在某次判断当中，有一个没有呈现过的元素被认为曾经在汇合当中了，那么也就是说它 hash 失去的地位均曾经在之前被置为 1 了，这个工夫产生的概率为：

[1−(1−1m)nk]k≈(1−e−knm)k[1−(1−1m)nk]k≈(1−e−knm)k

这里用到了一个极限：

limx→−∞(1−1x)−x=elimx→−∞(1−1x)−x=e

咱们来求一下抵触率最低时 k 的取值，为了不便计算，咱们令 b =enmb=enm，代入：

f(k)=(1−b−k)klnf(k)=kln(1−b−k)f(k)=(1−b−k)kln⁡f(k)=kln⁡(1−b−k)

两边求导：

1f(k)f′(k)=ln(1−b−k)+kb−klnb1−b−k1f(k)f′(k)=ln(1−b−k)+kb−kln⁡b1−b−k

咱们令导数等于 0，来求它的极值：

ln(1−b−k)(1−b−k)ln(1−b−k)(1−b−k)1−b−kb−k=−kb−klnb=b−klnb−k=b−k=12ln⁡(1−b−k)(1−b−k)=−kb−kln⁡bln⁡(1−b−k)(1−b−k)=b−kln⁡b−k1−b−k=b−kb−k=12

咱们将 b−k=12b−k=12 代入，能够求出最值时的 k =ln2⋅mn≈0.7mnk=ln⁡2⋅mn≈0.7mn

同理，咱们也能够预设定汇合元素 n 和错判率 p，来求解对应的 n，同样利用下面的公式推算，能够失去 m =−nlnp(ln2)2m=−nln⁡p(ln⁡2)2

如果咱们容许肯定的容错，并且可能大略预计会呈现的元素的个数，那么齐全能够应用布隆过滤器来代替传统的容器判重的办法。这样不仅效率极高，而且对于存储的要求十分小。

灵魂拷问

原理也明确了，代码也看懂了，这个时候咱们来思考一个问题：布隆过滤器能够删除元素吗？

很遗憾，布隆过滤器是不反对删除的。

因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果咱们间接删除这一位的话，会影响其余的元素。

还是用下面的例子举例：咱们删除线性代数，线性代数对应的地位是 1，3，5，尽管咱们并没有删除高等数学，然而因为咱们移除了高等数学也用到的地位 1，如果咱们再去判断高等数学是否存在就会失去谬误的后果，尽管咱们并没有删除它。

当然，在一些必须要有删除性能的场景下，也是有方法的。办法也很简略，就是批改数据结构，将本来每一位一个 bit 改成一个 int，当咱们插入元素的时候，不再是将 bit 设置为 true，而是让对应的地位自增，而删除的时候则是对应的位减一。这样，咱们删除单个后果就不会影响其余元素了。

这种办法并不是完满的，因为布隆过滤器存在误判的状况，很有可能咱们会删除本来就不存在的值，这同样会对其余元素产生影响。

布隆过滤器是一个优缺点都非常明显的数据结构，长处十分杰出：速度足够快，内存耗费小，代码实现简略。然而毛病也很显著：不反对删除元素，会有误判的状况。这样特点显明的数据结构真的十分吸引人。

明天的文章就是这些，如果感觉有所播种，请棘手点个关注吧，你们的举手之劳对我来说很重要。