1. Murmur哈希算法是干什么的？
在之前的文章 [Cassandra教程]（十四）浅谈Cassandra的架构 以前之前的文章我们提到了数据模型以及Partition Key, 同时Cassandra维护了一个令牌环，这样当我们写入一条数据或者需要读取数据的时候，就知道首先去哪一台机器执行相应的操作。
在底层支撑令牌的算法，就是默默无闻但是几乎一统江湖的MurmurHash算法。
所谓Murmur，并不是我们常听到的陌陌，而是(multiply and rotate) and (multiply and rotate). 根据维基上面的解释：
MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。[1][2][3]由Austin Appleby在2008年发明，[4][5] 并出现了多个变种，[6] 都已经发布到了公有领域(public domain)。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。[7]
来源： https://zh.wikipedia.org/wiki/Murmur%E5%93%88%E5%B8%8C
上面的表述我感觉说的还是不够浅显，Murmur哈希算法最大的特点是：
- 碰撞率低
- 计算速度快
因此，不仅是Cassandra，在常见的大数据库底层，都使用了这个算法作为底层的存储算法。
注意：原生的MurmurHash算法，并不能保证无碰撞，只是碰撞率比较低。相关测试代码以及测试数据请看下文
原文链接：http://www.flyml.net/2016/09/05/cassandra-tutorial-murmurhash/
2. 几种常见的版本
最新的版本是Murmur3, 是原作者被Google挖去之后基于Murmur2的缺陷做了改进。Google之后又基于Murmur3做了SipHash算法，但是应用看起来没有Murmur广泛。
Murmur3只有32-bit跟128-bit两种版本，相比Murmur2，计算速度更快，但是不支持Murmur2里面的64-bit.
原文链接：http://www.flyml.net/2016/09/05/cassandra-tutorial-murmurhash/
3. 应用
Java上面的实现版本很多，可以直接从Cassandra的源码里面抠出来使用。见GitHub. 在使用上比较简单的还是基于Guava，并且也是最新的Murmur3.
具体的使用方法可以参考Google自己写的文档：https://github.com/google/guava/wiki/HashingExplained
|
1 2 3 4 5 6 |
HashFunction hf = Hashing.md5(); HashCode hc = hf.newHasher() .putLong(id) .putString(name, Charsets.UTF_8) .putObject(person, personFunnel) .hash(); |
写的还是比较清晰的。唯一需要强调的一点就是，如果你想在任何时候，相同的String值一定得出相同hash值，就一定要新创建hasher，也就是上面的第二行代码。
具体可以对比下面的代码以及输出结果：
---- 每次都新创建Hasher实例
|
1 2 3 4 5 6 7 8 9 10 11 12 |
public static void main(String[] args) { HashFunction hf = Hashing.murmur3_128(); String str = "test"; System.out.println(hf.newHasher().putString(str, Charsets.UTF_8).hash().asInt()); System.out.println(hf.newHasher().putString(str, Charsets.UTF_8).hash().asInt()); } // 输出： // 1958601117 // 1958601117 |
---- 复用Hasher实例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public static void main(String[] args) { HashFunction hf = Hashing.murmur3_128(); Hasher hasher = hf.newHasher(); String str = "test"; System.out.println(hasher.putString(str, Charsets.UTF_8).hash().asInt()); System.out.println(hasher.putString(str, Charsets.UTF_8).hash().asInt()); } // 输出： // 1958601117 // 1782720758 |
可以看到，如果复用hasher的话，即使是同一个string对象，hash值也不一样了。
但是Guava的hasher创建效率非常非常高。几乎体会不到差别时间。
再来一个测试碰撞率的实验代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
package test; import java.util.Set; import com.google.common.collect.Sets; import com.google.common.hash.HashFunction; import com.google.common.hash.Hashing; public class GuavaHashTest { public static void main(String[] args) { HashFunction hf = Hashing.murmur3_128(); Integer testSize = 20000000; Set<Integer> set = Sets.newHashSetWithExpectedSize(testSize); int containsSize = 0; for(int i = 0; i < testSize; i++) { int tmp = hf.newHasher().putInt(i).hash().asInt(); if(i % 5000 == 0 ) System.out.println("i=" + i); if(set.contains(tmp)) { System.out.println("stopped at :" + i); containsSize++; } else { set.add(tmp); } } System.out.println("containsSize=" + containsSize); System.out.println("dup_ratio =" + containsSize / (1.0 * testSize)); } } |
第15行可以自行调试测试数据量。
我的测试结果：
containsSize=46241
dup_ratio =0.00231205
结论：在我的测试之中，2KW条测试记录（虽然都是int）完全没有冲突发生的情况。 如果是使用Guava自带的32bit，或者是128-bit但是返回int值，就会出现冲突碰撞的情况发生。
本文为原创文章，转载请注明出处原文链接：http://www.flyml.net/2016/09/05/cassandra-tutorial-murmurhash/
文章评论
没看懂结论，“”“完全没有冲突发生的情况”，这个怎样理解，是按照测试用例就没有嘛？
"完全没有冲突发生的情况" 就是在2KW这个测试用例里面, 没有出现冲突的情况
String(i).hashCode();的方式计算，发现冲突的更少，为何会这样的？
在底层String跟Integer还是不太一样的, 只不过具体算法是如何计算的, 我也不是非常非常了解.
各种字符操作...