Murmur哈希是一種非加密散列函式，適用於一般的基於散列的查找。它在2008年由Austin Appleby創建，在Github上託管，名為“SMHasher” 的測試套件。 它也存在許多變種，所有這些變種都已經被公開。 該名稱來自兩個基本操作，乘法（MU）和旋轉（R），在其內部循環中使用。
與加密散列函式不同，它不是專門設計為難以被對手逆轉，因此不適用於加密目的。
基本介紹
- 中文名：Murmur哈希
- 外文名：Murmur Hash
- 本質：非加密散列函式
種類,Murmur哈希3,Murmur哈希2,實現,漏洞,算法,
種類
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 ← 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 << 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;}