MurmurHash

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 208.84.140.10 (talk) at 01:34, 17 April 2012 (→‎Implementations). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.

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.

Implementations

The canonical implementations are in C++, but there are efficient ports for a variety of popular languages, including Python,[9],C,[10],C#,[11] Perl,[12] Ruby,[13] PHP,[14] Haskell,[15] Java,[16][17] and JavaScript.[18][19]

It has been adopted into a number of open-source projects, most notably libstdc++ (ver 4.6), nginx (ver 1.0.1)[20], Rubinius[21], libmemcached[22] (the C driver for Memcached), maatkit,[23] Hadoop.[1], Kyoto Cabinet,[24] RaptorDB[25] and Scala.[26]

References

  1. ^ a b "Hadoop in Java". Hbase.apache.org. 24 July 2011. Retrieved 13 January 2012.
  2. ^ Chouza et al.
  3. ^ "Couceiro et al" (PDF) (in Template:Pt icon). Retrieved 13 January 2012.{{cite web}}: CS1 maint: unrecognized language (link)
  4. ^ "MurmurHash on GooglePages". Murmurhash.googlepages.com. Retrieved 13 January 2012.
  5. ^ Tanjent (tanjent) wrote,3 March 2008 13:31:00. "MurmurHash first announcement". Tanjent.livejournal.com. Retrieved 13 January 2012.{{cite web}}: CS1 maint: numeric names: authors list (link)
  6. ^ "MurmurHash2-160". Simonhf.wordpress.com. 25 September 2010. Retrieved 13 January 2012.
  7. ^ "MurmurHash3 on smhasher".
  8. ^ "MurmurHash2 on smhasher".
  9. ^ "pyfasthash in Python". Google. Retrieved 13 January 2012.
  10. ^ "C implementation in qLibc by Seungyoung Kim".
  11. ^ Landman, Davy. "Davy Landman in C#". Landman-code.blogspot.com. Retrieved 13 January 2012.
  12. ^ "Toru Maesaka in Perl". Search.cpan.org. Retrieved 13 January 2012.
  13. ^ Bruce Williams <http://codefluency.com>, for Ruby Central <http://rubycentral.org> (3 May 2009). "Ruby". Rubyforge.org. Retrieved 13 January 2012.
  14. ^ "Murmurhash3 PHP extension". Murmur.vaizard.org. Retrieved 13 January 2012.
  15. ^ "Haskell". Hackage.haskell.org. Retrieved 13 January 2012.
  16. ^ MurmurHash3 in Java, part of Guava
  17. ^ Derek Young in Java, public domain
  18. ^ raycmorgan (owner). "Javascript implementation by Ray Morgan". Gist.github.com. Retrieved 13 January 2012.
  19. ^ garycourt. "MurmurHash.js by Gary Court". Github.com. Retrieved 13 January 2012.
  20. ^ "nginx". Retrieved 13 January 2012.
  21. ^ "Rubinius". Retrieved 29 February 2012.
  22. ^ libmemcached
  23. ^ "maatkit". Google. 24 March 2009. Retrieved 13 January 2012.
  24. ^ "Kyoto Cabinet specification". Fallabs.com. 4 March 2011. Retrieved 13 January 2012.
  25. ^ Gholam, Mehdi (13 November 2011). "RaptorDB CodeProject page". Codeproject.com. Retrieved 13 January 2012.
  26. ^ Scala compiler implementation[dead link]

See also

Retrieved from "https://en.wikipedia.org/w/index.php?title=MurmurHash&oldid=487765109"