数据结构与算法

谷歌的一致性哈希算法

jump consistent hash

jump consistent hash是谷歌发表的一种一致性哈希算法.
空间复杂度: O(1);
时间复杂度: O(lgn).

设计目标：

1.平衡性，把对象均匀地分布在所有桶中。(这个大部分哈希算法都能做到)
2.单调性，当桶的数量变化时，只需要把最少量的对象从旧桶移动到新桶，不需要做更多移动。比如原来是10个桶,增加了10个桶,只需要移动一半的对象就好了.
(更改算法的输入参数n,会有一半的对象依然映射到原来的桶里,有一半的对象映射到新的桶里.)

问题分析

记 ch(key,num_buckets) 为桶数量为num_buckets时的hash函数,返回分配的桶下标。

  • num_buckets=1时:
    由于只有1个桶，显而易见，对任意k，有ch(k,1)==0。

  • num_buckets=2时:
    为了使hash的结果保持均匀，ch(k,2)的结果应该有占比1/2的结果保持为0，有1/2跳变为1。

由此可以归纳，一般规律是：

num_buckets从n变化到n+1后，
ch(k,n+1) 的结果中，应该有占比 n/(n+1) 的结果保持不变，
而有 1/(n+1) 跳变为 n+1。

因此，我们可以用一个随机数生成器，来决定每次要不要跳变，并且让这个随机数生成器的状态仅仅依赖于key。所以就得到下面这个初步代码：

1
2
3
4
5
6
7
8
9
10
int ch(int key, int num_buckets) {
    random.seed(key) ;
    int b = 0; 
    for (int j = 1; j < num_buckets; j++) {
        if (random.next() < 1.0/(j+1) ) {
            b = j ;
        }
    }
    return b;
}

算法正确性

(0-based)
n个桶,从0开始往n-2跳变(n-2次)，每次跳变的概率依次是1/2,1/3,1/4…1/n。
从而保证keys在每个桶分布的概率均匀。

1
2
3
4
5
6
7
P(b=0(初始值)) =每次都不变=1/2*2/3*3/4...(n-2)/(n-1)*(n-1)/n=1/n;
P(b=1) =1/2(变)*2/3(不变)*....=1/n;
P(b=2) =1(变或者不变)*1/3(变)*3/4*...(n-1)/n=1/n;
P(b=3) =1(变或者不变)*1(变或者不变)*1/4*4/5...*(n-1)/n=1/n;
P(b=k) =1*1....1/k(变)*k/(k+1)...(n-1)/n=1/n;
P(b=n-2) =1/n;
P(b=n-1) =1- (上述所有的和)=1-(n-1)/(n-2)=1/n.

算法复杂度

n为桶的数量的话,进行n-1次跳变判断,算法复杂度是O(n).

改进

改进的思路

通过随机数，确定下一个跳变的j，而不是对每一个位置进行跳变判断。
因为跳变的概率从1/2开始一直在减少，所以依概率来说每次跳变的间隔大于1,所以计算下一个跳变值的次数少于n-1.

定义P(b,j>=i)的含义为: 当前跳变值为b时,下一个跳变值为j,j>=i的概率.

假设我们使用0-base的数组,则下标i位置不变的概率为: (i+1)/(i+2)
下一个跳变值j>=i时,也就是[b+1,i-2]区间内保持不变,因此有:

1
2
3
4
5
P(b,j>=b)=1 //(显然下一个跳变值>b)
P(b,j>=b+1)=1 //(显然下一个跳变值>=b+1)
P(b,j>=b+2)=1*(b+1/b+2)
...
P(b,j>=i)= 1*(b+1/b+2)*(b+2)/(b+3)...(i-1)/i = (b+1)/i

假设有一个在[0,1]区间均匀分布的随机变量R,由于均匀分布的特性,R < k的概率为 k.
(例如R< 0.3的概率为0.3),P(R<(b+1)/i)= (b+1)/i = P(j>=i);

因此可以生成一个[0,1]范围的随机数r,规定r<(b+1)/i的时候,就有j>=i;
因此 i<(b+1)/r. 由于对于任意的i都有j>=i,因此:

1
j=floor( (b+1)/r)，

这样我们用一个随机数r得到了j。

改进后代码如下：

1
2
3
4
5
6
7
8
9
10
11
int ch(int key, int num_buckets) {
    random.seed(key) ;
    int b = -1; //  上次跳变值
    int j = 0; // 这次跳变值
    while(j<num_buckets){// j不能超出范围
        b=j; 
        double r=random.next(); //  0<r<1.0
        j = floor( (b+1) /r);
    }
    return b;
}

其中r为[0,1]区间的随机数(均匀分布)。
算法中使用了一个64位的线性同余随机数生成器。
结果分布的均匀性与输入key的分布无关，由伪随机数生成器的均匀性保证。
由于用的是伪随机数,生成器由key进行seed,因此能保证一致性.

时间复杂度

根据概率计算.
由于r平均为0.5,因此j平均来说是成倍增长的,因此改进后算法的平均时间复杂度为：O(log(n))

推荐文章