妙计：布隆过滤器

在谈布隆过滤器算法的之前，我们先说一说查找，比如在1亿数据中 查找数字X是否存在。 常见的方法是： 1，遍历查找，随着数据量的增长，查询的时间复杂度O(n)也是线性增长的。 2，对数据排序之后，进行二分查找，查找的时间复杂度 O(logn) 3，使用哈希表k-v结构存储，这样通过判断X是否在K的集合，时间复杂度是O(1)。 这些方法都不可避免的需要存储所有数据，随着数据量的增加，存储空间也不断增加。 一，布隆过滤器的原理： 当然还有一种不需要存储数据，快速判断数据X是否存在的神奇方法：松下问童子。 童子具有先验的知识，能够判断师傅（X）在山中采药。 若有多个童子都判断 师傅（X）在在山中采药。 我们是不是就可以更准确的判断X存在了。

​这也就是布隆过滤器算法的奇妙之处：由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数（具有先验的判断）组成的。 只需要几个函数 和 很少的bit 就可以高效完成判断。 布隆过滤器：用先验代替后验是存在局限的，因为童子的拥有唯一正确的先验只是 师傅不在草庐。比如：师傅不在草庐（是肯定的）、也可以不在山中（不一定只在此山中）、可能在山外。 布隆过滤器的误判是正向的误判即 存在是真的误判（判断“不存在“一定不存在，判断”存在“却不一定存在），这种误判是可控的，我们可以增加 具有信息的函数 或 增加bit 来存储更多差异信息来减少误判率。 误判率：布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。 二，布隆过滤器的使用场景 利用布隆过滤器的特性，可以高性能的解决一下棘手问题： 比如：在网页爬虫是的 URL 去重，比如重复爬取、基于多组函数的判断，可以垃圾邮件识别（有点贝叶斯的意思）、大集合中重复元素的判断和缓存穿透等问题。 主要思想，通过布隆过滤器，前置过滤一些 确定非的存在，比如后续使用过多资源去做无用功的判断。 它的意义很大，使用最少的资源 解决最多的问题。