MurmurHash

介绍一种分布均匀的哈希算法——MurmurHash。它是由Austin Appleby在2008年发明的，并且经历了3次迭代，现在是MurmurHash3算法能够产生32位和128位的哈希值。MurmurHash不是加密型哈希函数，因而大多用于哈希式查找（hash-based lookups）。这个算法被多个开源项目引用，包括，nginx、libstdc++、Hadoop、libmemcached、npm、Guava等。MurmurHash的名字来源于内部循环multiply(MU)和rotate(R)。与这个算法一起发布的还有SMHasher哈希测试套件。

算法

MurmurHash3 的核心在于如下代码片段：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

c1 = 0xcc9e2d51;
c2 = 0x1b873593;
r1 = 15;
r2 = 13;
m = 5;
n = 0xe6546b64;

k *= c1; 
k = rotl(k,r1); 
k *= c2;

h ^= k;

h = rotl(h,r2); 
h = h*m+n;

其中c1输入数据的当前4字节块，h是最终的哈希值。rotl是位左旋转（rotate left）。

检验哈希函数的分布特性

SMHasher使用了术语**填充因子（fill factor）**来描述哈希函数的随机分布特性。填充因子就是给定一个表大小为N，键数目为K，如果所有键随机均匀分布在表的前F个槽，而F+1到N槽都是空的，那么 X=100*(F/N) 就是这个哈希函数的填充因子，可以认为这个哈希分布与在表上占据%X槽位的随机分布一致。

代数公式：

1
2

double f = (k*k - 1) / (n*r*r - k);
return 100 * (f / n);

其中k是键的数目，n是槽的总数，r是每个槽上的键数的均方根。

另

除此以外还有一些著名的哈希算法如：jenkins hash function、CityHash、Pearson hashing、Fowler-Noll-Vo hash function等。

参考阅读

MurmurHash in wikipedia Murmurhash3 wiki on github Murmurhash3 project Hash Distribution Hash FillFactor