Counting Bloom Filter 支持删除的实现
Counting Bloom Filter（计数布隆过滤器，简称 CBF）是标准布隆过滤器的扩展版本，它通过引入计数器机制，解决了标准布隆过滤器无法删除元素的致命缺陷。
一、为什么标准布隆过滤器不能删除？
1.1 问题的根源：位共享
标准布隆过滤器的底层是一个位数组（Bit Array）。当添加元素时，通过 k 个哈希函数将 k 个位置置为 1。
核心问题：多个元素的哈希结果可能映射到同一个位。如果直接将位从 1 设为 0 来删除元素 A，会“误伤”元素 B——因为系统无法区分这个位上的“1”是来自一个元素还是多个元素的叠加贡献。
1.2 标准布隆过滤器的不变性
| 特性 | 说明 |
|---|---|
| 假阴性为零 | 存在的元素一定被判定为存在 |
| 假阳性可能 | 不存在的元素可能被误判为存在 |
| 不可删除 | 无法安全地移除单个元素 |
删除操作如果处理不当，会破坏“假阴性为零”这一重要特性。
二、Counting Bloom Filter 的核心原理
2.1 数据结构改进
Counting Bloom Filter 的核心改进极其简单直观：将标准布隆过滤器中的位数组（bit array）替换为计数器数组（counter array）。
2.2 三种核心操作
| 操作 | 标准布隆过滤器 | Counting Bloom Filter |
|---|---|---|
| 添加 | 将 k 个位置置为 1 | 将 k 个位置的计数器加 1 |
| 查询 | 检查 k 个位置是否全为 1 | 检查 k 个位置的计数器是否全部大于 0 |
| 删除 | ❌ 不支持 | 将 k 个位置的计数器减 1 |
2.3 操作流程详解
以具体示例说明 CBF 的工作流程：
关键洞察：通过计数器机制，CBF 能够区分一个位上的“1”是由单个元素贡献还是多个元素共同贡献。当删除元素 A 时，只将其计数器减 1；如果其他元素也映射到相同位置，该位置的计数器仍然大于 0，因此不会错误地删除其他元素。
