Murmur哈希

Murmur哈希是一种非加密散列函数，适用于一般的基于散列的查找。它在2008年由Austin Appleby创建，在Github上托管，名为“SMHasher” 的测试套件。 它也存在许多变种，所有这些变种都已经被公开。 该名称来自两个基本操作，乘法（MU）和旋转（R），在其内部循环中使用。

与加密散列函数不同，它不是专门设计为难以被对手逆转，因此不适用于加密目的。

种类Murmur哈希32018年的版本是Murmur哈希3，它产生一个32位或128位散列值。 使用128位时，x86和x64版本不会生成相同的值，因为算法针对各自的平台进行了优化。

Murmur哈希2旧的Murmur哈希2 产生一个32位或64位的值。 较慢版本的Murmur哈希2可用于大端和对齐的机器。 Murmur哈希2A变体添加了Merkle-Damgård构造，因此可以逐渐调用它。 有两种变体生成64位值; 针对64位处理器的Murmur哈希64A和针对32位处理器的Murmur哈希64B。 Murmur哈希2-160生成160位散列，而Murmur哈希1已过时。

实现规范实现以C ++语言实现，但是对于各种流行语言，包括Python，C，Go， C#，D，Lua Perl，Ruby， Rust，PHP，Common Lisp，Haskell，Clojure，Scala，Java，Erlang，和JavaScript，以及一个在线版本。

它已被纳入许多开源项目中，其中最引人注目的是libstdc ++（ver 4.6），nginx（ver 1.0.1），Rubinius， libmemcached（Memcached的C驱动程序）， npm （nodejs package manager）， maatkit ，Hadoop ，Kyoto Cabinet ，RaptorDB ， OlegDB， Cassandra ，Solr ， vowpal wabbit ， Elasticsearch，Guava 和RedHat虚拟数据优化器（VDO）1。

漏洞如果用户可以选择输入数据以有意造成散列冲突，则散列函数容易受到攻击。 Jean-Philippe Aumasson和Daniel J. Bernstein能够证明，即使使用随机化种子实施Murmur哈希也容易受到所谓的HashDoS攻击。 通过使用差分密码分析，他们能够生成会导致哈希碰撞的输入。 攻击的作者建议使用他们自己的SipHash代替。

算法Murmur3_32(key, len, seed)//注意：在这个版本中，所有的整数算术运算都是无符号的32位整数。 //在溢出的情况下，结果受模数应用的限制c1 ← 0xcc9e2d51c2 ← 0x1b873593r1 ← 15r2 ← 13m ← 5n ← 0xe6546b64hash ← seedfor each fourByteChunk of keyk ← fourByteChunkk ← k × c1k ← (k ROL r1)k ← k × c2hash ← hash XOR khash ← (hash ROL r2)hash ← hash × m + nwith any remainingBytesInKeyremainingBytes ← SwapToLittleEndian(remainingBytesInKey)//注意：只有在big-endian机器上才需要Endian交换。 //目的是将有意义的数字放在值的低端， //这些数字最有可能影响低范围数字 //在随后的乘法中。 考虑定位有意义的数字 //在高频范围内会对高位数产生更大的影响 //乘法，特别是，这样的高位数可能会被丢弃 //通过溢出下的模运算。 我们不希望这样。remainingBytes ← remainingBytes × c1remainingBytes ← (remainingBytes ROL r1)remainingBytes ← remainingBytes × c2hash ← hash XOR remainingByteshash ← hash XOR lenhash ← hash XOR (hash >> 16)hash ← hash × 0x85ebca6bhash ← hash XOR (hash >> 13)hash ← hash × 0xc2b2ae35hash ← hash XOR (hash >> 16)下面是一个示例C实现（对于小端CPU）

uint32_t murmur3_32(const uint8_t* key, size_t len, uint32_t seed) {uint32_t h = seed;if (len > 3) {const uint32_t* key_x4 = (const uint32_t*) key;size_t i = len >> 2;do {uint32_t k = *key_x4++;k *= 0xcc9e2d51;k = (k 17);k *= 0x1b873593;h ^= k;h = (h 19);h = (h * 5) + 0xe6546b64;} while (--i);key = (const uint8_t*) key_x4;}if (len & 3) {size_t i = len & 3;uint32_t k = 0;key = &key[i - 1];do {k 16;h *= 0x85ebca6b;h ^= h >> 13;h *= 0xc2b2ae35;h ^= h >> 16;return h;}本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学