布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于判断一个元素是否在一个集合中。它基于位数组和多个哈希函数的原理，可以高效地进行元素的查询，而且占用的空间相对较小。

布隆过滤器的执行过程

1. 将要插入的元素使用多个哈希函数计算出多个哈希值。
2. 将计算出的多个哈希值映射到一个固定大小的位数组中，并将其对应位置的值设置为 1。
3. 查询时，对要查找的元素进行相同的哈希计算，并查询哈希值对应的位是否全部为 1。
4. 如果全部为 1，则说明该元素可能存在于集合中，但不能确定；如果有一个为 0，则说明该元素一定不在集合中。

布隆过滤器的使用场景

布隆过滤器的主要使用场景有以下几个：

• 集合成员资格测试：快速判断一个元素是否属于一个集合。
• 去重：在海量数据中快速去重。
• 缓存预热：预先将可能被查询的数据加载到缓存中。
• 废品邮件过滤：判断一封邮件是否为废品邮件。

Java 中的使用

在 Java 开发中，可以使用 Guava 中提供的 BloomFilter 类来实现布隆过滤器。

实现方法

以下代码展示了如何使用 Guava 实现布隆过滤器： java import com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels; public class BloomFilterExample { public static void main(String[] args) { // 估计要插入元素的数量 int expectedInsertions = 10000; // 误差率，取值为 0 到 1 之间 double fpp = 0.01; // 创建布隆过滤器 BloomFilter bloomFilter = BloomFilter.create( Funnels.stringFunnel(), expectedInsertions, fpp); // 添加元素到布隆过滤器 bloomFilter.put("element1"); bloomFilter.put("element2"); // 检查元素是否存在 boolean isPresent = bloomFilter.mightContain("element1"); System.out.println(isPresent); // true isPresent = bloomFilter.mightContain("element3"); System.out.println(isPresent); // false } }

使用注意事项

使用布隆过滤器时需要注意以下几点：

• 误差率不可避免：布隆过滤器是一种概率型数据结构，因此存在误差率。误差率大小取决于插入元素的数量和布隆过滤器的大小。
• 不可删除元素：一旦将元素添加到布隆过滤器中，就无法将其删除。
• 空间占用：布隆过滤器需要占用一定的内存空间。空间占用大小取决于插入元素的数量和误差率。

总结

布隆过滤器是一种高效的空间优化数据结构，可以用于快速判断元素是否属于一个集合。在 Java 开发中，可以使用 Guava 中的 BloomFilter 类来实现布隆过滤器。在使用时需要注意误差率不可避免、不可删除元素和空间占用等注意事项。

---

布隆过滤器

如果使用哈希表，内存空间需要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）与比特币

布隆过滤器（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内存空间。

优点

缺点