多阶哈希


什么是多阶哈希?

多阶hash表实际上是一个锯齿多维数组:

■■■■■■■■■■■■■■■
■■■■■■■■■■■■■
■■■■■■■■■■
■■■■■■
■■■

每一行是一阶,数组的长度逐层减少,每层的长度都是素数。写入时,若第一层对应的位置已被占用,则第二层尝试,直到最后一层。读取时,则逐层查找。多阶哈希表通过多维数组来处理冲突,类似“开链法”。

构建

  1. 估算总数据量N,并选择合适的阶数K
  2. 每行数据量大约是N/K,从这个数字开始找K个素数,作为每一阶的表大小,建表。

效果评估

  1. 装载率

    装载率跟两个因素相关,一个是阶数,阶数越高装载率越高;每阶大小一样是不行的,此时退化为hash的开链法,此时装载率低的原因在于,如果一个key集合在第一阶都落到一个节点,则会在后面每阶都冲突,相对来说如果每阶是一个素数,则前一阶冲突的key集合在后一阶会平均分散开,提高了随机性。

  2. 查询平均深度

    为了提高装载率充分利用内存,一般的做法是提高阶数,所以我们一般的推荐是20~50阶。阶数增加并不是毫无代价的,阶数越多,查找深度越高,性能也就越低。

显然,1和2是矛盾的。我们的问题就是,在阶数控制在很少的情况下能否保持一个很高的装载率(90%以上)。

优化猜想

前宽后窄的多阶hash

分析传统多阶hash会发现,因为插入是从前往后查找,并插入到最靠前的一个空位,数据会很自然的靠前聚集。在连续插入直至失败时,前面一半多的阶装载都接近满的状态,而后面几阶非常空,这样一来,我们可以把前面的阶做宽,后面阶做窄,以提高整体的状态率。由于大部分key都集中在较浅的阶,只有少量的key在较深的阶,这样做也提高了查询的平均深度。

为了减少查询的平均访问深度,需要将前面的阶放款,但同时为了装载率,又不能让每一阶大小的递减速度太快,防止后面的阶“后劲不足”。前面的阶空置过大,后面的阶反而很满。同时还要控制总阶数。因此需要反复试验取一个较平衡的方式。

假设每一阶的大小满足等比(或者指数)递减:

  1. 根据总容量和下面两条进行计算,对第一阶选择一个合适的数字
  2. 每一阶大小是下一阶的P倍
  3. 总阶数不大于N

如此,通过实验来探查一个较好的选择。

cuckoo hash

使用cuckoo hash在插入失败的情况下做优化,其他情况保持不变,即:

  1. 假设多阶哈希总阶数为N,要插入的数据为K1
  2. 若插入失败,则指定以下流程
    a ) 在N/3到N/2的(即不满的阶)的阶,随机选择一阶N1
    b ) 将K1插入N1阶,踢出原位的K2
    c ) 对K2从N1开始重新执行哈希插入,直至插入成功。否则,重试2.a

如此,就可以延迟插入失败,提高多阶哈希的装载率