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

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

个桶内的哈希索引单元存储的哈希函数重新计算元素的指纹, 并在桶内检查是否存在相同的指纹. 需要注意的是,
由于根据哈希索引单元内的哈希函数重新计算指纹会引入额外的计算代价, 可能会降低查询的吞吐率. 为解决该
问题, 本文设计了一种单哈希技术, 可以大幅降低哈希函数计算的开销.

哈希桶

哈希桶结构
h 1 (x)

x
h 2 (x) 哈希索引单元 指纹单元 (4 个)

b 个桶
图 4 指纹可变哈希布谷鸟过滤器结构

下面首先介绍指纹可变哈希布谷鸟过滤器 (VHCF) 的查询流程, 然后介绍如何利用单哈希技术降低哈希函数
计算的开销.

2.4.1 查询流程
如算法 1 所示, VHCF 的查询操作由两部分组成: (1) 定位到两个候选映射的哈希桶 (步骤 1); (2) 在桶内搜寻
是否有相同的指纹 (步骤 2–5). 具体而言, 步骤 1 首先计算两个候选哈希桶的位置 h 1 (x) 和 h 2 (x). 步骤 2 是根据候
选桶内的哈希索引单元计算元素指纹信息, 步骤 3 就是在候选桶内搜寻是否有相同的指纹. 如果有相同的指纹, 步
骤 4 就返回查询的元素在 VHCF 内部, 否则步骤 5 就返回元素不在 VHCF 内.
算法 1. 指纹可变哈希布谷鸟过滤器 VHCF 的查询操作.

输入: 待查询元素 x;
x 是否在 VHCF 内.
输出: 元素

1. 计算映射到的两个哈希桶, 也即 h 1 (x) 和 h 2 (x);
2. 从哈希索引单元内获取哈希函数编号 i 并计算出指纹信息 f i (x) ;

3. If 桶 h 1 (x) 和 h 2 (x) 包含由指纹 f i (x) ;
4. Return x 在 VCHF 内;
5. Return x 不在 VHCF 内;

2.4.2 利用单哈希技术降低哈希计算开销
由于每个桶的指纹哈希函数是可变的, 导致在访问不同桶的时候, 需要反复计算不同的指纹哈希函数. 为了更
好地说明上述问题, 本文在图 5(a) 中给出一个例子. 在图 5(a) 中所示, 不同的桶用于产生指纹的哈希函数不同, 在
第 1 个桶内产生指纹的哈希函数是 f 1 (x), 而在第 2 个桶产生指纹的哈希函数则是 f 3 (x). 由于每个桶内的指纹哈希
函数不同, 因此每次访问一个桶的时候都需要重新计算新的指纹, 这就带来了额外计算开销, 而标准的布谷鸟过滤
器只需要计算一次. 为了解决这部分额外的计算开销, 本文引入了一种单哈希技术降低由于引入指纹可变哈希导
致的额外计算代价.
单哈希技术的基本原理是哈希函数复用. 为了更好地说明上述基本原理, 本文给出了具体的例子. 如图 5(b)
所示, 给定一个元素利用哈希函数产生指纹时, 实际产生的随机哈希值比较长, 一般可以达到 64 比特或者更长. 然
而, 布谷鸟过滤器中的指纹长度却比较短, 例如 6–12 比特. 因此, 本文可以复用这些较长的哈希值划分为多个较短
的哈希指纹, 如图 5(b) 下半部分所示. 总而言之, 通过使用单哈希技术复用哈希值, 可以规避或缓解指纹可变哈希
技术带来的计算开销.