Murmur哈希

Murmur哈希是一種非加密散列函式,適用於一般的基於散列的查找。它在2008年由Austin Appleby創建,在Github上託管,名為“SMHasher” 的測試套件。 它也存在許多變種,所有這些變種都已經被公開。 該名稱來自兩個基本操作,乘法(MU)和旋轉(R),在其內部循環中使用。 與加密散列函式不同,它不是專門設計為難以被對手逆轉,因此不適用於加密目的。

種類

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代替。

算法

下面是一個示例C實現(對於小端CPU)

相關詞條

相關搜尋

熱門詞條

聯絡我們