浅谈哈希算法

2.4.1 Cuckoo hashing

布谷鸟哈希（Cuckoo hashing）于2001年由Rasmus Pagh和Flemming Friche Rodler提出，该哈希设计包含两个大小相等的子表和两个不同的哈希函数。插入元素时，依次考虑插入第一二个子表，如果均没有候选位置，则踢出其中一个元素，安插新元素，之后再进行踢出元素的插入操作。踢的次数若超过设置阈值，则需要重建原表。

算法分析

布谷鸟哈希创新性地引入“踢”的机制。这种设计的优点包括：较好地提高装载率（>95%），从而提升内存使用效率；有助于实现相对简单的查询，可控的最坏情况是进行两次探测，因而有利于处理读较多的操作。缺点是对于写较多的操作，对具有较高装载率水平的哈希表需要进行多次探测和踢操作；非动态更新，踢的次数一旦超过阈值会触发哈希表重建，而重建损害系统性能；查询平均次数高于经典链式哈希。

图4展示了在布谷鸟哈希中插入元素的过程。注意到，由于布谷鸟哈希插入子表的先后顺序固定， 第一个子表装载率会高于第二个子表，在布谷鸟哈希设计基础上提出的非对称布谷鸟哈希，即第一个子表的大小是第二个子表的两倍，可以解决这一问题。

2.4.2 Cuckoo filter

Cuckoo Filter的核心思想是设置每个桶对应4个entry，借助计算指纹的哈希函数，通过两个哈希函数 ，映射出两个候选位置i1和i2。如果两个位置均已有元素，则采取“踢”操作。

算法分析

Cuckoo Filter是Cuckoo Hash的变体。相比于布隆过滤器，Cuckoo Filter计算了关键字的指纹，对元素支持动态的插入和删除，在容忍一定假阳性的水平下空间开销更低。缺点是Cuckoo filter的桶的个数固定是2^n，并且网络流场景下表现不如Bloom filter，尤其当出现重复元素，若存储多个指纹时会消耗太多空间，若只存储一个指纹就不能支持删除元素。

2.4.3 Hopscotch Hashing

Hopscotch Hashing于2008年由Maurice Herlihy提出，仅包含一个哈希表和哈希函数。插入元素时首先进行一定范围的线性探测，如果线性探测范围均不为空，则找到最近的一个空桶，尝试将线性探测范围内的一个元素按照线性探测的规则插入到该空桶中，如果线性探测范围内所有元素均不能插入到该空桶中，则重建哈希表。

算法分析

Hopscotch Hashing可以采用比较简单的哈希函数，比经典的线性探测确定性更好，装载率达90%时仍表现良好。若想加快查询速度，可以使用位图辅助。

2.4.4 硬件定制优化Cuckoo哈希性能

OSDI 2018提出的level hash采用了Cuckoo hash的思想，同时针对非易失性存储器（NVM），作写优化。ICDE 2019的Multi-Copy Cuckoo哈希针对FPGA的片内片外，作插入查询优化，利用闲置的桶存储冗余信息。两者均显著提升Cuckoo hash表性能。最近几年发表在顶级会议上针对Cuckoo哈希的进一步优化和变种，还有ATC’19的CoCuckoo、ATC’17的SmartCuckoo和ATC’16的Horton Tables。