maglev hash算法

 

maglev hash算法先把n个server填满大小为m的数组table(m > n，m为素数)； 然后算法选择table[hash(input)]中的sever。

1. 对每个server构建排列表(permutation)

1.1 计算

排列表的大小为m，计算如下:
 

offset = hash1(sever) % m

skip = hash2(server) %(m -1) + 1

permutation[i] = (offset + i*skip) % m

permutation[]是 [0, 1, .., m -1]的一个排列。

1.2 证明

假设permutation[]不是0,1...,m-1的全排列，则存在permutation[k]与permutaion[j]相等，
则下列等式成立：

(1)  (offset + k * skip) % m == (offset + j * skip) % m

(2) (k * skip) % m ==  (j * skip) %m

(3)  (k - j) * skip == x * m  ， 假设k > j，x >= 1

(4)  (k - j ) * skip / x == m

由于 1 <= skip < m，  1 <= (k - j) < m， m是素数，等式(4)不可能成立。

1.3 排列表的含义

假设server的排列表时permutaion[]，那么这个server希望放在hash表的位置permutation[i]的哈希桶中，permutation[0]的优先级最高，permutation[1]次之。

 

2. 按照排列表填哈系表

按照server的顺序，对每个server按照自己的排列表中的优先级，把自己放到哈希表中，如果该哈系统被占了，则选择下一个优先级。

3代码

代码maglev_hash