本文主要介绍 布隆过滤器 的使用
大数据领域一个经常用到的算法——布隆过滤器。如果看过《数学之美》的同学对它应该并不陌生，它经常用在集合的判断上，在海量数据的场景当中用来快速地判断某个元素在不在一个庞大的集合当中。
# 原理
在我之前的理解当中，如果想要判断某个元素在不在集合当中，经典的结构应该是平衡树和 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 组合之前没有出现过，但是对应的位置都在其他元素中出现过了，这样就出现误差了。所以我们可以知道，布隆过滤器对于不存在的判断是准确的，但是对于存在的判断是有可能有错误的。
# 代码
布隆过滤器的原理很简单，明白了之后，我们很容易写出代码：
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，也就是判断错误的情况。那么，这种错误判断发生的概率有多大呢？
这个概率的计算也不难：由于数组长度是 m，所以插入一个 bit 它被置为 1 的概率是 1m，插入一个元素需要插入 k 个 hash 值，所以插入一个元素，某一位没有被置为 1 的概率是 (1−1m)k。插入 n 个元素之后，某一位依旧为 0 的概率是 (1−1m)nk，它变成 1 的概率是 1−(1−1m)nk。
如果在某次判断当中，有一个没有出现过的元素被认为已经在集合当中了，那么也就是说它 hash 得到的位置均已经在之前被置为 1 了，这个时间发生的概率为：
这里用到了一个极限：
我们来求一下冲突率最低时 k 的取值，为了方便计算，我们令 b=enm，代入：
f(k)=(1−b−k)klnf(k)=kln(1−b−k)
两边求导：
1f(k)f′(k)=ln(1−b−k)+kb−klnb1−b−k
我们令导数等于 0，来求它的极值：
ln(1−b−k)(1−b−k)=−kb−klnbln(1−b−k)(1−b−k)=b−klnb−k1−b−k=b−kb−k=12
我们将 b−k=12 代入，可以求出最值时的 k=ln2⋅mn≈0.7mn
同理，我们也可以预设定集合元素 n 和错判率 p，来求解对应的 n，同样利用上面的公式推算，可以得到 m=−nlnp(ln2)2
如果我们允许一定的容错，并且能够大概估计会出现的元素的个数，那么完全可以使用布隆过滤器来代替传统的容器判重的方法。这样不仅效率极高，而且对于存储的要求非常小。
# 灵魂拷问
原理也明白了，代码也看懂了，这个时候我们来思考一个问题：布隆过滤器可以删除元素吗？
很遗憾，布隆过滤器是不支持删除的。
因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。
还是用上面的例子举例：我们删除线性代数，线性代数对应的位置是 1，3，5，虽然我们并没有删除高等数学，但是由于我们移除了高等数学也用到的位置 1，如果我们再去判断高等数学是否存在就会得到错误的结果，虽然我们并没有删除它。
当然，在一些必须要有删除功能的场景下，也是有办法的。方法也很简单，就是修改数据结构，将原本每一位一个 bit 改成一个 int，当我们插入元素的时候，不再是将 bit 设置为 true，而是让对应的位置自增，而删除的时候则是对应的位减一。这样，我们删除单个结果就不会影响其他元素了。
这种方法并不是完美的，由于布隆过滤器存在误判的情况，很有可能我们会删除原本就不存在的值，这同样会对其他元素产生影响。
布隆过滤器是一个优缺点都非常明显的数据结构，优点非常出色：速度足够快，内存消耗小，代码实现简单。但是缺点也很明显：不支持删除元素，会有误判的情况。这样特点鲜明的数据结构真的非常吸引人。
# 优化
针对布隆过滤器的优缺点，目前以及出现布谷鸟过滤来替代布隆过滤器，但它也有很明显但优缺点，下次再说