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

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

3.1.2 构造时间复杂度分析

指纹可变哈希布谷鸟过滤器的构造过程主要涉及将集合 P 和 N 内的元素先插入辅助布谷鸟哈希表, 然后根
O(1), 这就
据每个哈希桶内元素频率分布情况选取最优的哈希函数. 首先, 布谷鸟哈希表的插入复杂度平摊下来是
使得插入集合 P 内的元素的复杂度为 O(|P|), 而插入集合 N 内元素的复杂度为 O(|N|). 此外, 在搜寻最优哈希函数
时, 需要遍历所有候选指纹哈希函数, 然后找到最优的哈希函数. 由于候选的哈希函数数目取决于每个桶内哈希索
d
引单元的比特数 d, 也即 2 个候选指纹哈希函数. 因此, 搜索最优哈希函数复杂度为:

 
b−1
∑ 
  d   d d
O   N i ·2 ·c  = O(2·|N|·2 ·c) = O(|N|·2 ) (3)

 
i=0
d
将所有步骤的复杂度合并后可知, 最终的构造复杂度为 O(|P|+|N|·(2 +1)).

3.1.3 空间复杂度分析
对于空间复杂度, 过滤器的空间复杂度通常用 BPK (bits-per-key) 指标衡量, 即每个元素占用的比特数目, 该
参数通常是由用户指定. 因此, 在给定 BPK 和总元素个数的情况下, 空间复杂度为 p· BPK. 此外, 空间复杂度也可
以表示为 b·(d +c·e), 其中 b 是 VHCF 内包含的哈希桶个数, c 是 VHCF 单个哈希桶可存储的指纹单元数, d 是 VHCF
单个哈希桶内哈希索引单元比特数, e 是 VHCF 哈希桶内指纹单元的指纹长度.
复杂度分析总结: 在时间复杂度分析方面, VHCF 的查询复杂度是常数级别, 与标准布谷鸟过滤器查询复杂度
相同. 但由于引入哈希索引单元, 略慢于标准布谷鸟过滤器. 在构造时间复杂度方面, VHCF 的构造复杂度正比于
集合 P 和集合 N 的总大小, 同样由于引入了最优哈希函数搜索的步骤, VHCF 的构造时间复杂度高于标准布谷鸟
过滤器.

3.2 误判率分析
本文先计算在不考虑哈希索引单元的情况下的误判率, 即映射到相同哈希桶内的同时并且映射的桶内有相同
c 个长
的指纹信息. 因此, 由于本文只考虑静态场景下已经映射到同一个桶内的元素, 只需要考虑在同一个桶内和
度为 e 的指纹冲突的概率, 误判率表示为:

c
p = (4)
2 e
N 的元素内映射进入哈
进一步地, 本文继续考虑引入了哈希索引单元后的误判率, 为了分析方便, 本文将集合
d
希桶 B i 内的元素集合记为 , 并简记 |N i | = n. 由于引入了指纹哈希单元, 我们允许一个单元最多使用 2 个哈希函
N i
2 个哈希函数中误判元素个数最少的
d
数, 并且只选择误判率最低的哈希函数. 因此, 上述问题可以转化成为求解
哈希函数对应的误判个数, 即求解下列式子的期望:
1 2 2 d , i
min(h ,h ,...,h ) h 指代第 i 个哈希函数误判的元素个数.
i Y 且
这里, 首先可以发现 h 都是独立同分布的变量, 为了求解方便, 引入一个新变量

2 d
1
2
Y = min(h ,h ,...,h ) (5)
1
i
2

首先求解 Y 的累计概率分布, Pr(Y ⩽ i) = 1−Pr(h > i,h > i,...) . 由于 h 是独立同分布变量, 因此该式子可以简
化为:

2 d
1
1
2
Pr(Y ⩽ i) = 1−Pr(h > i)·Pr(h > i)·... ·Pr(h > i) = 1−Pr(h > i) 2 d (6)
1
1
Pr(h > i), 即单个哈希函数误判个数的累计概率分布函数. 通过分情况讨论, h 有如下几种情
下面, 继续求解
( )
n
1
1
n
况: (1) h = 0 的概率为 p 0 = (1− p) ; (2) h = 1 的概率为 p 1 = (1− p) p 1 = p(1− p) n−1 ; (3) 拓展至一般情况时, 误
n
1
( )
n
n−i
i
i 的概率, p i = p (1− p) . 因此, 可以得知:
判个数为
i
∑
1
Pr(h > i) = 1− p j (7)
j∈[0,i]
1
因此, 将 Pr(h > i) 代入下列式子, 可得: