陌生但默默一统江湖的MurmurHash

看Jedis的主键分区哈希时,看到了名字很萌很陌陌的MurmurHash,谷歌一看才发现Redis,Memcached,Cassandra,HBase,Lucene都用它。

关于Hash,我之前只知道MD5,SHA1,SHA256还有Java自己的hashCode(),学校里怎么没教MurmurHash啊? 哦,原来这算法是2008年才被发明的,与MD5这些讲究安全性的摘要算法比,Redis们内部为主键做个Hash而已,就不需要安全性了,因此Google家的MurmurHash这种non-cryptographic的速度会快几十倍。详见Hash 函数概览(State of hash functions)

好了,以后要多用MurmurHash。在Java的实现,Guava的Hashing类里有,上面提到的JedisCassandra里都有Util类。

PS.有些人看到murmur就想到了陌陌就想到了别的,其实是 multiply and rotate的意思,因为算法的核心就是不断的"x *= m; x = rotate_left(x,r);"


 

Java的HashCode

那Java自己的String的hashCode()呢? 用的是Horner法则, s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

实现上是循环原哈希值×31再加下一个Char的值,算法及其复杂度简单一目了然,连我都能看懂。

for (int i = 0; i < str.length(); i++) { hash = 31*hash + str.charAt[i]; }

注意,int会溢出成负数,再溢成正数,比如"abcde"是 92599395, abcdef"是 -1424385949, "abcdefgh" 是 1259673732

Eclipse的自动代码生成的hashCode()函数也是类似的,循环原哈希值×31,再加下一个属性的hashCode()值。

31有个很好的特性,就是用移位和减法来代替乘法,可以得到更好的性能:31*i==(i<<5)-i。现在的VM可以自动完成这种优化。 Java自己的HashMap,会在调用Key的hashCode()得到一个数值后,用以下算法再hash一次,免得Key自己实现的hashCode()质量太差。

static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

那为什么Cassandra们不选简单直白的Horner法则呢?

我猜原因之一是它的性能,有个评测用js来跑的,还是murmur好些。

再猜原因之二它的变化不够激烈,比如"abc"是96354, "abd"就比它多1。而用 murmur"abc"是1118836419,"abd"是413429783。像在Jedis里,它的几个Shard节点的名字就叫做shard-1,shard-2,shard-3而已,hash这几个字符串,murmur的结果还能均匀的落在一致性哈希环上,用Honer法则就不行了。

 
文章持续修订,转载请保留原链接:http://calvin1978.blogcn.com/articles/murmur.html

This entry was posted in 技术. Bookmark the permalink.

4 Responses to 陌生但默默一统江湖的MurmurHash

  1. gaowei says:

    文章清楚明了,赞!

  2. Pingback: MurmurHash算法 | OpenWares | Open Source and Free Matters

  3. d says:

    d

  4. 匿名 says:

    谢谢

发表评论

您的电子邮箱不会被公开。

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>