布隆过滤器的实现原理是什么？

## 作用 布隆过滤器是一种空间效率很高的概率型数据结构，用于快速判断一个元素是否可能存在于集合中。 它的判断结果分为两种： - **一定不存在**：如果判断元素不存在，那么该元素一定不存在，不会漏判。 - **可能存在**：如果判断元素存在，只能说明可能存在，可能出现假阳性。 ## 原理 布隆过滤器底层由两部分组成： - 一个长度为 `m` 的二进制位数组，初始值全部为 `0` - `k` 个相互独立的哈希函数 ### 1. 添加元素 添加元素时： 1. 使用 `k` 个哈希函数分别计算该元素，得到 `k` 个位数组下标。 2. 将这些下标对应的二进制位全部设置为 `1`。 3. 如果对应位置已经是 `1`，则保持不变。 ### 2. 查询元素 查询元素时： 1. 同样使用 `k` 个哈希函数计算出 `k` 个下标。 2. 检查这些下标对应的位： - 只要有任意一个位置为 `0`，该元素就一定不存在。 - 如果所有位置都为 `1`，则该元素可能存在。 ### 3. 误判原因 不同元素经过哈希后，可能映射到相同的位数组位置。一个不存在的元素，其对应的所有位置可能已经被其他元素设置为 `1`，因此会被误判为“可能存在”。 ### 4. 特点 - 空间占用小，不需要存储元素本身。 - 插入和查询速度快，时间复杂度都是 `O(k)`。 - 存在假阳性，但不存在假阴性。 - 传统布隆过滤器不支持删除，因为清除某一位可能影响其他元素。