看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);"
那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);
}