MurmurHash
MurmurHash is a non-cryptographic hash function suitable for general hash-based lookup.[1][2][3] It was created by Austin Appleby in 2008,[4][5] and exists in a number of variants,[6] all of which have been released into the public domain.
Contents |
[edit] Variants
The current version is MurmurHash3[7], which yields a 32-bit or 128-bit hash value and is optimized for Intel processors.
The older MurmurHash2[8] yields a 32-bit or 64-bit value. Slower versions of MurmurHash2 are available for big-endian and aligned-only machines. The MurmurHash2A variant adds the Merkle-Damgard construction so that it can be called incrementally. There are two variants which generate 64-bit values; MurmurHash64A, which is optimized for 64-bit processors, and MurmurHash64B, for 32-bit ones. MurmurHash2-160 generates the 160-bit hash, and MurmurHash1 is obsolete.
[edit] Implementations
The canonical implementations are in C++, but there are efficient ports for a variety of popular languages, including Python,[9] C#,[10] Perl,[11] Ruby,[12] PHP,[13] Haskell,[14] Java,[15][16] and JavaScript.[17][18]
It has been adopted into a number of open-source projects, most notably libstdc++ (ver 4.6), nginx (ver 1.0.1),[19] libmemcached[20] (the C driver for Memcached), maatkit,[21] Hadoop.[1], Kyoto Cabinet,[22] RaptorDB[23] and Scala.[24]
[edit] References
- ^ a b "Hadoop in Java". Hbase.apache.org. 24 July 2011. http://hbase.apache.org/docs/current/api/org/apache/hadoop/hbase/util/MurmurHash.html. Retrieved 13 January 2012.
- ^ Chouza et al.
- ^ "Couceiro et al." (in (Portuguese)) (PDF). http://www.inesc-id.pt/ficheiros/publicacoes/5453.pdf. Retrieved 13 January 2012.
- ^ "MurmurHash on GooglePages". Murmurhash.googlepages.com. http://murmurhash.googlepages.com/. Retrieved 13 January 2012.
- ^ Tanjent (tanjent) wrote,3 March 2008 13:31:00. "MurmurHash first announcement". Tanjent.livejournal.com. http://tanjent.livejournal.com/756623.html. Retrieved 13 January 2012.
- ^ "MurmurHash2-160". Simonhf.wordpress.com. 25 September 2010. http://simonhf.wordpress.com/2010/09/25/murmurhash160/. Retrieved 13 January 2012.
- ^ "MurmurHash3 on smhasher". http://code.google.com/p/smhasher/wiki/MurmurHash3.
- ^ "MurmurHash2 on smhasher". http://code.google.com/p/smhasher/wiki/MurmurHash2.
- ^ "pyfasthash in Python". Google. http://code.google.com/p/pyfasthash/. Retrieved 13 January 2012.
- ^ Landman, Davy. "Davy Landman in C#". Landman-code.blogspot.com. http://landman-code.blogspot.com/2009/02/c-superfasthash-and-murmurhash2.html. Retrieved 13 January 2012.
- ^ "Toru Maesaka in Perl". Search.cpan.org. http://search.cpan.org/~tmaesaka/Digest-MurmurHash-0.10/lib/Digest/MurmurHash.pm. Retrieved 13 January 2012.
- ^ Bruce Williams <http://codefluency.com>, for Ruby Central <http://rubycentral.org> (3 May 2009). "Ruby". Rubyforge.org. http://rubyforge.org/projects/murmurhash. Retrieved 13 January 2012.
- ^ "Murmurhash3 PHP extension". Murmur.vaizard.org. http://murmur.vaizard.org/en/. Retrieved 13 January 2012.
- ^ "Haskell". Hackage.haskell.org. http://hackage.haskell.org/package/murmur-hash. Retrieved 13 January 2012.
- ^ MurmurHash3 in Java, part of Guava
- ^ Derek Young in Java, public domain
- ^ raycmorgan (owner). "Javascript implementation by Ray Morgan". Gist.github.com. http://gist.github.com/588423. Retrieved 13 January 2012.
- ^ garycourt. "MurmurHash.js by Gary Court". Github.com. http://github.com/garycourt/murmurhash-js. Retrieved 13 January 2012.
- ^ "nginx". http://nginx.org/en/CHANGES. Retrieved 13 January 2012.
- ^ libmemcached
- ^ "maatkit". Google. 24 March 2009. http://code.google.com/p/maatkit/source/detail?r=3273. Retrieved 13 January 2012.
- ^ "Kyoto Cabinet specification". Fallabs.com. 4 March 2011. http://fallabs.com/kyotocabinet/spex.html. Retrieved 13 January 2012.
- ^ Gholam, Mehdi (13 November 2011). "RaptorDB CodeProject page". Codeproject.com. http://www.codeproject.com/KB/database/RaptorDB.aspx. Retrieved 13 January 2012.
- ^ Scala compiler implementation[dead link]
