实现一个基于多重哈希的布隆过滤器变种（支持计数和删除操作） 题目描述 设计一个改进的布隆过滤器，支持以下操作： 添加元素 查询元素是否存在 删除元素 统计元素插入次数 与标准布隆过滤器不同，标准版本只能添加和查询，不支持删除（因为多个元素可能共享位），也不支持计数。我们需要使用多重哈希和计数阵列来突破这些限制。 解题过程 步骤1：理解标准布隆过滤器的局限性 标准布隆过滤器使用一个位数组和k个哈希函数。 添加元素：对元素进行k次哈希，将对应位置设为1。 查询元素：检查k个位置是否都为1（可能存在误判）。 无法删除 ：如果直接将某元素的k个位置归0，可能会影响其他共享这些位的元素。 无法计数 ：位数组只能表示0/1，无法记录同一个元素被添加了多少次。 步骤2：设计支持计数和删除的方案 为了支持计数和删除，我们不能使用简单的位数组，而应该使用一个 计数数组 。 每个数组位置不再存储0或1，而是存储一个计数器。 添加元素时，对元素进行k次哈希，将对应位置的计数器加1。 查询元素时，检查k个位置的计数器是否都大于0。 删除元素时，对元素进行k次哈希，将对应位置的计数器减1（需确保计数器不会为负）。 步骤3：处理哈希冲突和误判 即使使用计数数组，仍然存在误判可能性： 当查询一个从未添加的元素时，如果它的k个哈希位置计数器都巧合地大于0（因为其他元素的操作），则会误判为存在。 删除一个元素时，如果该元素从未被添加（或者已经删除），则可能导致计数器变为负数，这是不允许的。 解决方案： 在删除操作前，先执行查询操作。只有确认元素存在时，才执行删除。 使用更复杂的结构，如 布谷鸟过滤器 或 计数布隆过滤器 。我们这里实现计数布隆过滤器。 步骤4：数据结构设计 我们使用以下结构： 一个整数数组 counters[] ，长度为 m （数组大小）。 k个不同的哈希函数 h1, h2, ..., hk 。 一个容量参数，根据预期元素数量n和可接受的误判率p计算m和k。 步骤5：操作实现细节 添加元素 add(x) : 对x计算k个哈希值： index_i = h_i(x) % m 。 对于每个 index_i ，将 counters[index_i] 加1。 查询元素 contains(x) : 对x计算k个哈希值： index_i = h_i(x) % m 。 如果所有 counters[index_i] 都大于0，返回True（可能存在）。 否则返回False（一定不存在）。 删除元素 remove(x) : 先调用 contains(x) ，如果返回False，则无法删除。 否则，对每个 index_i ，将 counters[index_i] 减1。 统计元素插入次数 get_count(x) : 由于一个元素对应k个位置，理论上这些位置的计数器最小值就是该元素的插入次数（因为其他元素可能增加某些位置的计数）。 因此， count(x) = min(counters[index_i] for i in 1..k) 。 步骤6：哈希函数选择 选择k个独立、均匀分布的哈希函数。 实践中可以使用一个基础哈希函数，然后通过公式生成k个哈希值，例如： h_i(x) = h1(x) + i * h2(x) + i^2 确保哈希值在[ 0, m-1 ]范围内均匀分布。 步骤7：复杂度分析 时间复杂度：每个操作都是O(k)，即O(1)（因为k是常数）。 空间复杂度：O(m)，m根据n和p计算。 步骤8：误判率分析 误判率p ≈ (1 - e^(-k * n / m))^k 通过调整m和k，可以控制误判率。 这个设计在标准布隆过滤器基础上，通过计数阵列实现了删除和计数功能，同时保持了空间效率。