必须用两个独立种子的哈希函数生成双表索引,踢出循环需清空旧槽位且限log₂(cap)次,空间利用率对比需运行50次取均值方差并导出CSV。

要在C++中实现布谷鸟哈希的插入策略并准确对比不同哈希函数组合下的空间利用率,必须先确保两个哈希表槽位索引严格由独立哈希函数生成,且插入失败时触发重哈希前需完整执行踢出链路。
初始化双表结构与哈希函数
定义两个大小相等的哈希表(vector
声明两个无状态哈希器对象hash1、hash2,各自封装独立seed与mixing轮数,避免编译器内联优化导致实际调用同一函数体。
核心插入逻辑:踢出-重定位循环
步骤一:计算当前键k在table1中的位置i1 = hash1(k) % cap,若table1[i1]为空,直接写入并返回true。
立即学习“C++免费学习笔记(深入)”;
步骤二:否则计算其在table2中的备选位置i2 = hash2(k) % cap,若table2[i2]为空,写入并返回true。
步骤三:若两处均被占,则随机选择一个位置(如掷硬币决定优先踢出table1[i1]还是table2[i2]),将该位置原值evict取出,更新k=evict,跳转回步骤一重新计算其两个新位置——这构成一次“踢出”迭代。
设置最大踢出次数为log₂(cap),超过则判定需扩容;每次踢出后必须清空被踢键的旧槽位,【漏清会导致后续查找命中脏数据】。
空间利用率对比实验配置
方法一:固定容量cap=4096,插入1000个随机整数,统计最终有效载荷数与总槽位数比值。
方法二:启用动态扩容机制——当插入失败且踢出超限时,将cap翻倍,重建两张新表,所有旧键按新hash规则重哈希插入。
方法三:引入二级缓存(stash)作为溢出区,仅当踢出循环达阈值且stash未满时暂存被踢键;stash满则强制扩容。记录stash平均占用槽位数。
运行三组各50次,取空间利用率(载荷/总分配槽位)均值与方差,输出至CSV文件供gnuplot绘图。


















