Linear Hash

作者 chris.Yun 日期 2018-08-30
algorithm
Linear Hash

Linear Hash是一种动态哈希算法，可以动态的调整哈希表的大小，使得哈希表的查询性能保持O(1)的时间复杂度。

  • 静态哈希：哈希表初始化时，bucket数量已经确定（例如跟取模运算的值相同），当哈希表中元素数量增加时，每一个bucket对应的链表长度会增加，最后导致查询效率极速下降。
  • 动态哈希：与静态哈希相反，bucket数量可以动态调整（一般只增加），当哈希表中元素数量增加时，查询时间还是一个常量时间。

算法实现：

P: bucket桶的大小，保持不变
N：当前桶的数量
E：当前取模值变化的bucket的坐标
mod：模值
M1：当前最小模值
M2：当前最大模值 M2=M1+mod

扩容伪代码：

数据i插入到哈希表h中   

insert(i) {
    m_i = i % M1 

    if m_i < E
        m_i = i % M2

    when size(h.bucket(m_i)) == P:

        if m_i == E
            new Bucket(N), E++, N++, 
        else 
            递归扩容(E)

        if E+1 == M1
            M1 = M2
            M2 = M1 + mod
            E = 0

        for value in h.bucket(m_i)   
            if value % M2 == N-1
                h.bucket(m_i).remove(value)
                h.bucket(N).add(value)


    insert(i)
}

示例

P=5，mod=4，hash表新增元素24，bucket(0)位置已满，需要进行扩容

hash表初始情况

bucket id list E
0 4,8,12,16,20 *
1 5,9
2 6,10
3 7,11

扩容完成后hash表情况

bucket id list E
0 4,12,20
1 5,9 *
2 6,10
3 7,11
4 8,16

插入后的hash表情况

bucket id list E
0 8,16,24
1 5,9 *
2 6,10
3 7,11
4 4,12,20

扩容到3号时hash表情况，需要新增元素48

bucket id list E
0 8,16,24,32,40 *
1 9,17
2 10
3 11
4 4,12,20,28,36
5 5,13
6 6,14
7 7

插入后的hash表情况

M1=8,M2=16

bucket id list E
0 16,32,48
1 9,17 *
2 10
3 11
4 4,12,20,28,36
5 5,13
6 6,14
7 7
8 8,24,40

HashMap实际应用

了解线性哈希算法时，联想到HashMap的实现，重新看了下JDK1.8的源码（与1.6、1.7实现不太一样），http://yikun.github.io/2015/04/01/Java-HashMap工作原理及实现/ 这篇文章讲的很详细，可以了解的更快。

HashMap#resize()的过程，直接将bucket的容量扩充到两倍（8->16->32->…），将原有bucket的元素重新计算哈希放到新的bucket中去，由于扩容的长度都是2的幂，所以元素要么在原bucket位置，要么在原位置挪动2次幂。

because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.

例如，长度为8，以前在5，扩容之后可能在5，或者13。bucket数量为pow(2,n)，扩容后的数量为pow(2, n+1)，对于原bucket(i)上的元素来说，扩容后的可能位置为(i, i+pow(2,n))。

设计中比较巧妙的地方在于两点：

  1. 哈希函数不是采用的十进制的%，由于mod值（长度）是2的幂，因此采用的是 & 运算。

    (n - 1) & hash

  2. 移动位置的时候不需要重新计算hash，比如原来长度是8，扩容后变为16，对应的n二进制分别为，1000、10000即相当于多出来一个高位bit。因此，只需要看新增的bit位置是0还是1，0的话位置保持不变。

    if ((e.hash & oldCap) == 0) {
    if (loTail == null)
        loHead = e;
    else
        loTail.next = e;
    loTail = e;
} else {
    if (hiTail == null)
        hiHead = e;
    else
        hiTail.next = e;
    hiTail = e;
}
FEATURED TAGS
algorithm
FRIENDS