实现一个基于多重哈希的布隆过滤器变种（支持计数和删除操作）

题目描述：
布隆过滤器是一种空间效率很高的概率型数据结构，用于判断一个元素是否在集合中。但传统布隆过滤器不支持删除操作。本题要求设计一个支持计数和删除的布隆过滤器变种，使用多重哈希和计数数组来实现。

解题步骤：

1. 理解传统布隆过滤器的局限性

   • 传统布隆过滤器使用一个位数组和k个哈希函数
   • 插入元素时，将k个哈希函数计算出的位置设为1
   • 查询时，如果所有k个位置都为1，则元素"可能存在"（可能有误判）
   • 但无法支持删除，因为将一个位置从1改为0可能影响其他元素

2. 设计计数布隆过滤器数据结构

   • 使用计数数组代替位数组，每个位置存储计数器
   • 选择k个不同的哈希函数：h₁(x), h₂(x), ..., hₖ(x)
   • 确定数组大小m和哈希函数数量k（基于预期元素数量和误判率）

3. 插入操作实现

   • 对于要插入的元素x，计算k个哈希值：h₁(x)%m, h₂(x)%m, ..., hₖ(x)%m
   • 将对应位置的计数器加1
   • 示例：插入"apple"，k=3，m=10，哈希结果为[2,5,8]，则位置2,5,8的计数器各加1

4. 查询操作实现

   • 对于要查询的元素x，计算k个哈希值
   • 检查所有对应位置的计数器是否都大于0
   • 如果都大于0，返回"可能存在"；否则返回"肯定不存在"
   • 注意：可能存在误判（假阳性），但不会漏判

5. 删除操作实现

   • 对于要删除的元素x，计算k个哈希值
   • 先验证元素是否存在（所有计数器>0）
   • 如果存在，将所有对应位置的计数器减1
   • 重要：只能删除之前确实插入过的元素

6. 处理哈希冲突和误判

   • 计数器溢出问题：使用足够大的数据类型（如4字节整数）
   • 误判率分析：与数组大小m、哈希函数数量k、元素数量n相关
   • 最优参数选择：当k = (m/n)·ln2时，误判率最低

7. 性能优化考虑

   • 空间效率：计数数组比位数组占用更多空间，但支持删除
   • 时间效率：插入、查询、删除都是O(k)时间复杂度
   • 权衡：根据具体应用场景选择传统布隆过滤器或计数布隆过滤器

这种计数布隆过滤器在需要支持删除操作的场景中非常有用，如网络路由表、缓存系统等。