转载

陌生但默默一统江湖的MurmurHash

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

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

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

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

陌生但默默一统江湖的MurmurHash

Java的HashCode

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

实现上是循环原哈希值×31再加下一个Char的值,有时int也会溢出成负数。算法简单一目了然,连我都能看懂。

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

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

还有Java自己的HashMap,会在调用Key的hashCode()得到一个数值后,用以下算法再hash一次,免得Key自己实现的hashCode()质量太差。

static int hash(int h) {

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

正文到此结束
Loading...