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

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

先搜索起点 (第 3–5 行). 该队列记录了每个元素的哈希桶索引、已确定的迁移路径以及当前探测深度. 需要注
意, 对于已确定的迁移路径, 若使用一个变长数组记录已确定路径的哈希桶索引和指纹槽下标会占用较多空间.
本文提出一种压缩编码方案, 该方案仅使用一个定长整数即可记录已确定的迁移路径. 如图 3 所示, 由于指纹槽
下标仅需两个比特位即可表示, 因此可以将已确定路径中的所有指纹槽下标编码到一个整数中. 在此基础上, 额
外使用一个比特位区分迁移路径的起始哈希桶. 根据起始哈希桶索引和迁移路径上的指纹槽下标, 可解码出完
整的迁移路径.

算法 3. 无锁并发布谷鸟过滤器的路径探查和元素迁移操作.
输入: 两个整数类型的变量 i 1 和 i 2 . 其中, i 1 和 i 2 表示两个路径探查起点桶地址;
输出: 一个布尔类型的变量 TRUE 或 FALSE. 其中, 输出 TRUE 表示操作成功, 即成功探查到可行迁移路径, 并成
功完成指纹迁移; 输出 FALSE 表示操作失败, 即无法探查到可行迁移路径.

1. /*注释: 开始路径探查过程*/
2. path_discovery:
q 为空;
3. 初始化广度优先队列
4. 插入元素 (bucket = i 1 , path = 0,depth = 0) 到队列 q 中;
5. 插入元素 (bucket = i 2 , path = 1,depth = 0) 到队列 q 中;
6. while ( q 不为空)
7. 取队列 q 队首元素 x;
8. 读取桶 [x.bucket] 的值;
9. for (桶 [x.bucket] 中所有的插槽)
10. if (该插槽中没有指纹)
11. 成功获得一条可行迁移路径;
12. 跳出第 6 行的 while 循环;
13. if (当前搜索深度未达到阈值)

14. 将插槽中存储的指纹的另一候选桶的信息 (bucket, path, depth) 入队;
15. 若无法成功探查到可行路径, 则返回 FALSE, 否则开始指纹迁移流程;
16. 解码第 11 行获得的可迁移路径;
17. 记录可迁移路径长度;
18. /*注释: 反向遍历可迁移路径并迁移元素*/
19. for (反向遍历可行迁移路径)
20. 获得源哈希桶索引;
21. 获得待迁移指纹的指纹槽下标;
22. 计算目标哈希桶索引;
23. if (源哈希桶索引和目标哈希桶索引相同)
24. continue;
25. 读取目标哈希桶中每个插槽中的指纹;
26. if (目标哈希桶中没有空插槽)
27. goto path_discovery;
28. 将待迁移指纹原子地从源哈希桶迁移到目标哈希桶中;
29. return TRUE;

路径探查与元素迁移分离技术初始化后不断取出队首元素, 读取队首元素对应哈希桶 (第 7, 8 行), 并检查