布隆过滤器（Bloom Filter）是一种空间效率很高的概率型数据结构，用于判断一个元素是否在一个集合中。它允许一些误报（false positives），但不允许漏报（false negatives）。换句话说，如果布隆过滤器说一个元素存在于集合中，它可能是错误的，但如果说它不存在于集合中，则一定是正确的。

肖哥弹架构 跟大家“弹弹” 高并发锁， 关注公号回复 'mvcc' 获得手写数据库事务代码

欢迎 点赞，关注，评论。

关注公号 Solomon 肖哥弹架构获取更多精彩内容

历史热点文章

• 解锁大语言模型参数：零基础掌握大型语言模型参数奥秘与实践指南
  

• 高性能连接池之HikariCP框架分析：高性能逐条分解(架构师篇)
  

• 缓存雪崩/穿透/击穿/失效原理图/14种缓存数据特征+10种数据一致性方案
  

• Java 8函数式编程全攻略：43种函数式业务代码实战案例解析(收藏版)
  

• 一个项目代码讲清楚DO/PO/BO/AO/E/DTO/DAO/ POJO/VO
  

• 17个Mybatis Plugs注解：Mybatis Plugs插件架构设计与注解案例(必须收藏)
  

1、布隆过滤器设计原理图

布隆过滤器由一个位数组和若干个哈希函数组成。每个哈希函数会将元素映射到位数组的不同位置。具体步骤如下：

1. 初始化：创建一个位数组，所有位都设置为 0。

2. 添加元素：

3. 对元素应用所有哈希函数，得到若干个哈希值。

4. 将这些哈希值对应的位数组位置设为 1。

5. 查询元素：

6. 对元素应用相同的哈希函数，得到哈希值。

7. 检查这些位置的位是否都为 1：

8. 如果都为 1，认为元素可能存在于集合中（可能是误报）。

9. 如果任一位不为 1，认为元素一定不在集合中。

图解释:

• 元素添加/查询流程: 表示布隆过滤器处理元素添加和查询的整个过程。

• 元素: 需要添加或查询的元素。

• 哈希函数组: 一组独立的哈希函数，用于计算元素的哈希值。

• 位数组: 一个大型的位数组，用于存储哈希函数的计算结果。

• 索引 1, 索引 2, ..., 索引 k: 表示哈希函数计算得到的位数组中的位置索引。

• 位设置: 将哈希函数计算得到的索引位置在位数组中设置为 1。

• 元素状态检查: 在查询时，检查所有哈希函数计算得到的索引位置的位状态。

• 可能存在: 如果所有索引位置的位都为 1，则元素可能存在于集合中。

• 不存在: 如果任一索引位置的位为 0，则元素肯定不存在于集合中。

2、布隆过滤器的工作原理

图解释:

1. 开始添加元素:

2. 启动添加元素到布隆过滤器的过程。

3. 计算元素的哈希值:

4. 使用一组哈希函数对元素进行哈希计算。

5. 多个哈希函数:

6. 每个哈希函数生成一个索引位置。

7. 位数组:

8. 根据哈希函数生成的索引，将位数组中对应的位置设为 1。

9. 索引位置设为 1:

10. 实际设置位数组中索引位置的值。

11. 结束添加元素:

12. 完成元素添加过程。

13. 开始查询元素:

14. 启动查询元素是否存在的过程。

15. 检查索引位置:

16. 根据哈希函数生成的索引，检查位数组中对应的位置。

17. 所有位都是 1? :

18. 如果所有哈希函数生成的索引位置都是 1，表示元素可能存在。

19. 任一位是 0? :

20. 如果任一哈希函数生成的索引位置是 0，表示元素一定不存在。

21. 元素可能存在:

22. 说明查询的元素有可能在布隆过滤器中。

23. 元素一定不存在:

24. 说明查询的元素一定不在布隆过滤器中。

25. 结束查询:

26. 完成元素查询过程。

特点和注意事项:

• 空间效率: 相比于存储元素本身，布隆过滤器使用较少的内存空间。

• 时间效率: 添加和查询操作的时间复杂度接近 O(k)，k 是哈希函数的数量。

• 误判: 布隆过滤器允许误判（false positives），即判断元素存在但实际上不存在的情况，但不会漏判（false negatives）。

应用场景:

1. 缓存系统: 判断数据是否在缓存中。

2. 数据库索引: 优化数据库查询，减少不必要的查询。

3. 分布式系统: 减少对中心服务器的请求。

4. 大数据去重: 在处理大量数据时，用于数据去重。

3、位数组分析

布隆过滤器中的位数组是其核心组成部分之一。这个数组以位（bit）为单位存储信息，旨在高效地判断一个元素是否可能存在于一个集合中。位图是一种空间优化的数据结构，适合用于表示大量数据的存在性。其基本思想是将每个数据用二进制的“0”或“1”表示，“1”表示数据存在，“0”表示数据不存在。位图特别适合用于对海量整数数据进行存在性检查或排序操作。

通过上述的描述，相信读者对位图有了一定的了解，在了解了位图的定义之后，让我们用一个实例再来说明一下位图的作用：假设有 40 亿个不重复的无符号整数，我们需要判断某个数是否存在于这 40 亿个数中。通常的解决方法可能是将数据存储在数组或列表中，然后进行遍历或使用二分查找。然而，这两种方式的时间复杂度较高，而位图通过将每个整数映射到相应的比特位，能以较低的空间消耗实现高效查询。如上例，假设数据集中有 40 亿个整数，使用位图只需要约 512MB 的空间即可完成数据存储和查询。

4、布隆过滤器设计背景

布隆过滤器（Bloom Filter）由伯特·布隆（Burton Howard Bloom）于 1970 年提出，是一种概率型数据结构，用于判断一个元素是否可能存在于一个集合中。布隆过滤器的设计背景和动机主要基于以下几个方面：

4.1. 空间效率

在很多应用场景中，需要判断数据是否属于某个集合，而这些集合往往非常大。传统的数据结构如哈希表或查找树，虽然能提供高效的查找性能，但需要消耗较多的内存空间。布隆过滤器通过允许一定的误报率，显著减少了存储空间的需求。

4.2. 速度要求

在某些实时系统中，如数据库索引、网络爬虫的 URL 去重等，需要快速判断元素是否已经存在。布隆过滤器提供了非常快的查询速度，因为它只涉及位操作和哈希计算。

4.3. 分布式系统

在分布式系统中，数据的查找往往伴随着网络 I/O 的开销。布隆过滤器可以在本地快速判断数据是否存在，从而减少对远程服务器的查询请求，降低网络延迟。

4.4. 数据去重

在处理大量数据流时，如网络爬虫、日志分析等，需要快速去除重复数据。布隆过滤器可以用来检测数据是否已经出现过，从而避免存储或处理重复的数据。

4.5. 资源限制

在资源受限的环境中，如嵌入式系统、移动设备等，内存资源非常宝贵。布隆过滤器提供了一种节省内存的方式，使得这些设备能够有效地处理大量数据。

4.6. 可扩展性

布隆过滤器的另一个优点是它很容易扩展。通过增加位数组的大小和哈希函数的数量，可以调整其空间效率和误报率，以适应不同的应用需求。

4.7. 数学基础

布隆过滤器的设计基于概率论的原理，特别是哈希函数的独立性和随机性。通过数学计算，可以预测在给定的误报率和元素数量下，所需的位数组大小和哈希函数数量。

5、布隆过滤器特点与应用

布隆过滤器的优点

1. 空间效率：相比于其他数据结构（如哈希表），布隆过滤器可以更高效地使用内存。

2. 时间效率：布隆过滤器的查询和插入操作的时间复杂度都很低，接近 O(k)，k 是哈希函数的数量。

3. 简单性：布隆过滤器的实现相对简单。

布隆过滤器的应用场景

1. 缓存淘汰策略：用于判断数据项是否应该被缓存。

2. 数据库索引：减少数据库查询中的不必要的磁盘 I/O 操作。

3. 分布式系统：在分布式系统中，用于减少对中心服务器的查询请求。

4. 数据库系统：用于索引和查询优化。

5. 网络通信：用于检测和过滤重复的数据包。

6. 缓存系统：用于决定是否将数据加载到缓存中。

7. 大数据处理：用于数据去重和快速查找。

Java 实现布隆过滤器

在 Java 中实现布隆过滤器，我们可以使用一个位数组和几个哈希函数。以下是一个简单的布隆过滤器实现：

import java.util.BitSet;import java.util.HashMap;import java.util.Map;
public class BloomFilter {    private BitSet bitSet;    private int size;    private int hashCount;    private Map<Integer, java.util.function.IntFunction<Boolean>> hashFunctions;
    public BloomFilter(int size, int hashCount) {        this.size = size;        this.hashCount = hashCount;        this.bitSet = new BitSet(size);        this.hashFunctions = new HashMap<>();
        // 使用简单的哈希函数集合        // 这里只是，实际应用中应该使用更好的哈希函数        for (int i = 0; i < hashCount; i++) {            this.hashFunctions.put(i, j -> BloomFilter.hash(j, i));        }    }
    public void add(int item) {        for (int i = 0; i < hashCount; i++) {            int hash = hashFunctions.get(i).apply(item);            bitSet.set(hash, true);        }    }
    public boolean check(int item) {        for (int i = 0; i < hashCount; i++) {            int hash = hashFunctions.get(i).apply(item);            if (!bitSet.get(hash)) {                return false;            }        }        return true;    }
    // 简单的哈希函数，实际应用中请使用更复杂的哈希函数    private static int hash(int item, int index) {        return (item * 16777619) ^ (index * 2654435761);    }
    public static void main(String[] args) {        BloomFilter bloomFilter = new BloomFilter(1024, 3);
        bloomFilter.add(1);        bloomFilter.add(2);        bloomFilter.add(3);
        System.out.println(bloomFilter.check(1)); // true        System.out.println(bloomFilter.check(2)); // true        System.out.println(bloomFilter.check(3)); // true        System.out.println(bloomFilter.check(4)); // false    }}

解释

• BitSet: Java 提供的一个位数组的实现。

• size: 布隆过滤器的位数组的大小。

• hashCount: 哈希函数的数量。

• hashFunctions: 存储哈希函数的映射。

添加元素

1. 对于每个哈希函数，计算元素的哈希值。

2. 将位数组中对应索引的位置设为 1。

查询元素

1. 对于每个哈希函数，计算元素的哈希值。

2. 检查位数组中对应索引的位置是否都为 1。

3. 如果都为 1，返回 true，表示元素可能存在。

4. 如果任一位置为 0，返回 false，表示元素一定不存在。

注意

• 哈希函数的选择对布隆过滤器的性能至关重要。在实际应用中，建议使用更复杂的哈希函数，如 MurmurHash。

• hash() 函数在这里是用的简单哈希函数，实际应用中需要替换为更好的哈希函数实现。