陌生但默默一统江湖的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);"
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);
}
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
