查看“︁Murmur哈希”︁的源代码

{{noteTA
|G1=IT
}}
'''MurmurHash''' 是一种非[[加密]]型[[哈希函数]]，适用于一般的哈希检索操作。<ref name="Hadoop">{{cite web |url=http://hbase.apache.org/docs/current/api/org/apache/hadoop/hbase/util/MurmurHash.html |title=Hadoop in Java |publisher=Hbase.apache.org |date=24 July 2011 |accessdate=13 January 2012 |deadurl=yes |archiveurl=https://web.archive.org/web/20120112023407/http://hbase.apache.org/docs/current/api/org/apache/hadoop/hbase/util/MurmurHash.html |archivedate=2012年1月12日 }}</ref><ref>[http://laboratorios.fi.uba.ar/lsi/chouza-tesisingenieriainformatica.pdf Chouza et al] {{Wayback|url=http://laboratorios.fi.uba.ar/lsi/chouza-tesisingenieriainformatica.pdf |date=20120309075158 }}.</ref><ref>{{cite web |url=http://www.inesc-id.pt/ficheiros/publicacoes/5453.pdf |title=Couceiro et al. |format=PDF |language=pt |accessdate=13 January 2012 |archive-date=2015-09-24 |archive-url=https://web.archive.org/web/20150924034600/http://www.inesc-id.pt/ficheiros/publicacoes/5453.pdf |dead-url=no }}</ref>由Austin Appleby在2008年发明，<ref>{{cite web |url=http://murmurhash.googlepages.com/ |title=MurmurHash on GooglePages |publisher=Murmurhash.googlepages.com |accessdate=13 January 2012 |archive-date=2009-08-26 |archive-url=https://web.archive.org/web/20090826040009/http://murmurhash.googlepages.com/ |dead-url=no }}</ref><ref>{{cite web |author=Tanjent (tanjent) wrote,3 March 2008 13:31:00 |url=http://tanjent.livejournal.com/756623.html |title=MurmurHash first announcement |publisher=Tanjent.livejournal.com |accessdate=13 January 2012 |archive-date=2020-11-09 |archive-url=https://web.archive.org/web/20201109021506/https://tanjent.livejournal.com/756623.html |dead-url=no }}</ref> 并出现了多个变种，<ref name="Murmur160">{{cite web |url=http://simonhf.wordpress.com/2010/09/25/murmurhash160/ |title=MurmurHash2-160 |publisher=Simonhf.wordpress.com |date=25 September 2010 |accessdate=13 January 2012 |archive-date=2019-04-15 |archive-url=https://web.archive.org/web/20190415114414/https://simonhf.wordpress.com/2010/09/25/murmurhash160/ |dead-url=no }}</ref> 都已经发布到了[[公有领域]](public domain)。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。<ref name="StackExchange">{{cite web |url=http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed |publisher=stackexchange.com |title=Which hashing algorithm is best for uniqueness and speed |accessdate=2013-04-24 |archive-date=2016-07-05 |archive-url=https://web.archive.org/web/20160705171834/http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed |dead-url=no }}</ref>

== 变种 ==
当前的版本是MurmurHash3，<ref>{{cite web|title=MurmurHash3 on smhasher|url=http://code.google.com/p/smhasher/wiki/MurmurHash3|accessdate=2013-04-24|archive-date=2015-09-06|archive-url=https://web.archive.org/web/20150906104733/http://code.google.com/p/smhasher/wiki/MurmurHash3|dead-url=no}}</ref><ref name="Horvath">{{cite web | first = Adam | last = Horvath | url = http://blog.teamleadnet.com/2012/08/murmurhash3-ultra-fast-hash-algorithm.html | title = MurMurHash3, an ultra fast hash algorithm for C# / .NET | date = Aug 10, 2012 | accessdate = 2013-04-24 | archive-date = 2012-09-30 | archive-url = https://web.archive.org/web/20120930020314/http://blog.teamleadnet.com/2012/08/murmurhash3-ultra-fast-hash-algorithm.html | dead-url = no }}</ref> 能够产生出32-bit或128-bit哈希值。

较早的MurmurHash2<ref>{{cite web|title=MurmurHash2 on smhasher|url=http://code.google.com/p/smhasher/wiki/MurmurHash2|accessdate=2013-04-24|archive-date=2015-11-25|archive-url=https://web.archive.org/web/20151125120113/http://code.google.com/p/smhasher/wiki/MurmurHash2|dead-url=no}}</ref>能产生32-bit或64-bit哈希值。对于大端存储和强制对齐的硬件环境有一个较慢的MurmurHash2可以用。MurmurHash2A 变种增加了[[Merkle–Damgård 构造]]，所以能够以增量方式调用。 有两个变种产生64-bit哈希值：MurmurHash64A，为64位处理器做了优化；MurmurHash64B，为32位处理器做了优化。MurmurHash2-160用于产生160-bit 哈希值，而MurmurHash1已经不再使用。

== 实现 ==
最初的实现是[[C++]]的，但是被移植到了其他的流行语言上，包括 [[Python]],<ref>{{cite web |url=http://code.google.com/p/pyfasthash/ |title=pyfasthash in Python |publisher=Google |accessdate=13 January 2012 |archive-date=2015-03-21 |archive-url=https://web.archive.org/web/20150321222944/https://code.google.com/p/pyfasthash/ |dead-url=no }}</ref> [[C语言|C]],<ref>{{cite web |url=http://www.qdecoder.org/qlibc/ |title=C implementation in qLibc by Seungyoung Kim |deadurl=yes |archiveurl=https://archive.today/20130415181005/http://www.qdecoder.org/qlibc/ |archivedate=2013-04-15 |accessdate=2013-04-24 }}</ref> [[C♯|C#]],<ref name="Horvath"/><ref>{{cite web |last=Landman |first=Davy |url=http://landman-code.blogspot.com/2009/02/c-superfasthash-and-murmurhash2.html |title=Davy Landman in C# |publisher=Landman-code.blogspot.com |accessdate=13 January 2012 |archive-date=2020-05-07 |archive-url=https://web.archive.org/web/20200507105107/http://landman-code.blogspot.com/2009/02/c-superfasthash-and-murmurhash2.html |dead-url=no }}</ref> [[Perl]],<ref>{{cite web |url=http://search.cpan.org/~tmaesaka/Digest-MurmurHash-0.10/lib/Digest/MurmurHash.pm |title=Toru Maesaka in Perl |publisher=Search.cpan.org |accessdate=13 January 2012 |archive-date=2018-06-14 |archive-url=https://web.archive.org/web/20180614102415/http://search.cpan.org/~tmaesaka/Digest-MurmurHash-0.10/lib/Digest/MurmurHash.pm |dead-url=no }}</ref> [[Ruby]],<ref>{{cite web |author=Bruce Williams <http://codefluency.com>, for Ruby Central <http://rubycentral.org> |url=http://rubyforge.org/projects/murmurhash |title=Ruby |publisher=Rubyforge.org |date=3 May 2009 |accessdate=13 January 2012 |deadurl=yes |archiveurl=https://web.archive.org/web/20120223232810/http://rubyforge.org/projects/murmurhash |archivedate=2012年2月23日 }}</ref> [[PHP]],<ref>{{cite web |url=http://murmur.vaizard.org/en/ |title=Murmurhash3 PHP extension |publisher=Murmur.vaizard.org |accessdate=13 January 2012 |archive-date=2016-03-23 |archive-url=https://web.archive.org/web/20160323035928/http://murmur.vaizard.org/en/ |dead-url=no }}</ref> [[Haskell]],<ref>{{cite web |url=http://hackage.haskell.org/package/murmur-hash |title=Haskell |publisher=Hackage.haskell.org |accessdate=13 January 2012 |archive-date=2020-10-27 |archive-url=https://web.archive.org/web/20201027115507/http://hackage.haskell.org/package/murmur-hash |dead-url=no }}</ref>、[[Scala]]<ref>{{cite web|url=https://github.com/scala/scala/blob/master/src/library/scala/util/hashing/MurmurHash3.scala|title=Scala standard library implementation|date=14 December 2012}}{{dead link|date=2017年11月 |bot=InternetArchiveBot |fix-attempted=yes }}</ref>、[[Java]]<ref>[http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/hash/Hashing.html MurmurHash3 in Java] {{Wayback|url=http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/hash/Hashing.html |date=20120503050137 }}, part of Guava</ref><ref>[http://dmy999.com/article/50/murmurhash-2-java-port Derek Young in Java] {{Wayback|url=http://dmy999.com/article/50/murmurhash-2-java-port |date=20091003114850 }}, public domain</ref>和[[JavaScript]]<ref>{{cite web |author=raycmorgan (owner) |url=http://gist.github.com/588423 |title=Javascript implementation by Ray Morgan |publisher=Gist.github.com |accessdate=13 January 2012 |archive-date=2019-10-18 |archive-url=https://web.archive.org/web/20191018145719/https://gist.github.com/raycmorgan/588423 |dead-url=no }}</ref><ref>{{cite web |author=garycourt |url=http://github.com/garycourt/murmurhash-js |title=MurmurHash.js by Gary Court |publisher=Github.com |accessdate=13 January 2012 |archive-date=2020-11-26 |archive-url=https://web.archive.org/web/20201126083128/https://github.com/garycourt/murmurhash-js |dead-url=no }}</ref>等。

这个算法已经被若干开源计划所采纳，最重要的有libstdc++ (4.6版)、Perl<ref>{{cite web |url=http://search.cpan.org/~drolsky/perl-5.17.7/pod/perl5176delta.pod#New_hash_function_Murmurhash-32_%28v3%29 |title=perl5176delta |accessdate=31 December 2012 |archive-date=2018-05-24 |archive-url=https://web.archive.org/web/20180524110727/http://search.cpan.org/~drolsky/perl-5.17.7/pod/perl5176delta.pod#New_hash_function_Murmurhash-32_%28v3%29 |dead-url=no }}</ref>、[[nginx]] (不早于1.0.1版)<ref>{{cite web |url=http://nginx.org/en/CHANGES |title=nginx |accessdate=13 January 2012 |archive-date=2016-05-05 |archive-url=https://web.archive.org/web/20160505031534/http://nginx.org/en/CHANGES |dead-url=no }}</ref>、[[Rubinius]]<ref>{{cite web |url=https://github.com/rubinius/rubinius/commit/1d69526c484cc9435a7198e41b8995db6c3acf1a |title=Rubinius |accessdate=29 February 2012 |archive-date=2017-03-13 |archive-url=https://web.archive.org/web/20170313005441/https://github.com/rubinius/rubinius/commit/1d69526c484cc9435a7198e41b8995db6c3acf1a |dead-url=no }}</ref>、 libmemcached ([[Memcached]]的[[C语言]]客户端驱动)<ref>{{Cite web |url=http://libmemcached.org/libMemcached.html |title=libmemcached |accessdate=2013-04-24 |archive-date=2020-12-07 |archive-url=https://web.archive.org/web/20201207041820/https://libmemcached.org/libMemcached.html |dead-url=no }}</ref>、maatkit<ref>{{cite web |url=http://code.google.com/p/maatkit/source/detail?r=3273 |title=maatkit |publisher=Google |date=24 March 2009 |accessdate=13 January 2012 |archive-date=2015-09-30 |archive-url=https://web.archive.org/web/20150930081820/http://code.google.com/p/maatkit/source/detail?r=3273 |dead-url=no }}</ref>、[[Hadoop]]<ref name="Hadoop"/>、Kyoto Cabinet<ref>{{cite web |url=http://fallabs.com/kyotocabinet/spex.html |title=Kyoto Cabinet specification |publisher=Fallabs.com |date=4 March 2011 |accessdate=13 January 2012 |archive-date=2018-12-28 |archive-url=https://web.archive.org/web/20181228220357/https://fallabs.com/kyotocabinet/spex.html |dead-url=no }}</ref>以及[[RaptorDB]]<ref>{{cite web |last=Gholam |first=Mehdi |url=http://www.codeproject.com/KB/database/RaptorDB.aspx |title=RaptorDB CodeProject page |publisher=Codeproject.com |date=13 November 2011 |accessdate=13 January 2012 |archive-date=2011-12-30 |archive-url=https://web.archive.org/web/20111230012750/http://www.codeproject.com/KB/database/RaptorDB.aspx |dead-url=no }}</ref>。

== 算法 ==

 Murmur3_32(''key'', ''len'', ''seed'')
     ''c1'' <math>\gets</math> 0xcc9e2d51
     ''c2'' <math>\gets</math> 0x1b873593
     ''r1'' <math>\gets</math> 15
     ''r2'' <math>\gets</math> 13
     ''m'' <math>\gets</math> 5
     ''n'' <math>\gets</math> 0xe6546b64
  
     ''hash'' <math>\gets</math> seed
 
     for each fourByteChunk of key
         k <math>\gets</math> fourByteChunk
 
         k <math>\gets</math> k * c1
         k <math>\gets</math> (k << r1) '''OR''' (k >> (32-r1))
         k <math>\gets</math> k * c2
 
         hash <math>\gets</math> hash '''XOR''' k
         hash <math>\gets</math> (hash << r2) '''OR''' (hash >> (32-r2))
         hash <math>\gets</math> hash * m + n
 
     with any remainingBytesInKey
         remainingBytes <math>\gets</math> SwapEndianOrderOf(remainingBytesInKey)
         remainingBytes <math>\gets</math> remainingBytes * c1
         remainingBytes <math>\gets</math> (remainingBytes << r1) '''OR''' (remainingBytes >> (32 - r1))
         remainingBytes <math>\gets</math> remainingBytes * c2
 
         hash <math>\gets</math> hash '''XOR''' remainingBytes
  
     hash <math>\gets</math> hash '''XOR''' len
 
     hash <math>\gets</math> hash '''XOR''' (hash >> 16)
     hash <math>\gets</math> hash * 0x85ebca6b
     hash <math>\gets</math> hash '''XOR''' (hash >> 13)
     hash <math>\gets</math> hash * 0xc2b2ae35
     hash <math>\gets</math> hash '''XOR''' (hash >> 16)

== 参考 ==
{{reflist|colwidth=30em}}

[[Category:散列函数]]
[[Category:带有伪代码示例的条目]]