北大杨仝教授团队：多拷贝Cuckoo Hashing原理与应用

Multi-copy Cuckoo Hash是一种高级哈希算法，由北京大学的杨仝老师和Dagang Li等人在ICDE 2019年的论文中提出，其目的是为了改善Cuckoo Hashing在实际应用中的性能问题。Cuckoo Hashing的核心概念是基于多个哈希函数（如d个）为每个元素分配备用桶，同时结合了重定位（relocation）策略，旨在实现高负载比（load ratio）和平均O(1)的查找时间。然而，它牺牲了插入过程的简单性来换取高效的查找性能，因为插入过程中可能存在复杂的冲突解决，可能导致多次重插甚至死循环。 插入算法的关键步骤如下，假设d=2： 1. 使用hashA和hashB确定两个位置。 - 如果两个位置都为空，选择其中一个插入。 - 如果只有一个位置空，将元素插入空位置。 - 若两个位置都不空，尝试将元素踢出一个位置（如位置A），并将该元素的键通过hash函数找到其另一个位置（如位置B）。重复此过程直到找到空位或达到预设的最大踢出次数。 - 当踢出次数过多而未成功插入，表明表满，需要进行rehash操作，可能涉及到表的大小调整，通常是增加到下一个素数。 查找过程相对简单，只需检查原始哈希函数确定的位置，然后查看备用位置，如Cuckoohash(b)中的c，尽管这减少了查找所需的计算量，但可能会导致不确定的迭代次数，增加了潜在的复杂性。 影响Multi-copy Cuckoo Hash性能的主要因素包括： - **插入时的循环踢出**：标准Cuckoo Hashing的不确定性导致插入过程可能需要遍历整个链表，增加时间和空间消耗，甚至可能导致死循环。通过使用多副本，可以减少这种不确定性。 - **插入失败的损耗**：传统Cuckoo Hashing在插入失败时会进行rehash，涉及全表重算和数据迁移，效率较低。在多副本方案中，这方面的损耗有所缓解。 - **多桶检查**：查找时需要检查所有备用桶，尤其在表较大且存放在外部内存时，增加了查找时的数据访问延迟。 在硬件层面，例如Altera FPGA开发板中，对哈希计算和存储操作的性能考虑也至关重要。哈希计算在单个时钟周期完成，而片上SRAM读取需要3个时钟周期，写入仅需1个时钟周期。相比之下，片下SDRAM的读取速度慢得多，需要18个时钟周期。这些性能指标对于优化Cuckoo Hash算法在实际应用中的实现具有指导意义。