如果使用哈希表，内存空间需要100亿*64字节=640G(10亿字节（byte）是1G)，空间就爆掉了。此时就轮到布隆过滤器登场了。
布隆过滤器应用场景：黑名单 爬虫去重
布隆过滤器优势：节省内存(30G以内)，查询速度快
布隆过滤器劣势：存在一定失误率
但布隆过滤器的失误率是可以容忍的，一是可以通过设计人为的把失误率控制的很低；二是就算失误了不会误报已经在黑名单里的URL。布隆过滤器只会把正常的URL当成黑名单系统里的，但不会误报已经在黑名单里的URL。形象点说就是“宁可错杀三千不会放过一个”
在讲解布隆过滤器原理之前先讲位图。
位图是bit类型的数组。 int类型4字节即32bit，所以长度100的int类型数组可以看出长度3200的bit数组。假如要找1782位比特，那么在int数组里下标是1782/32，在下标里存的int数字里第几个比特位？即1782%32的计算结果，从而把整型数组操作转换成比特类型数组操作。
布隆过滤器即大位图，假设是长度为m的bit数组，那么占用m/8位字节（Byte）,
URL加黑名单过程：开始时m位比特都是0（白）的状态，该URL通过哈希函数f1得到一个哈希值，然后%m,得到0~m-1上某个位置，将该位置描黑（变成1），再用哈希函数f2得到一个哈希值，再描黑，再用哈希函数f3同样处理（f1、f2、f3是独立的哈希函数），假设一共用了k个哈希函数，那么描黑了k个位置（某个位置重复了就重复了，但一旦描黑就没有描白的时候）完成后可以说该URL加入了位图里。对下一个URL同样处理，用k个哈希函数描黑k个位置……一直做100亿个，位图中有相当多位置被描黑了。
如何查某个URL在不在黑名单里？把待查的URL用K个哈希函数算出对应的哈希值，再把该哈希值%m，把K个位置的状态都拿出来，如果全黑，就说这个URL属于黑名单系统，如果有一个是白，就不属于黑名单系统。如果m很小，100亿个URL之后所有位图都是黑的，那么不论查谁都在黑名单里；如果m取的大一些，失误率就会降低。
但布隆过滤器需要准备多少个bit位和单样本的大小无关。一个URL经过K个哈希函数得到K个哈希值，对m取模后去相应的大比特map中描黑，只要保证哈希函数能接收单样本这种类型的参数就可以了，与样本是64字节还是128字节无关。所以影响失误率的重要参数就是样本量N和位图比特数组长度m。
布隆过滤器三公式： 出处
1.确定m:对于输入的数据量n（这里是100亿）和失误率p（这里是万分之一），布隆过滤器的大小m：m = - (n lnp) / (ln2 ln2)
2.确定K：K假如很少，例如只有一个哈希函数，相当于每个数据只采集了一个特征点，只把一个位置描黑，查的时候也只用一个哈希函数，特征点不够，失误率虽然不至于很高但有一定的量，如果K很大，例如用10万个哈希函数去把10万个位置描黑，m的空间会接近耗尽，查什么URL都是黑的，失误率非常高。需要的哈希函数的个数k：k = ln2 * m/n = 0.7 * m/n
3.因为前两步中公式1公式2都会进行向上取整，所以公式3算出的实际的失误率与比预期失误率要低
布隆过滤器在Hadoop中的应用：Hadoop中的分布式文件系统，是由许多小文件组成的，如何查询一个数据在哪个文件里？首先不可能记录每个小文件的索引，这样做占用空间太大了。所以每个小文件里都搞一个布隆过滤器，当Hadoop想知道某个key在哪个文件里，就查每一个布隆过滤器，文件a的布隆过滤器会说明你这个key在我这个文件里，但可能会有误报；文件c的布隆过滤器会说明你这个key在我这个文件里，但可能会有误报……如果失误率很低，哪怕有几万个分布式文件，最终可能算出来只有3个文件里可能含有这个key。那么就只用把这3个小文件遍历一遍，就知道key在哪个小文件里了。通俗点讲，如果一个文件真的含有key，那么它的布隆过滤器会说这个key属于我；但因为有失误率，可能会发生一个文件不含有这个key，它还是会说这个key属于我；可是这也没关系，多查一遍就可以，反正失误率很低，需要遍历的文件很少。
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合。它的优点是空间效率和查询时间都比一般的算法要好得多，缺点是有一定的误识别率和删除困难。
如果想要判断一个元素是否在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。数组、链表、树等数据结构都是这种思路，它们的时间复杂度为（O(n)、O(logn)）。散列表是一个能够提供更快查询速度的数据结构（时间复杂度为O(1)）。但是随着集合中元素的增加，我们需要的存储空间越来越大，特别是随着大数据的发展，我们越来越不可能将所有的数据都先加载到内存中再进行查找。
这时，我们就可以借助一种新的数据结构，也就是本文的主题：布隆过滤器（Bloom Filter）。
我们使用一段长度为m的二进制位数组，再使用k个哈希函数，将一个值进行k次哈希，得到k个索引，并将对应的位置设置为1。
布隆过滤器主要提供两种方法：Add和Test。
Add：通过哈希函数计算，得到k个索引，并将其对应的二进制位设置为1。
Test：通过哈希函数计算，得到k个索引，判断如果任意位置上的二进制都为0，则表示该值一定不在集合中；但是如果所有位置上的二进制都为1，却并不能表示该值一定在集合中，这被称为假阳性，或是判断错误。
可以通过增大数组的长度m，以及增加哈希函数的数量k来降低假阳性的概率。
时间复杂度
由于需要计算k次的哈希，需要的时间复杂度为O(k)，而计算出对应的索引后，可以进行直接地址访问，需要的时间复杂度为O(1)，所以总的时间复杂度为O(k)。
空间复杂度
由于需要长度为m的二进制数据，所以空间复杂度为O(m)，但是由于数据的基本单位是位，假设为了处理100万条数据，为了降低假阳性的概率，我们使用长度为1000万的二进制数组，所需的内存空间为10,000,000/8/1024/1024=1.2M内存空间。
优点
缺点
在上篇【链接】中，我们借助 Java 的 BitSet 源码尝试着理解了下 BitMap 算法，但是有一个很致命的劣势没有解决，那就是很尴尬的 数据碰撞问题 。
啥意思呢，再次解释一下下，BitMap 中我们只是很简单地初始化了一个 Long 数组，然后使用一个个小小的 bit 位来表示一个数据的存在与否，但是其中必然会面对 哈希碰撞 问题。
我们画张简图来回顾下 BitMap 算法。
如上图所示，hash function 均为 f1，数据 A 和 D 指向的位是 1 ，所以肯定是存在的，而 B 和 C 指向的都是同一个位，所以哈希碰撞就是这样很容易地产生了。
即：位上无元素则表示该数据肯定不存在，位上有元素则只能表示该数据 可能存在 。
有弊端总有解决之道，此处正好引入本文主要介绍的一种算法： 布隆过滤器 ，英文名为 Bloom Filter ，下文简称 BF 算法。
同样，我们还是先画一张简图来直观地认识下 BF 算法。
由上图我们可以看出，此时的 A、B、C、D 四个数据各自经过 f1 和 f2 方法进行两次 hash 算法，然后分别指向位上面，只有当 f1 和 f2 指向的位上面都为 1 时，才会标记为存在。
小结：BF 算法虽然在一定程度上减少了 BitMap 算法中的哈希碰撞，但是终言之，只是减少而已，没法完全避免，就像上文举的案例2一样。
通过上面的图，其实很容易看出，上图中 hash function 的数量是 2，假如我们计算 3 次呢？或者 4 次甚至更多呢？诚然这可以更进一步避免数据的碰撞问题，但是太多的话却适得其反。
所以介绍优化之前我们先小结下 BF 算法的劣势，因为优化都是基于某些劣势来进行的：
所以，针对上面的两个点，我们逐个来突破下：
1、关于误判率
BF 算法优劣的影响因素，其实很容易就可以联想到，一个是根据插入的数据总量（n）来计算出最合适的位数组的大小（m）和 hash 函数的个数（k），还有一个便是最优的 误判率 （使用 P(error) 表示）的选择问题。
比如：我们假设 P 为 0.01，此时最优的 m 应大概是 n 的 13 倍，而 k，应大概为 8。
详细的证明过程见下文。
2、关于元素删除的需求
因为数据对应的位会牵动其它的数据，所以 BF 是不可以删除位数据的，那么如果有这样的需求呢？可以使用 couting Bloom Filter 来解决，大致思路就是使用一个 counter 数组来代替位数组。
什么意思呢？简言之就是在原来的 BF 算法的位上面，不再是用简单的 0 或 1 来表示了，而是存储该位上面的数据总量，比如有两个数据经过 hash function 计算都有指向同一个位，则将该位标记为2，代表有两个数据，当删除其中一个数据时，只需要将该位上面的 2 调整为 1 即可，如此便不再影响其它数据的正确性。
BF 算法虽然有着一定的缺点（主要是误判率），但是它的优点更为突出，所以应用场景也是很广的。
比如我们在爬虫业务下，有很多的 URL，我们可以通过 BF 算法来判断每个 URL 是否已经被我们的爬虫程序处理过。
再比如邮箱服务中垃圾邮件的过滤策略，由于垃圾邮件是海量的，我们不可能使用一个很完整的散列映射来标记每一个垃圾邮箱的地址，此处可以使用 BF 算法来标记，从而节约了容量。
另外，BF 算法在很多开源框架中也都有相应的实现，例如：
1、误判概率的证明和计算
假设布隆过滤器中的hash function满足simple uniform hashing假设：每个元素都等概率地hash到m个slot中的任何一个，与其它元素被hash到哪个slot无关。若m为bit数，则对某一特定bit位在一个元素由某特定hash function插入时没有被置位为1的概率为：
现在考虑query阶段，若对应某个待query元素的k bits全部置位为1，则可判定其在集合中。因此将某元素误判的概率为：
从上式中可以看出，当m增大或n减小时，都会使得误判率减小，这也符合直觉。 现在计算对于给定的m和n，k为何值时可以使得误判率最低。设误判率为k的函数为：
下面求最值：
这说明了若想保持某固定误判率不变，则布隆过滤器的 位数 m 与添加的元素数 n 应该是线性同步增加的。
2、设计和应用布隆过滤器的方法
应用时首先要先由用户决定添加的元素数 n 和期望的误差率 P。这也是一个设计完整的布隆过滤器需要用户输入的仅有的两个参数，之后的所有参数将由系统计算，并由此建立布隆过滤器。
系统首先要计算需要的内存大小 m bits:
这里需要特别注意的是，9.6 bits/element 不仅包含了被置为1的 k 位，还把包含了没有被置为1的一些位数。此时的
此概率为某 bit 位在插入 n 个元素后未被置位的概率。因此，想保持错误率低，布隆过滤器的空间使用率需为 50%。
代码比较长，文章中暂不完整展示，更完整的代码 demo 详见【链接】。
下面列出了一小部分代码块，作用是根据插入的元素数量和过滤器容器的大小来计算实际的误报率：
本文转载自互联网，如有侵权，联系删除
