ps：如果这篇帖子对于还在找工作和找实习的你有所帮助，可以关注我，给本贴点赞、评论、收藏并订阅专栏；同时不要吝啬您的花花

一、布隆过滤器基础定义

布隆过滤器（Bloom Filter）是1970年由布隆提出的空间效率极高的概率型数据结构，核心功能是快速判断一个元素是否存在于某个集合中。它牺牲了极小的判断准确性，换来了远超哈希表、数组等传统结构的存储空间利用率和查询速度，是大数据场景下解决“存在性校验”的核心工具。

它的核心特点是：判断不存在则一定不存在，判断存在则可能存在，不存在漏判，仅存在极低概率的误判。

二、核心底层组件

布隆过滤器的底层核心数据结构为二进制位数组（Bit Array，也叫比特数组/位图），整套原理完全依托该结构搭配哈希函数簇实现高效存储与查询，两大组件缺一不可：

1. 二进制位数组（Bit Array）

这是布隆过滤器的底层存储载体，是一个长度固定为m的连续比特位数组，初始状态下所有比特位均为0。在Redis中实现布隆过滤器（依托RedisBloom模块）时，底层对应的Redis基本数据结构为Bitmap（位图），而Redis Bitmap本质是基于String（字符串）基础数据结构封装实现的，这也是它空间高效的核心原因——1MB空间就能容纳838万多个比特位，可支撑海量元素的标记。

2. 独立哈希函数簇

需要选取k个相互独立、低碰撞、分布均匀的哈希函数（日常场景常用2-8个），每个哈希函数能将任意输入元素（字符串、数字、对象等），映射为0到m-1之间的整数索引，也就是定位到位数组的某个位置。哈希函数的独立性和均匀性，直接决定了布隆过滤器的误判率高低。

三、完整工作流程

布隆过滤器的操作极简，仅包含初始化、插入元素、查询元素三步，无标准删除操作（基础版），具体流程如下：

1. 初始化阶段

提前确定两个核心参数：位数组长度m、哈希函数个数k；创建长度为m的二进制位数组，将所有比特位重置为0；加载k个独立哈希函数，完成过滤器的初始搭建。

2. 元素插入流程

当需要把某个元素加入集合时，执行以下操作：

1. 哈希映射：将待插入元素依次传入k个哈希函数，得到k个不同的数组索引值；
2. 比特置位：定位到位数组中这k个索引对应的位置，将所有位置的比特值从0改为1；

注意：即便多个元素映射到同一个比特位，该位仍保持1，不做叠加计数。

3. 元素查询流程

判断元素是否存在时，严格复刻插入的哈希逻辑，步骤如下：

1. 重复哈希：将待查询元素传入同样的k个哈希函数，生成k个对应的数组索引；
2. 比特校验：检查位数组中这k个索引位置的比特值：
3. 只要有任意一个比特位为0：该元素一定不存在于集合中（零漏判）；
4. 所有比特位均为1：该元素可能存在于集合中（存在误判可能）。

四、关键特性：误判根源与局限

核心结论：布隆过滤器只存在误判，没有漏判

1. 误判原因

误判的本质是哈希碰撞+比特位复用：多个不同元素经过k个哈希函数映射后，可能会占用相同的比特位组合。当查询一个未插入的元素时，它的k个哈希索引恰好被其他元素全部置为1，就会被误判为“存在”。

误判率可通过调整参数控制：增大位数组长度m、增加哈希函数个数k，能大幅降低误判概率，但会占用更多空间、降低查询速度。

2. 基础版无法删除元素

因为比特位是多元素共享的，删除一个元素时直接将对应比特位置0，会破坏其他共享该比特位元素的查询结果。如需删除功能，可使用变种结构计数布隆过滤器（用计数器替代单比特位，记录比特位被命中次数）。

五、核心优缺点

✅ 优势

• 空间利用率极高：无需存储元素本身，仅用比特位标记，海量数据下存储空间远小于哈希表；
• 查询/插入速度快：时间复杂度仅为O(k)，k为哈希函数个数，远低于遍历查询；
• 零漏判：判断不存在的元素，绝对不在集合中，可靠性强。

❌ 劣势

• 存在假阳性误判：不能100%精准判断元素存在；
• 基础版不支持删除：删除元素会影响其他数据的校验；
• 无法获取集合内的具体元素：仅能做存在性判断，不能遍历元素。

六、典型应用场景

布隆过滤器的特性完美适配大数据高并发场景，常见落地场景包括：

• 缓存穿透防护：过滤缓存和数据库中都不存在的无效请求，避免数据库压力过载；
• 黑名单校验：垃圾邮件、恶意IP、违规账号的快速过滤；
• 海量数据去重：爬虫URL去重、大数据集重复元素筛选；
• 推荐系统去重：避免给用户重复推荐相同内容。

ps：如果这篇帖子对于还在找工作和找实习的你有所帮助，可以关注我，给本贴点赞、评论、收藏并订阅专栏；同时不要吝啬您的花花