Murmur哈希

发表于 更新于 分类于

说到哈希算法，可能大部分人都会不自觉得想到 md 和 sha 系列，在这之前，我就是这样的，因为他们意味着流行安全和稳定。 但是，最近我知道了一款另类的流行的哈希函数，这款哈希函数广泛应用于分布式系统-Hadoop/Lucence等等， 原因就是因为它速度快而且散列效果好，这个哈希算法就是 MurmurHash。

哈希系列比较流行的有三个系列，分别是 MD/SHA 和 MAC 系列，但是这些系列都是比较安全， 虽然 MD5 和 SHA-1 已经被王小云教授碰撞了，但是相对我们平时使用的直接简单求模这种还是比较安全的， 相对安全带来的负面效果就是计算量还是挺大的，而且不保证哈希结果的均匀。 而在分布式环境下，为了资源的合理利用，我们需要的更多是均匀，因为是内部散列的作用， 所以哈希安全我们并不那么在乎，所以在这种情境下，2008 才被发明的 MurmurHash 成为了分布式中的宠儿，深受 Google 系的喜爱。

MurmurHash 当前最新的版本是 MurmurHash3，它能够产生出32-bit或128-bit哈希值。 除了我们能够猜到的不再使用的 mmh1 以及 还在使用的 mmh2 之外，还有好些变种，不过都是针对平台优化的。

Murmur哈希的算法确实比较简单，它的计算过程其实就是它的名字，MUltiply and Rotate， 因为它在哈希的过程要经过多次MUltiply and Rotate，所以就叫 MurMur 了。

具体算法就不介绍了，也不上伪代码和程序代码了，就以 Python 语言为例子，简单记录一下怎么使用

python 中有两个库可以使用，但是有一个是纯 cpp 迁移，所以比较少人用，另外一个比较多人使用，名字就是 mmh3，所以我们先安装一下它：

1
pip install mmh3

mmh3 其实就只有4个函数，hash/hash64 和 hash128，这三个函数都是返回整数，所以如果需要的话， 我们都是要自己转换成十六进制的。此外，还有一个是返回字节的 hash_bytes,它就返回直接序列，我们可以直接使用：

1
2
3
4
5
6
import mmh3

print(mmh3.hash('foo'))
print(mmh3.hash64('foo'))
print(mmh3.hash128('foo'))
print(mmh3.hash_bytes('foor'))

可以看到结果是：

1
2
3
4
-156908512
(-2129773440516405919, 9128664383759220103)
168394135621993849475852668931176482145
*\xc4\x9c\x94\x82\x07p\xb2\x9ci\xe1\xf6\xdd}\xbf\x05
  1. Murmur哈希 - 维基百科
  2. mmh3 - pypi
0%