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

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

1.1 布谷鸟哈希表
布谷鸟哈希表是一种高效的哈希表实现, 可以支持单个数据的插入和查询操作. 如图 3(a) 所示, 布谷鸟哈希表
c
由 d 个子哈希表组成, 其中的每个子表由 b 个桶组成并且每个桶有 个单元. 此外, 这些 d 个哈希子表分别使用 d
个哈希函数 h 1 , h 2 , ..., h d . 每个哈希函数都会将插入的元素均匀地映射到对应哈希表中的一个桶内. 给定元素 x,
i
c
它只会被放置在 d 个子表中的某一个, 即在第 个子表的桶 h i (x) 内. 同时, 由于一个哈希桶内最多有 个单元用于
c 个元素映射到同一个桶内时, 需要将冲突的元素移动到其他子表内的桶中. 例如, 如
存储元素, 因此当有超过
图 3(b) 中所示, 元素 x 在每个子表内映射的对应位置都已经被占用了, 因此需要将第 1 个子表内冲突的元素 y 先
踢出子表, 然后重新插入下一个子表. 这里如果下一个子表还是被占用, 上述过程可能要重复多次直到有一个空位
置被找到. 如果重复次数过多后依旧没有空位置, 那就表明当前哈希表已经装满了, 需要重新扩容以容纳更多的
元素.

p p c 个单元 c 个单元
h d (x) h d (x)
b 个桶 b 个桶 重插入
f(a) f(a) f(m)

h 1 (x) f(c) f(m)
h i (x) h i (x) f(c) f(x)
x z x z
y f(d) f(d)
重插入 x
f(e) f(g) f(e) f(g)
h 1 (x) h 1 (x)
y x
h 1 (x) + f(x) f(f) f(q) f(f) f(q)
(a) 布谷鸟哈希表 (b) 布谷鸟哈希表重插入 (c) 布谷鸟过滤器 (d) 布谷鸟过滤器重插入
图 3 布谷鸟哈希表和布谷鸟过滤器

布谷鸟过滤器 [18] 是基于布谷鸟哈希表的近似成员测试数据结构. 与布谷鸟哈希表不同的是, 布谷鸟过滤器不
存储整个元素, 而只存储元素的指纹信息, 从而可以使用更少的空间. 由于存储的是指纹信息, 因此布谷鸟过滤器
会产生误判, 将不在过滤器内的元素误认为在过滤器内, 但是这个误判率是很低的, 并且可以被理论证明是有
界的.
如图 3(c) 所示, 布谷鸟过滤器由单个哈希表组成, 这个哈希表由 b 个桶组成, 每个桶内包含 个单元用以存储
c
元素指纹信息. 当需要插入一个元素 x 进布谷鸟过滤器时, 每个元素都被两个哈希函数映射到 2 个桶中, 每个桶最
h 1 (x) 和指纹
多可以存储 c 个元素. 为了获取两个桶位置以及元素指纹信息, 布谷鸟过滤器仅仅使用两个哈希函数
哈希函数 f(x). 具体而言, 如果元素 x 的指纹为 f(x), 则其两个桶位置 idx 和 idx 2 由以下两个哈希函数给出:

1

idx 1 = h 1 (x),

.
idx 2 = h 1 (x)⊕ f(x).


这里只使用两个哈希函数的优点在于, 只需给定一个桶的位置和一个指纹, 就可以通过当前的桶位置和指纹
信息进行位异或操作, 从而确定另一个桶的位置. 如图 3(d) 所示, 布谷鸟过滤器的插入过程和布谷鸟哈希表类似,
也需要经历重插入过程, 从而尽可能提升可容纳的元素数目. 此外, 当指纹的长度为 e 时, 标准布谷鸟过滤器的误
c
判率可以由公式 给出.
2 e−1
1.2 布谷鸟过滤器的改进工作
为了拓展和提升布谷鸟可用性和功能, 前人已经提出了多种基于布谷鸟过滤器的变种. 这些变种基本关注 3
类问题: 提升布谷鸟过滤器的访问性能, 支持动态扩容以及支持更复杂的查询.
第 1 类变种工作主要着眼于提升布谷鸟过滤器的性能. 其中, Morton 过滤器 [19] 通过有偏插入机制和稀疏数据
压缩等技术, 直接提升了布谷鸟过滤器的插入、查询和删除等操作的性能. Vacuum 过滤器 [25] 关注过滤器在内存
访问时缓存的特性, 设计了由小范围到大范围逐步提升的重插入机制, 提升了布谷鸟过滤器的插入和查询性能. 此