maglev hash算法

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

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

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

offset = hash1(sever) % m

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

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

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

假设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)不可能成立。

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

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