Murmur雜湊
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
MurmurHash 是一種非加密型雜湊函數,適用於一般的雜湊檢索操作。[1][2][3]由Austin Appleby在2008年發明,[4][5] 並出現了多個變種,[6] 都已經發佈到了公有領域(public domain)。與其它流行的雜湊函數相比,對於規律性較強的key,MurmurHash的隨機分佈特徵表現更良好。[7]
變種
當前的版本是MurmurHash3,[8][9] 能夠產生出32-bit或128-bit雜湊值。
較早的MurmurHash2[10]能產生32-bit或64-bit雜湊值。對於大端儲存和強制對齊的硬件環境有一個較慢的MurmurHash2可以用。MurmurHash2A 變種增加了Merkle–Damgård 構造,所以能夠以增量方式呼叫。 有兩個變種產生64-bit雜湊值:MurmurHash64A,為64位元處理器做了最佳化;MurmurHash64B,為32位元處理器做了最佳化。MurmurHash2-160用於產生160-bit 雜湊值,而MurmurHash1已經不再使用。
實現
最初的實現是C++的,但是被移植到了其他的流行語言上,包括 Python,[11] C,[12] C#,[9][13] Perl,[14] Ruby,[15] PHP,[16] Haskell,[17]、Scala[18]、Java[19][20]和JavaScript[21][22]等。
這個演算法已經被若干開源計劃所採納,最重要的有libstdc++ (4.6版)、Perl[23]、nginx (不早於1.0.1版)[24]、Rubinius[25]、 libmemcached (Memcached的C語言客戶端驅動)[26]、maatkit[27]、Hadoop[1]、Kyoto Cabinet[28]以及RaptorDB[29]。
演算法
Murmur3_32(key, len, seed) 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 << r1) OR (k >> (32-r1)) k k * c2 hash hash XOR k hash (hash << r2) OR (hash >> (32-r2)) hash hash * m + n with any remainingBytesInKey remainingBytes SwapEndianOrderOf(remainingBytesInKey) remainingBytes remainingBytes * c1 remainingBytes (remainingBytes << r1) OR (remainingBytes >> (32 - 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)
參考
- ^ 1.0 1.1 Hadoop in Java. Hbase.apache.org. 24 July 2011 [13 January 2012]. (原始內容存檔於2012年1月12日).
- ^ Chouza et al (頁面存檔備份,存於互聯網檔案館).
- ^ Couceiro et al. (PDF). [13 January 2012]. (原始內容存檔 (PDF)於2015-09-24) (葡萄牙語).
- ^ MurmurHash on GooglePages. Murmurhash.googlepages.com. [13 January 2012]. (原始內容存檔於2009-08-26).
- ^ Tanjent (tanjent) wrote,3 March 2008 13:31:00. MurmurHash first announcement. Tanjent.livejournal.com. [13 January 2012]. (原始內容存檔於2020-11-09).
- ^ MurmurHash2-160. Simonhf.wordpress.com. 25 September 2010 [13 January 2012]. (原始內容存檔於2019-04-15).
- ^ Which hashing algorithm is best for uniqueness and speed. stackexchange.com. [2013-04-24]. (原始內容存檔於2016-07-05).
- ^ MurmurHash3 on smhasher. [2013-04-24]. (原始內容存檔於2015-09-06).
- ^ 9.0 9.1 Horvath, Adam. MurMurHash3, an ultra fast hash algorithm for C# / .NET. Aug 10, 2012 [2013-04-24]. (原始內容存檔於2012-09-30).
- ^ MurmurHash2 on smhasher. [2013-04-24]. (原始內容存檔於2015-11-25).
- ^ pyfasthash in Python. Google. [13 January 2012]. (原始內容存檔於2015-03-21).
- ^ C implementation in qLibc by Seungyoung Kim. [2013-04-24]. (原始內容存檔於2013-04-15).
- ^ Landman, Davy. Davy Landman in C#. Landman-code.blogspot.com. [13 January 2012]. (原始內容存檔於2020-05-07).
- ^ Toru Maesaka in Perl. Search.cpan.org. [13 January 2012]. (原始內容存檔於2018-06-14).
- ^ Bruce Williams <http://codefluency.com>, for Ruby Central <http://rubycentral.org>. Ruby. Rubyforge.org. 3 May 2009 [13 January 2012]. (原始內容存檔於2012年2月23日).
- ^ Murmurhash3 PHP extension. Murmur.vaizard.org. [13 January 2012]. (原始內容存檔於2016-03-23).
- ^ Haskell. Hackage.haskell.org. [13 January 2012]. (原始內容存檔於2020-10-27).
- ^ Scala standard library implementation. 14 December 2012.[永久失效連結]
- ^ MurmurHash3 in Java (頁面存檔備份,存於互聯網檔案館), part of Guava
- ^ Derek Young in Java (頁面存檔備份,存於互聯網檔案館), public domain
- ^ raycmorgan (owner). Javascript implementation by Ray Morgan. Gist.github.com. [13 January 2012]. (原始內容存檔於2019-10-18).
- ^ garycourt. MurmurHash.js by Gary Court. Github.com. [13 January 2012]. (原始內容存檔於2020-11-26).
- ^ perl5176delta. [31 December 2012]. (原始內容存檔於2018-05-24).
- ^ nginx. [13 January 2012]. (原始內容存檔於2016-05-05).
- ^ Rubinius. [29 February 2012]. (原始內容存檔於2017-03-13).
- ^ libmemcached. [2013-04-24]. (原始內容存檔於2020-12-07).
- ^ maatkit. Google. 24 March 2009 [13 January 2012]. (原始內容存檔於2015-09-30).
- ^ Kyoto Cabinet specification. Fallabs.com. 4 March 2011 [13 January 2012]. (原始內容存檔於2018-12-28).
- ^ Gholam, Mehdi. RaptorDB CodeProject page. Codeproject.com. 13 November 2011 [13 January 2012]. (原始內容存檔於2011-12-30).