Murmur哈希是一種非加密散列函式，適用於一般的基於散列的查找。它在2008年由Austin Appleby創建，在Github上託管，名為“SMHasher” 的測試套件。 它也存在許多變種，所有這些變種都已經被公開。 該名稱來自兩個基本操作，乘法（MU）和旋轉（R），在其內部循環中使用。
與加密散列函式不同，它不是專門設計為難以被對手逆轉，因此不適用於加密目的。
基本介紹
- 中文名：Murmur哈希
- 外文名：Murmur Hash
- 本質：非加密散列函式
種類,實現,漏洞,算法,
種類
Murmur哈希3
2018年的版本是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）。
漏洞
如果用戶可以選擇輸入數據以有意造成散列衝突，則散列函式容易受到攻擊。 Jean-Philippe Aumasson和Daniel J. Bernstein能夠證明，即使使用隨機化種子實施Murmur哈希也容易受到所謂的HashDoS攻擊。 通過使用差分密碼分析，他們能夠生成會導致哈希碰撞的輸入。 攻擊的作者建議使用他們自己的SipHash代替。
算法
Murmur3_32(key, len, seed)
//注意：在這個版本中，所有的整數算術運算都是無符號的32位整數。
//在溢出的情況下，結果受模數套用的限制
c1 ← 0xcc9e2d51
c2 ← 0x1b873593
r1 ← 15
r2 ← 13
m ← 5
n ← 0xe6546b64
hash ← seed
for each fourByteChunk of key
k ← fourByteChunk
k ← k × c1
k ← (k ROL r1)
k ← k × c2
hash ← hash XOR k
hash ← (hash ROL r2)
hash ← hash × m + n
with any remainingBytesInKey
remainingBytes ← SwapToLittleEndian(remainingBytesInKey)
//注意：只有在big-endian機器上才需要Endian交換。
//目的是將有意義的數字放在值的低端，
//這些數字最有可能影響低範圍數字
//在隨後的乘法中。 考慮定位有意義的數字
//在高頻範圍內會對高位數產生更大的影響
//乘法，特別是，這樣的高位數可能會被丟棄
//通過溢出下的模運算。 我們不希望這樣。
remainingBytes ← remainingBytes × c1
remainingBytes ← (remainingBytes ROL r1)
remainingBytes ← remainingBytes × c2
hash ← hash XOR remainingBytes
hash ← hash XOR len
hash ← hash XOR (hash >> 16)
hash ← hash × 0x85ebca6b
hash ← hash XOR (hash >> 13)
hash ← hash × 0xc2b2ae35
hash ← 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 << 15) | (k >> 17);
k *= 0x1b873593;
h ^= k;
h = (h << 13) | (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 <<= 8;
k |= *key--;
} while (--i);
k *= 0xcc9e2d51;
k = (k << 15) | (k >> 17);
k *= 0x1b873593;
h ^= k; }
h ^= len;
h ^= h >> 16;
h *= 0x85ebca6b;
h ^= h >> 13;
h *= 0xc2b2ae35;
h ^= h >> 16;
return h;
}
