Page 445 - 《软件学报》2025年第7期

3366 软件学报 2025 年第 36 卷第 7 期

N 内两个桶内都要插入的原因是因为元素在判定是否在过滤器内部的时候需要检查两个哈希桶内
哈希桶内. 这里
是否有相同的指纹, 因此只有同时插入到两个映射的哈希桶内, 才能在后续步骤中规避集合 N 中的元素被误判. 注
N 内的元素插入辅助布谷鸟哈希表时采用标记插入
意, 由于最终的过滤器内不会存储集合 N 内的元素信息, 集合
的方式, 即挂载在这个桶内的一个指定空间, 这样就避免了集合 P 内的元素竞争辅助布谷鸟哈希表内哈希桶存储
空间. 第 3 部分是核心步骤, 需要根据辅助哈希表内每个桶内元素情况求解最优哈希函数. 为了解决这个问题, 本

文首先将这个问题形式化为一个优化问题: 寻找一个指纹哈希函数 f i , 使得当前桶内的误判代价最低, 也即

  
 ∑ ∑ 
  
   d
 min C(B i ) =  f i (x) == f i (y), i ∈ [0,2 −1]


 C(x)·Sign  
  


x∈N i y∈P i (1)
 {


 0, x < 0

 s.t. Sign(x) =


 1, x ⩾ 0
为了解决上述问题, 本文只需要遍历所有的候选指纹哈希函数, 然后选择误判代价最低的指纹哈希函数即可.
为了更好地说明上述过程, 本文将具体的步骤形式化地呈现在算法 2 的步骤 4–11. 首先, 步骤 4–11 会循环遍
历所有的哈希桶, 然后在循环过程中依次优化每个桶内的哈希函数. 步骤 5 将集合 P 和 N 中映射到当前哈希桶 B i
P i 和 . 步骤 6 C i 为最大整数值以及最优哈希函数编号 为
I
内的元素分别记录为集合 N i 初始化临时变量误判代价
−1. 步骤 7–9 计算每个候选指纹哈希函数的误判代价, 并将误判代价最低的指纹哈希函数记录进入变量 I 内. 如步
骤 10、11 所示, 在获取最优的哈希函数编号 I 后, 为当前桶内的 P i 元素使用最优的指纹哈希函数生成指纹, 然后
连同最优哈希函数编号和指纹一一对应地插入指纹可变哈希布谷鸟过滤器的相同的桶内. 构造结束.

2.5.2 优化构造过程
在构造指纹可变哈希布谷鸟过滤器时, 为哈希桶 B i 选择最优的哈希函数时, 需要遍历映射到该哈希桶内所有
P i 内的元素数量, 这就会极大地拖累整体的构造
的元素, 即 P i 和 . 这里集合 N i 内的元素数量可能会远大于集合
N i
时间. 为了应对集合 N i 内元素过多导致构造时间过长的问题, 本文提出一种优化后的构造过程. 每个哈希桶内只
K 个误判代价最高的元素. 为了实现
保存最多 K 个 N i 集合内的元素. 为了保证整体的误判代价最低, 本文只保存
上述目标, 可以先将集合 N 内的元素按照误判代价从高到低排序依次映射进入辅助布谷鸟哈希表内, 但每个桶内
只保留误判代价最高的 K 个元素, 进入下一轮用于搜寻最优哈希函数, 这直接降低了构造开销.

2.5.3 支持频繁更新的场景
尽管 VHCF 的设计主要面向静态集合场景, 但通过推迟和周期性重构, 在动态场景下 VHCF 的性能可以依旧
不逊于标准布谷鸟过滤器. 具体的方案如下: 当新元素插入 VHCF 的桶内时, 我们可以选择不立即进行重构, 而是
直接使用哈希索引单元内的哈希函数计算指纹, 然后将其直接插入. 通过这样的策略, 新插入元素的误报率与标准
布谷鸟过滤器完全一致. 最后, 等到元素变动比例超过一定阈值时, 才进行整体重构, 从而大幅降低误报率. 这一策
略有效地平衡了性能和动态变化的需求.

3 理论分析和优化
为了更好理解本文提出的指纹可变哈希布谷鸟过滤器的性能, 本节从查询复杂度、构造复杂度、误判率 3 个
方面展开进行理论分析. 下面先从查询复杂度入手, 然后再分析误判率.

3.1 复杂度分析

3.1.1 查询时间复杂度分析
指纹可变哈希布谷鸟过滤器查询过程和标准布谷鸟过滤器的查询过程相似, 都需要使用两个哈希函数访问两
个候选哈希桶, 然后检查两个哈希桶内是否含有匹配的指纹信息. 不同的是, VHCF 需要根据哈希索引单元重新计
算指纹信息. 因此, 指纹可变哈希布谷鸟过滤器 VHCF 的查询复杂度为:

O(2·(1+c)) = O(c) (2)
考虑到此处的参数 c 是个常数, 因此上述查询复杂度可以简化为 O(1).