布隆过滤器java代码 布隆过滤器bitmap

布隆过滤器详解

布隆过滤器 （英语：Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。

创新互联公司为企业级客户提高一站式互联网+设计服务，主要包括成都网站设计、成都做网站、app软件开发、小程序开发、宣传片制作、LOGO设计等，帮助客户快速提升营销能力和企业形象，创新互联各部门都有经验丰富的经验，可以确保每一个作品的质量和创作周期，同时每年都有很多新员工加入，为我们带来大量新的创意。 

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树源迅、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为 ， ， 。

这个时候，布隆过滤器（Bloom Filter）就应运而生。

了解布隆过滤器原理之前，先回顾下 Hash 函数原理。

哈希函数的概念是：将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值。下面是一幅示意图：

所有散列函数都有如下基本特性：

但是用 hash表存储大数据量时，空间效率还是很低，当只有一个 hash 函数时，还很容易发生哈希碰撞。

BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的。

在初始状态时，对于长度为 m 的位数组，它的所有位都被置为0，如下图所示：

当有变量被加入集合时，通过 K 个映射函数将这个变量映射成位图中的 K 个点，把它们置为 1（假定有两个变量都通过 3 个映射函数）。

查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了

为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。

布隆顷凳过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。

这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。(比如上图中的第 3 位)

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数 ，另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集，其它任何数据结构都不能；

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。

另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器雹乎此加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。

在程序的世界中，布隆过滤器是程序员的一把利器，利用它可以快速地解决项目中一些比较棘手的问题。

如网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。

布隆过滤器的典型应用有：

知道了布隆过滤去的原理和使用场景，我们可以自己实现一个简单的布隆过滤器

分布式环境中，布隆过滤器肯定还需要考虑是可以共享的资源，这时候我们会想到 Redis，是的，Redis 也实现了布隆过滤器。

当然我们也可以把布隆过滤器通过 bloomFilter.writeTo() 写入一个文件，放入OSS、S3这类对象存储中。

Redis 提供的 bitMap 可以实现布隆过滤器，但是需要自己设计映射函数和一些细节，这和我们自定义没啥区别。

Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能。

在已安装 Redis 的前提下，安装 RedisBloom，有两种方式

直接编译进行安装

使用Docker进行安装

使用

布隆过滤器基本指令：

我们只有这几个参数，肯定不会有误判，当元素逐渐增多时，就会有一定的误判了，这里就不做这个实验了。

上面使用的布隆过滤器只是默认参数的布隆过滤器，它在我们第一次 add 的时候自动创建。

Redis 还提供了自定义参数的布隆过滤器， bf.reserve 过滤器名 error_rate initial_size

但是这个操作需要在 add 之前显式创建。如果对应的 key 已经存在，bf.reserve 会报错

我是一名 Javaer，肯定还要用 Java 来实现的，Java 的 Redis 客户端比较多，有些还没有提供指令扩展机制，笔者已知的 Redisson 和 lettuce 是可以使用布隆过滤器的，我们这里用 Redisson

为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器横空出世。论文《Cuckoo Filter：Better Than Bloom》作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。相比布谷鸟过滤器而言布隆过滤器有以下不足：查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数。

由于使用较少，暂不深入。

细嚼慢咽布隆过滤器(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 详见【链接】。

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

布隆过滤器

[TOC]

通过解决方案：

Java中如将数据存储在内存中，最简单的算法结构是HashMap。通过HashMap判断key是否存在，来判断数据是否存在。通过hash算法查找元素，时间复杂度基本是 O(1) （可能存在hash冲突后转换成链表或红黑树的情况，时间复杂度的影响可以忽略）。

使用HashMap速度很快，存储简单，绝大部分场景可以使用。但是HashMap 占用的空间比较大 ：

为什么出现布隆过滤器：

举例：

如1000万个Integer存储在内存中，占用空间为：4x32x10000000位，即1220兆。如布隆过滤器通过4字节存储（布隆过滤器通过多次hash对数据计算后--几次hash根据数据量指定，得到多个数据， 占用多个位 ），则占用空间为610M。比原有空间少一半。

个人觉得，此比较在字符等的比较中尤为有效银嫌。

一个字符串多个字符，根据编码方式，一个字符两个或三个字节，如10个字符，字符串存储占用20个字节，还有相关字符串相关的类信息的内存占用。

位存储，根据数据量的大小，hash的位数，灵活计算。如4个字节，则是原hashMap占用空间的五分之一。

（1）定义字节向量

先定义一个指定长度的字节数组（字节数组，数组内每个元素的值）。

如长度为8（一个字节大小），默认所有元素值均为0，如下：

（2）计算哈希值

将要写入过滤器的数据，根据一定数量的哈希函数，得到多个哈希值，再依次判断每个哈希值对应的索引。

如使用3个哈希函数，计算得到3个哈希值，判定哈希值对应的字节向量为为1，3，7。

（3）更新字节向量

将计算出的字节向量的索引， 对应的字节向量中的元素值更高为1 （无论之前为0或者为1，均更改为1）。如下：

（1）计算哈希值

将要判断过滤器中是否存在的数据，根据一定数量的哈希函数，得到多个哈希值，再依次判断每个哈希值对应的索引。

如使用3个哈希函数，计算得到3个哈希值，判定哈希值对应的字节向量为为1，3，7。

注意：哈希函数的判断方式和计算索引的方式，需和写入数据时完全一致。

（2）判断是否存在

如原字节数组中，对应1，3，7中存在的元素的值都为1。则判定为此元素 可能存在 ，但凡有一个元素的值不为1，则判定此元素 一定不存在 。

布隆过滤器，主要需实现的目标是， 在指定的数据个数范围内，满足误判率在设定的范围内 ，误判率太高的话，无法起到过滤数据的情况，误判率不能为0。

因此需要计算两个数据来满足 存储数据的个数 和 误判率 ：

使用布隆过滤器的决定性因素之一，就是此算法插入数据和查询数据的速度必须非常快。因此在对数据进行哈希运算的时候， 需选择计算快的哈希算法 。

而且， 写入数据以及查询数据的哈希算法，顺序和算法都需完全一致 。

待完善。。。。。

可以通过google的 guava ，在内存中轻松实现布隆过滤器。

无需手动计算满足字节数组的长度和哈希个数，只需要输入 拟输入数据的个数 和 期望误判率 即可。

不输入期望误判率的情况下，误判率为0.03，即100个非范围内的数据进行校验时，约三个数据会判定茄搏芹为存在。

多次执行，结果一致，根据结果判定：

内存的存储存在局限性，可以使用redis中的bitMap来实现字节数组的存储。

使用redis实现布隆过滤器。需要根据公式，手动计算字节数组的长度和哈希的个数。

实现过程，待完善。。。颤毕。。。