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

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

VHCF). 我们注意到布谷鸟过滤器中元素被误判的根本原因在于一个桶内元素的指纹发生了冲突. 为了解决这个
问题, 指纹可变哈希的基本思想是通过改变产生元素的指纹信息的哈希函数, 使得指纹可以改变, 避免一些代价过
高的元素被误判. 为了实现指纹可变的目标, 一个简单的解决方法是为每个指纹均匀地分配独立的空间, 用于记录
产生指纹的哈希函数. 然而, 均匀地分配空间会降低整体的空间利用率. 这是因为很多元素不会发生冲突, 或者发
生冲突的代价很低, 为这样的元素分配独立的空间不会起到作用. 另一方面, 一些元素发生冲突的代价比较大, 给
它们分配的空间不够还会造成整体的误判代价较高. 因此, 在指纹可变哈希布谷鸟过滤器中, 本文采取了以哈希桶
为单位来选择最优的哈希函数, 即在同一个桶内的元素使用相同的哈希函数产生指纹, 并且产生指纹的哈希函数
会被每个哈希桶统一记录.
为了更好地说明, 我们以图 2(b) 为例解释具体的构造步骤. 如图 2(a) 描述了前置步骤, 即根据应用自身需求
N
划分集合 P 和集合 , 集合 P 中的元素会被插入到过滤器中, 而集合 N 中的元素会在过滤器中进行查询. 然后, 如
图 2(b) 所示, 再构造一个辅助布谷鸟哈希表 (cuckoo hash table), 借助辅助布谷鸟哈希表我们可以有针对性地优化
每个哈希桶所使用的哈希函数, 以降低总体误判代价. 最后, 我们可以得到如图 2(c) 所示的优化后的哈希函数, 其
中每个哈希桶内哈希索引单元内的数字表示该桶内元素使用产生指纹的哈希函数编号.

哈希索引单元 指纹单元

h 1 (x) h 1 (x)
正元素 P
优化哈希函数
x
x
负元素 N h 2 (x) h 2 (x)

(a) 根据应用需求划分集合 (b) 构建辅助布谷鸟哈希表 (c) 构建可变哈希布谷鸟过滤器
图 2 构建代价敏感的指纹可变哈希布谷鸟过滤器框架图

最后, 在多个数据集上广泛测试了本文提出的指纹可变哈希技术的布谷鸟过滤器, 结果显示, 在使用相同的空
间下, 本文的方法相比传统布谷鸟过滤器, 整体的误判率平均降低至原来的 20%–33%.
本文的创新点包括: (1) 在问题定义层面, 引入了代价敏感近似集合成员查询问题, 指出查询集合的全部或部
分是可以获取的, 并且每个查询拥有一个误判代价来反应其重要程度. (2) 在方法层面, 本文提出了一种全新的指
纹可变哈希技术, 优化每个桶的指纹生成函数, 降低误判代价. (3) 在理论分析和实验层面, 本文提供了严密的理论
分析和丰富的实验证明, 从多角度论证了提出方法的优越性.
本文第 1 节介绍基础知识以及布谷鸟过滤器相关工作. 第 2 节详细介绍指纹可变哈希布谷鸟过滤器的设计思
路和操作方法, 包括如何通过改变产生元素的指纹信息的哈希函数来避免元素冲突, 以及如何选择最优的哈希函
数. 第 3 节给出指纹可变哈希布谷鸟过滤器的性能理论分析. 第 4 节通过对比实验验证所提过滤器的有效性. 第 5
节总结全文并对指纹可变哈希布谷鸟过滤器的优势和不足进行讨论, 并提出未来的研究方向.

1 布谷鸟过滤器研究背景和相关工作

考虑到现有基于布谷鸟过滤器的相关工作都沿用布谷鸟哈希表的结构, 并在此基础上提升布谷鸟过滤器的性
能及增加其功能, 因此本文将从基础的布谷鸟哈希表和布谷鸟过滤器开始介绍相关工作.