软件学报

作者：李猛，罗文啟，戴海鹏，王瀚橙，顾荣，陈贵海

单位：李猛，南京大学 计算机学院, 江苏 南京 21002311,罗文啟，南京大学 计算机学院, 江苏 南京 21002302,戴海鹏，南京大学 计算机学院, 江苏 南京 21002303,王瀚橙，南京大学 计算机学院, 江苏 南京 21002304,顾荣，南京大学 计算机学院, 江苏 南京 21002305,陈贵海，南京大学 计算机学院, 江苏 南京 21002306

关键词：布谷鸟过滤器;代价敏感;集合成员查询;误判率

布谷鸟过滤器是一种空间高效的近似成员资格查询数据结构, 在网络系统中被广泛应用于网络路由、网络测量和网络缓存等. 然而, 传统的布谷鸟过滤器设计并未充分考虑在网络系统中, 部分或全部查询集合已知的情况, 以及这部分查询具有代价的情况. 这导致现有的布谷鸟过滤器在该情况下性能无法达到最优. 为此, 设计了指纹可变哈希布谷鸟过滤器(VHCF). VHCF提出了指纹可变哈希技术, 感知已知的查询集合及其代价, 通过为每个哈希桶搜索最优指纹哈希函数, 从而大幅降低误判代价. 随后, 每个哈希桶的最优指纹哈希函数会被独立地记录进入每个哈希桶内的哈希索引单元. 此外, 提出了一种单哈希的技术用于降低引入指纹可变哈希技术导致的额外计算开销, 还对VHCF的操作复杂度和误判率进行了理论分析. 最后, 实验和理论结果都一致表明, VHCF在保证查询吞吐量相当的情况下, 取得了比现有布谷鸟过滤器及其变种都要低的误判率. 特别的, 在保持指纹长度相同的情况下, VHCF只需为每个哈希索引单元分配 1–2比特, 即可相比标准布谷鸟过滤器降低误判率12.5%–50%.

来源：2025年第7期

《软件学报》期刊编辑部

查看软件学报杂志2025年第7期