浅谈哈希算法
张梦瑜，毕艳婷，蔡斐钊，梁皓天
指导老师：杨仝
（北京大学 计算机系网络所 北京）
概述
哈希表作为一个最基本的数据结构，具有O(1)的查询时间复杂度，在计算机的很多领域都被广泛应用。本文将哈希算法的冲突解决策略分为经典策略、多子表多位置、设置片内摘要辅助、布谷鸟哈希的踢机制和完美哈希五大类，并对这五大类13种哈希算法进行综述。希望能够给研究者一定的研究启发。
关键词：哈希算法；冲突；性能比较
2
哈希表算法
本部分将介绍五类不同的哈希冲突处理策略：经典策略、多子表多位置处理策略、片内摘要策略、踢机制策略、完美哈希策略。
2.1 第一类：经典哈希算法
经典策略主要有链表法和开放寻址法。如果发生哈希冲突，链表法将在冲突位置设置链表，将冲突元素挂上去；开放寻址法会以例如线性探测、双散列函数探测、平方探测的方式对其他位置进行探查，如果有空位置则将冲突元素插入。
表1展示了经典哈希算法的查询表现。其中m是哈希总桶个数，n是哈希插入元素个数，a为装载率。如图所示，链表法具有较好的查询时间表现，但需要额外的指针开销空间。
2.2 第二类：多子表多位置
多子表多位置的核心思想是采用多个哈希函数，设立多个子表，使元素有多个侯选位置，这样相比于比单子表单位置，冲突概率会大大降低。
2.2.1 d-left哈希
d-left哈希采用“Always-Go-Left”策略，即插入元素时，如果有多个候选位置为空或者有多个长度相同的最短链表，则将元素插入到最左边的候选桶中。
算法分析
d-left的优点是有较高的装载率，同时并行查询和Always-Go-Left策略可以实现较好的查询效率。缺点是每个侯选位置都挂有链表造成了较大的空间开销，同时如果不能实现并行查询则需要对子表的多次访存。
2.2.2 Lossy 哈希，组相连
Lossy哈希主要应用在缓存场景下，类似于CPU中的组相连的缓存策略。当插入元素的多个侯选位置均不为空时，Lossy哈希会删除其中一个侯选位置的元素（比如一个很长时间不被访问的元素）。
算法分析
相比于传统的线性探测法，Lossy哈希的优点在于有较好的空间利用率， 保证了最差查询次数，减少了插入查询的平均探查次数。缺点在于有可能会丢弃元素，造成假阴性。
2.3 第三类：SRAM/DRAM，Bloom filter
采用例如布隆过滤器，二进制向量，指纹等片内摘要辅助哈希表的插入查询删除操作。布隆过滤器是一个二进制向量和一系列随机映射函数的组合，可用于检索一个元素是否在一个集合中，优点是空间效率和查询时间较好，缺点是具有一定的假阳性。
2.3.1 Peacock hashing
孔雀鸟哈希（Peacock hashing）[26]使用了大小等比递减的多级子表，其中最大子表为主表，其余子表为候选表。插入元素时按照子表大小依存探查，直至插入到一个空位置，如果均有冲突则丢弃该元素。在片内对每个候选表设置一个布隆过滤器。
算法分析
孔雀鸟哈希的优点在于使用片内摘要有效降低查询探测次数，只为候选表设置片内布隆过滤器，节约了片内内存。缺点在于有可能丢弃元素。
2.3.2 Segmented hash
分段哈希（Segmented hash）[27]有多个大小相等的子表，但只有一个哈希函数，并在片内设置了二进制向量、计数器、改进的布隆过滤器。二进制向量表示对应桶是否为空，计数器表示对应桶链表元素个数，改良的布隆过滤器用于在有多个侯选位置可选时，将元素插入到置为1个数最少布隆过滤器对应的子表中。
算法分析
分段哈希的优点在于使用多种片内辅助结构，并改进布隆过滤器，降低插入查询的访存次数，缺点在于占用了较多片内空间。
2.3.3 Fast hash table
快速哈希（Fast hash table）[2]有一个哈希表和计数器，哈希表的桶可以挂链表，计数器对应每个桶及链表元素总数目。如果有多个候选空位置，插入时将元素插入在计数器最小且子表索引最小的桶中，并将多个候选位置的计数器均加1。
算法分析
快速哈希的优点在于查询效率极高，如果所查元素不在表中，不需要进行访存就可以知道，（计数器有一个为0）。缺点在于插入删除操作较为繁琐，访存次数较高。
2.4 第四类：Cuckoo hash
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。
2.5 第五类：完美哈希，针对静态集合
完美哈希指的是直接构造一个没有冲突的哈希函数，就不会产生冲突了。
算法分析
完美哈希的优点在于有O(1)的插入查询，缺点在于完美哈希函数的构建很麻烦，且如果元素候选集发生改变，需要重新设计哈希函数和重建哈希表。
Davi de Castro Reis将多种高效的完美哈希算法进行了比较和实现，并将代码进行开源[34][35]。比较典型的完美哈希算法有CHD算法（Compress Hash and Displace）[36]， BMZ算法[37]，CHM算法[38]，FCH算法[39]，BDZ算法[40]，其中CHD算法和BDZ算法是效果较好。
2.6 Dcuckoo哈希
Dcuckoo使用多级子表和多个哈希函数，并在片内为每个子表设置指纹、二进制数据和布隆过滤器作为摘要，只有最后一个子表可以挂链表，插入元素时采用Cuckoo哈希中“踢”的机制。
算法分析
DCuckoo的优点是可以实现较高的装载率，且减少了片外访存次数，只在最后一个子表设置指针，节约了内存使用。缺点是，如果采用“踢”的机制需要更新布隆过滤器，但是布隆过滤器不支持删除操作，所以会降低查询效率。
2.7算法性能比较
3
硬件加速
硬件加速
FPGA（Field－Programmable Gate Array），即现场可编程门阵列。利用FPGA平台可以在片内内嵌SRAM，相对于片外有更高的访问速度，但SRAM价格昂贵，且由于空间限制，片内内存只能有很小的空间，所以需要将哈希表放在片外，将所需空间较小的摘要存在在片内，借助片内辅助访问片外，可减少片外内存访问。
除FGA平台外，我们还可以使用GPU-CPU实现片内-片外架构。GPU即图形处理器，最初主要用于图形图像相关的计算处理。GPU的每个处理器核心的数字逻辑运算单元相对简单，但由于其核数众多，拥有很强的并行计算能力。随着CUDA，OpenCL等语言的出现，GPU开始在科学计算领域得到广泛的应用。哈希函数的计算也是GPU的强项，因此我们可以将片内摘要存储在GPU的显存中。虽然GPU与GPU之间的单次通信有一定的延迟，但我们可以把查询请求一次性发送给GPU进行处理，以获得较高的吞吐量。与FGPA相比，GPU的实现成本较低，在消费市场较为常见。
4
总结与展望
总结与展望
本文介绍并分析了五大类共13种哈希算法，包括开放寻址法，可分为线性探测、双散列函数探测、平方探测等以及链表法；多子表多位置哈希算法，包括d-left哈希和Lossy哈希；设置片内摘要的哈希算法，包括Peacock 哈希、Segment哈希、快速哈希；采用踢机制的哈希表包括Cuckoo哈希和Hopscotch哈希；完美哈希及硬件加速相关内容。不同的应用场景会对哈希算法提出不同的性能要求，通过了解各种哈希算法的核心设计和优劣性，可以找到最合适应用场景的哈希算法。接下来我们希望能够更好的优化哈希算法，提出适合更多应用场景的新的哈希算法。同时也希望这些哈希算法能给读者以启发，激发读者对哈希算法进行改进和创新的灵感。