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

李猛 等: 代价敏感的指纹可变哈希布谷鸟过滤器 3365

Case 1 哈希桶结构
1 110101 111101 010001 000101 待查询元素: x=(01010111000101001)
指纹哈希索引单元 指纹单元 (4 个)
f(x)
Case 2 哈希桶结构
3 010101 011111 000100 110111 哈希值: 010101 110001 010011 010100
f 1 (x) f 2 (x) f 3 (x) f 4 (x)
指纹哈希索引单元 指纹单元 (4 个)
(a) 指纹哈希函数不同导致冗余计算 (b) 单哈希技术复用哈希值降低哈希计算开销
图 5 利用单哈希技术降低哈希计算开销

2.5 指纹可变哈希布谷鸟过滤器的构造过程
本节介绍如何构造 VHCF, 以实现在给定数据集下整体的误判代价最低. 在集合 N 中, 元素被误判的根本原因
是其指纹与过滤器中的某个指纹发生冲突. 本文提出了改变产生指纹的哈希函数的方法, 以减少冲突的发生. 此
外, 指纹可变哈希布谷鸟过滤器的每个桶内还包含一个额外的哈希索引单元, 存储当前桶内用于产生指纹的哈希
函数编号. 在确定了基本方案之后, 下一个重要问题是如何选择最优的哈希函数, 以降低整体的误判代价. 为了解
决这个问题, 本文将哈希函数的选择问题形式化为一个优化问题, 并提出了算法 2 来降低整体的误判代价.
算法 2. 指纹可变哈希布谷鸟过滤器 VHCF 的构造算法.

输入: 元素全集 U;
输出: 元素 x 是否在 VHCF 内.

1. 根据应用需求将元素分别划分至集合 P 和集合 N 内;
2. 构造辅助布谷鸟哈希表, 再将集合 P 中每个元素 x 插入布谷鸟哈希表, 即桶 h 1 (x) 或 h 2 (x);
3. 将集合 N 中的元素同时标记插入布谷鸟哈希表的两个哈希桶, 即桶 h 1 (x) 和桶 h 2 (x);
4. For 哈希桶 B i :
5. 将映射到 B i 内的 P 集合内元素记为 , 并将集合 N 内映射到桶 B i 内的内元素记为 N i ;
P i
6. 初始化当前桶内误判代价 C i = +∞, 初始化当前桶最优哈希函数编号为 ;
I
7. For 指纹函数集合 {f 1 , f 2 , ..., f 2 d} 中每一个哈希函数 :
f i
 
∑ ∑ 
   
8.  f i (x) == f i (y);

f i , 时的误判代价
计算选择哈希函数
C(x)·Sign
 
 
x∈N i y∈P i
9. 如果 C < C i , 则将当前的函数编号记录进入 内部;
I
10. 将 I 的编号记录进入指纹可变哈希布谷鸟过滤器对应桶的哈希索引单元;
11. 依次生成 P i 内每个元素的指纹并记录进入 VHCF 对应桶内;

2.5.1 VHCF 构造过程
如图 2 所示, 构造 VHCF 的主要步骤分为 3 步: (1) 明确集合 P 和 N 内的元素; (2) 构建辅助布谷鸟哈希表;
(3) 求解最优哈希函数配置并生成指纹可变哈希布谷鸟过滤器 VHCF. 为了更清晰地展现构建过程, 完整的构建过
程见算法 2. 本文按照 3 个部分逐步解释整个的构建过程.
第 1 部分是划分不同集合内的元素, 见算法 2 的步骤 1, 根据应用的需求将不同的元素划分至对应集合. 例如,
网络多播机制中, 需要把转发的端口划分到集合 P 内, 而将其余端口划分进入集合 N 内. 下一步是构建辅助布谷
鸟哈希表, 见算法 2 的步骤 2、3, 需要分别将集合 P 内的元素和 N 内的元素分别映射到辅助的布谷鸟哈希表中.
N 的元素则会同时插入两个映射的
这里需要注意的是, 集合 P 内的元素只会放置在两个候选桶的中一个, 而集合