Murmur哈希

MurmurHash 是一种非加密哈希函数，适用于一般的哈希检索操作。[1][2][3]由Austin Appleby在2008年发明，[4][5] 并出现了多个变种，[6] 都已经发布到了公有领域(public domain)。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。[7]

算法

```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. Hadoop in Java. 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） （葡萄牙语）.
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>. Ruby. Rubyforge.org. 3 May 2009 [13 January 2012]. （原始内容存档于2012年2月23日）.
16. ^ Murmurhash3 PHP extension. Murmur.vaizard.org. [13 January 2012]. （原始内容存档于2016-03-23）.