redis布隆过滤器的c开发，java布隆过滤器解决redis缓存穿透

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

细嚼慢咽布隆过滤器(Bloom Filter)

在上篇【链接】中，我们借助 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 详见【链接】。

下面列出了一小部分代码块，作用是根据插入的元素数量和过滤器容器的大小来计算实际的误报率：

布隆过滤器

如果使用哈希表，内存空间需要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属于我；可是这也没关系，多查一遍就可以，反正失误率很低，需要遍历的文件很少。

如果面试官问你布隆过滤器，你该怎么回答？

假设遇到这样一个问题：一个网站有 20 亿 url 存在一个黑名单中，这个黑名单要怎么存？若此时随便输入一个 url，你如何快速判断该 url 是否在这个黑名单中？并且需在给定内存空间（比如：500M）内快速判断出。

可能很多人首先想到的会是使用 HashSet，因为 HashSet基于 HashMap，理论上时间复杂度为：O(1)。达到了快速的目的，但是空间复杂度呢？URL字符串通过Hash得到一个Integer的值，Integer占4个字节，那20亿个URL理论上需要：20亿*4/1024/1024/1024=7.45G的内存，不满足空间复杂度的要求。

这里就引出本文要介绍的“布隆过滤器”。

百科上对布隆过滤器的介绍是这样的：

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

是不是描述的比较抽象？那就直接了解其原理吧！

还是以上面的例子为例：

哈希算法得出的Integer的哈希值最大为：Integer.MAX_VALUE=2147483647，意思就是任何一个URL的哈希都会在0~2147483647之间。

那么可以定义一个2147483647长度的byte数组，用来存储集合所有可能的值。为了存储这个byte数组，系统只需要：2147483647/8/1024/1024=256M。

比如：某个URL（X）的哈希是2，那么落到这个byte数组在第二位上就是1，这个byte数组将是：000….00000010，重复的，将这20亿个数全部哈希并落到byte数组中。

判断逻辑

如果byte数组上的第二位是1，那么这个URL（X）可能存在。为什么是可能？因为有可能其它URL因哈希碰撞哈希出来的也是2，这就是误判。

但是如果这个byte数组上的第二位是0，那么这个URL（X）就一定不存在集合中。

多次哈希

为了减少因哈希碰撞导致的误判概率，可以对这个URL（X）用不同的哈希算法进行N次哈希，得出N个哈希值，落到这个byte数组上，如果这N个位置没有都为1，那么这个URL（X）就一定不存在集合中。

Guava框架提供了布隆过滤器的具体实现：BloomFilter，使得开发不用再自己写一套算法的实现。

BloomFilter提供了几个重载的静态 create方法来创建实例：

最终还是调用：

真正的byte数组维护在类：BitArray中。

最后通过：put和 mightContain方法，添加元素和判断元素是否存在。

1、因使用哈希判断，时间效率很高。空间效率也是其一大优势。

2、有误判的可能，需针对具体场景使用。

3、因为无法分辨哈希碰撞，所以不是很好做删除操作。

1、黑名单

2、URL去重

3、单词拼写检查

4、Key-Value缓存系统的Key校验

5、ID校验，比如订单系统查询某个订单ID是否存在，如果不存在就直接返回。

布隆过滤器的基本原理和使用

工作中遇到一个需求，需要从词库中快速判断某个关键字是否存在，词库大小不超过百万，当时脑子第一反应是用hash表相关数据结构，和同事一交流，同事推荐用布隆过滤器，查询效率不输hashmap，而且非常节省存储空间。经过研究发现布隆过滤器挺好用的，这篇文章来说说三点：

1.什么是布隆过滤器。

2.布隆过滤器基本原理。

3.布隆过滤器的使用方式。

布隆过滤器（Bloom Filter）是1970年由[布隆]提出的。它实际上是一个很长的[二进制]向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

a.下图是一个初始化后的长度为11的布隆过滤器结构，可以看成一个数组，还未放入任何数据，所有位的值都是0。

b.假如有三个hash函数（hash1、hash2、hash3）此时我们添加一个关键字进去，假设我们添加一个字母"a"，通过三个hash函数分别求出2、5、6，于是把下标为2、5、6的值都改为1。

c.此时我们根据字母"a"去布隆过滤器查找，判断a是否存在的流程如下图，由于对a进行三个hash函数取模得到的2、5、6下标的值都是1，说明这个a大概率已经存在了（为什么是大概率呢？因为布隆过滤器是一种概率型数据结构，存在非常小的误判几率，不能判断某个元素一定百分之百存在，所以只能用在允许有少量误判的场景，不能用在需要100%精确判断存在的场景）。

如果使用字母b进行查找，三个hash函数取模得到的是7、8、9或者3、5、6，发现这些下标对应的值都不全部是1，则判定为不存在。

相对于HashMap的优点：

布隆过滤器节省空间，无需存储全部数据，只需要将多个hash函数取模得到的下标对应位置的值改为1即可，无需存储全部数据，是一种极度节省存储空间的数据结构。

相对于HashMap的缺点：

布隆过滤器无法做到100%精确判断，而HashMap可以。布隆过滤器本质上是赌不同的字符串不太可能所有的哈希函数都发生哈希碰撞，虽然有极低的概率发生，但是基本可以把误判率控制在1%以内。