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还是不太一样的, 只不过具体算法是如何计算的, 我也不是非常非常了解.
各种字符操作...