- kdd’21 高loadfactor的完美哈希设计方案
论文题目：MapEmbed: Perfect Hashing with High Load Factor and Fast Update
背景介绍
完美哈希的背景，是通过把键值对映射到一段连续的空间中来建立索引，并且在所有的插入过程中是不会发生冲突的。通常的组成形式都是一个小索引（比如一系列bucket的指针）加上一个键值对表（被上层指针指向的bucket）。
作者想利用在快速内存层保存一个虚拟索引表，并把索引表中的每一个条目和下层慢内存中的物理桶进行关联，最终保证了高效的空间利用率。
整体架构介绍
通过多层的逻辑映射，最终实现高效的空间利用率。设计的总体架构图如下，通过在上层的快速内存中建立一个虚拟的indextable对数据进行第一次映射，该层的每一个cell对应了底层慢速内存中的多个buckets，最终实现了一个有着更高空间利用率，支持快速动态插入的完美哈希表设计。
首先介绍该哈希表是如何支持插入操作的。
- 通过上层的第一个哈希函数把键值对映射到cell数组中
- 通过第二个哈希函数确定键值对应该放置在cell对应的几个buckets中的哪一个。
- 去下层慢速内存中找到对应的buckets，如果能够成功插入直接返回，否则要进行循环调整操作。
对于循环调整策略，一般的文字很难表达正确的意思，直接看下图中举出的例子。
例子一：例子一中要把蓝色的键值对插入，首先在上层通过第一个哈希函数hc确定好对应的cell，接着使用第二个哈希函数确定应该插入到4号桶的位置，但此时发现4号桶已经满了，因此只能首先把和5号cell相关联的所有桶中的数据进行循环移动操作，直到找到一种情况，可以把所有的键值对都放在对应的桶中且不溢出才停止。5号cell中保存的数字代表了循环移位的次数，保证了后续读取操作的正确性。
例子二：和例子一相同，不过需要循环移动两次，因此cell中保存的数字是3.
例子三：和例子一相同，只需要循环移动一次即可。
测试
主要对比了几种主流的完美哈希策略，并且针对本设计的几个超参数进行了测试说明。
思考
- 可能产生的写放大问题。
- 这种方法真的还能叫做完美哈希吗，因为其实在第二层无法放置键值对的时候，进行的循环移动操作更像是cuckoo hash中的驱逐操作。