什么是多阶哈希？
多阶hash表实际上是一个锯齿多维数组：
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■
■■■■■■■■■■
■■■■■■
■■■
每一行是一阶，数组的长度逐层减少，每层的长度都是素数。写入时，若第一层对应的位置已被占用，则第二层尝试，直到最后一层。读取时，则逐层查找。多阶哈希表通过多维数组来处理冲突，类似“开链法”。
构建
- 估算总数据量N，并选择合适的阶数K
- 每行数据量大约是N/K，从这个数字开始找K个素数，作为每一阶的表大小，建表。
效果评估
装载率
装载率跟两个因素相关，一个是阶数，阶数越高装载率越高；每阶大小一样是不行的，此时退化为hash的开链法，此时装载率低的原因在于，如果一个key集合在第一阶都落到一个节点，则会在后面每阶都冲突，相对来说如果每阶是一个素数，则前一阶冲突的key集合在后一阶会平均分散开，提高了随机性。
查询平均深度
为了提高装载率充分利用内存，一般的做法是提高阶数，所以我们一般的推荐是20~50阶。阶数增加并不是毫无代价的，阶数越多，查找深度越高，性能也就越低。
显然，1和2是矛盾的。我们的问题就是，在阶数控制在很少的情况下能否保持一个很高的装载率（90%以上）。
优化猜想
前宽后窄的多阶hash
分析传统多阶hash会发现，因为插入是从前往后查找，并插入到最靠前的一个空位，数据会很自然的靠前聚集。在连续插入直至失败时，前面一半多的阶装载都接近满的状态，而后面几阶非常空，这样一来，我们可以把前面的阶做宽，后面阶做窄，以提高整体的状态率。由于大部分key都集中在较浅的阶，只有少量的key在较深的阶，这样做也提高了查询的平均深度。
为了减少查询的平均访问深度，需要将前面的阶放款，但同时为了装载率，又不能让每一阶大小的递减速度太快，防止后面的阶“后劲不足”。前面的阶空置过大，后面的阶反而很满。同时还要控制总阶数。因此需要反复试验取一个较平衡的方式。
假设每一阶的大小满足等比（或者指数）递减：
- 根据总容量和下面两条进行计算，对第一阶选择一个合适的数字
- 每一阶大小是下一阶的P倍
- 总阶数不大于N
如此，通过实验来探查一个较好的选择。
cuckoo hash
使用cuckoo hash在插入失败的情况下做优化，其他情况保持不变，即：
- 假设多阶哈希总阶数为N，要插入的数据为K1
- 若插入失败，则指定以下流程
a ) 在N/3到N/2的(即不满的阶)的阶，随机选择一阶N1
b ) 将K1插入N1阶，踢出原位的K2
c ) 对K2从N1开始重新执行哈希插入，直至插入成功。否则，重试2.a
如此，就可以延迟插入失败，提高多阶哈希的装载率
本文作者 ： cyningsun
本文地址 ： https://www.cyningsun.com/06-08-2018/multi-level-hash.html
版权声明 ：本博客所有文章除特别声明外，均采用 CC BY-NC-ND 3.0 CN 许可协议。转载请注明出处！