Murmur哈希

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 ${\displaystyle \gets }$  0xcc9e2d51 c2 ${\displaystyle \gets }$  0x1b873593 r1 ${\displaystyle \gets }$  15 r2 ${\displaystyle \gets }$  13 m ${\displaystyle \gets }$  5 n ${\displaystyle \gets }$  0xe6546b64 hash ${\displaystyle \gets }$  seed for each fourByteChunk of key k ${\displaystyle \gets }$  fourByteChunk k ${\displaystyle \gets }$  k * c1 k ${\displaystyle \gets }$  (k << r1) OR (k >> (32-r1)) k ${\displaystyle \gets }$  k * c2 hash ${\displaystyle \gets }$  hash XOR k hash ${\displaystyle \gets }$  (hash << r2) OR (hash >> (32-r2)) hash ${\displaystyle \gets }$  hash * m + n with any remainingBytesInKey remainingBytes ${\displaystyle \gets }$  SwapEndianOrderOf(remainingBytesInKey) remainingBytes ${\displaystyle \gets }$  remainingBytes * c1 remainingBytes ${\displaystyle \gets }$  (remainingBytes << r1) OR (remainingBytes >> (32 - r1)) remainingBytes ${\displaystyle \gets }$  remainingBytes * c2 hash ${\displaystyle \gets }$  hash XOR remainingBytes hash ${\displaystyle \gets }$  hash XOR len hash ${\displaystyle \gets }$  hash XOR (hash >> 16) hash ${\displaystyle \gets }$  hash * 0x85ebca6b hash ${\displaystyle \gets }$  hash XOR (hash >> 13) hash ${\displaystyle \gets }$  hash * 0xc2b2ae35 hash ${\displaystyle \gets }$  hash XOR (hash >> 16) 

参考

1. . Hbase.apache.org. 24 July 2011 [13 January 2012]. （原始内容存档于2012年1月12日）. 
2. Chouza et al （页面存档备份，存于互联网档案馆）.
3. Couceiro et al. (PDF). [13 January 2012]. （原始内容 (PDF)于2015-09-24） （葡萄牙语）. 
4. MurmurHash on GooglePages. Murmurhash.googlepages.com. [13 January 2012]. （原始内容于2009-08-26）. 
5. Tanjent (tanjent) wrote,3 March 2008 13:31:00. MurmurHash first announcement. Tanjent.livejournal.com. [13 January 2012]. （原始内容于2020-11-09）. 
6. MurmurHash2-160. Simonhf.wordpress.com. 25 September 2010 [13 January 2012]. （原始内容于2019-04-15）. 
7. Which hashing algorithm is best for uniqueness and speed. stackexchange.com. [2013-04-24]. （原始内容于2016-07-05）. 
8. MurmurHash3 on smhasher. [2013-04-24]. （原始内容于2015-09-06）. 
9. Horvath, Adam. MurMurHash3, an ultra fast hash algorithm for C# / .NET. Aug 10, 2012 [2013-04-24]. （原始内容于2012-09-30）. 
10. MurmurHash2 on smhasher. [2013-04-24]. （原始内容于2015-11-25）. 
11. pyfasthash in Python. Google. [13 January 2012]. （原始内容于2015-03-21）. 
12. C implementation in qLibc by Seungyoung Kim. [2013-04-24]. （原始内容存档于2013-04-15）. 
13. Landman, Davy. Davy Landman in C#. Landman-code.blogspot.com. [13 January 2012]. （原始内容于2020-05-07）. 
14. Toru Maesaka in Perl. Search.cpan.org. [13 January 2012]. （原始内容于2018-06-14）. 
15. Bruce Williams <http://codefluency.com>, for Ruby Central <http://rubycentral.org>. . Rubyforge.org. 3 May 2009 [13 January 2012]. （原始内容存档于2012年2月23日）. 
16. Murmurhash3 PHP extension. Murmur.vaizard.org. [13 January 2012]. （原始内容于2016-03-23）. 
17. Haskell. Hackage.haskell.org. [13 January 2012]. （原始内容于2020-10-27）. 
18. Scala standard library implementation. 14 December 2012. ^{[永久失效連結]}
19. MurmurHash3 in Java （页面存档备份，存于互联网档案馆）, part of Guava
20. Derek Young in Java （页面存档备份，存于互联网档案馆）, public domain
21. raycmorgan (owner). Javascript implementation by Ray Morgan. Gist.github.com. [13 January 2012]. （原始内容于2019-10-18）. 
22. garycourt. MurmurHash.js by Gary Court. Github.com. [13 January 2012]. （原始内容于2020-11-26）. 
23. perl5176delta. [31 December 2012]. （原始内容于2018-05-24）. 
24. nginx. [13 January 2012]. （原始内容于2016-05-05）. 
25. Rubinius. [29 February 2012]. （原始内容于2017-03-13）. 
26. libmemcached. [2013-04-24]. （原始内容于2020-12-07）. 
27. maatkit. Google. 24 March 2009 [13 January 2012]. （原始内容于2015-09-30）. 
28. Kyoto Cabinet specification. Fallabs.com. 4 March 2011 [13 January 2012]. （原始内容于2018-12-28）. 
29. Gholam, Mehdi. RaptorDB CodeProject page. Codeproject.com. 13 November 2011 [13 January 2012]. （原始内容于2011-12-30）.