布隆过滤器

应用场景

大数据 ， 快速查找 ， 不介意小概率误判

分布式磁盘 IO
爬虫
黑名单过滤

优缺点

优点

空间小，相比list, RB-tree, hash 不用存数据
查询快， $O(k)$ 级别的查询效率，还能并行

缺点

有时候同学不在寝室，他却告诉我们在；但是他们告诉我们不在，就一定不在
删除难

原理

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

一般了解到这里就可以。如果你还想看，下面就是无聊的公式推导了。参考 wiki 吧

搞事情

搞哈希算法

哈希算法 = 数组 + 哈希函数

碰撞了怎么办？

两种办法：开链法和闭散列法。开链法就是将映射到同一下标的所有元素形成一个链表，挂到该位置下面；闭散列法就是将冲突的元素按照某种方式向后排放。

缺点

开链法：极端条件下又变成 $O(n)$ 了
闭散列法：多吃多占，影响了下个本来映射到该位置的元素

负载因子

就是当前哈希表中存放的元素数和数组长度的比值。一般来说，负载因子超过 0.8，就需要对哈希表扩容。即重新构造一个更大的数组，将所有元素转移过去，再释放原有空间。

误判概率

$P \approx\left(1-e^{-\frac{n k}{m}}\right)^{k}$

看看影响因素

集合中元素数量 $n$
数组大小 $m$
选取的 $k$ 个哈希函数

从这个公式也可以看出， $m$ 和 $n$ 成比例才可以保证误报率不变。 $k$ 不用管他。

参考：

https://www.wikiwand.com/en/Bloom_filter
https://smartbrave.github.io/posts/3e0efa6d