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 的核心在于如下代码片段:

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槽位的随机分布一致。

代数公式:

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

Leave a Reply

Your email address will not be published. Required fields are marked *