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] and, as of 8 January 2016,[5] is hosted on GitHub along with its test suite named SMHasher. It also exists in a number of variants,[6] all of which have been released into the public domain. The name comes from two basic operations, multiply (MU) and rotate (R), used in its inner loop.
Unlike cryptographic hash functions, it is not specifically designed to be difficult to reverse by an adversary, making it unsuitable for cryptographic purposes.
Variants
MurmurHash1
The original MurmurHash was created as an attempt to make a faster function than Lookup3.[7] Although successful, it had not been tested thoroughly and was not capable of providing 64-bit hashes as in Lookup3. Its design would be later built upon in MurmurHash2, combining a multiplicative hash (similar to the Fowler–Noll–Vo hash function) with an Xorshift.
MurmurHash2
MurmurHash2[8] yields a 32- or 64-bit value. It comes in multiple variants, including some that allow incremental hashing and aligned or neutral versions.
- MurmurHash2 (32-bit, x86)—The original version; contains a flaw that weakens collision in some cases.[9]
- MurmurHash2A (32-bit, x86)—A fixed variant using Merkle–Damgård construction. Slightly slower.
- CMurmurHash2A (32-bit, x86)—MurmurHash2A, but works incrementally.
- MurmurHashNeutral2 (32-bit, x86)—Slower, but endian- and alignment-neutral.
- MurmurHashAligned2 (32-bit, x86)—Slower, but does aligned reads (safer on some platforms).
- MurmurHash64A (64-bit, x64)—The original 64-bit version. Optimized for 64-bit arithmetic.
- MurmurHash64B (64-bit, x86)—A 64-bit version optimized for 32-bit platforms. It is not a true 64-bit hash due to insufficient mixing of the stripes.[10]
The person who originally found the flaw[clarification needed] in MurmurHash2 created an unofficial 160-bit version of MurmurHash2 called MurmurHash2_160.[11]
MurmurHash3
The current version, completed April 3, 2011, is MurmurHash3,[12][13] which yields a 32-bit or 128-bit hash value. When using 128-bits, the x86 and x64 versions do not produce the same values, as the algorithms are optimized for their respective platforms. MurmurHash3 was released alongside SMHasher, a hash function test suite.
Implementations
The canonical implementation is in C++, but there are efficient ports for a variety of popular languages, including Python,[14] C,[15] Go,[16] C#,[13][17] D,[18] Lua, Perl,[19] Ruby,[20] Rust,[21] PHP,[22][23] Common Lisp,[24] Haskell,[25] Elm,[26] Clojure,[27] Scala,[28] Java,[29][30] Erlang,[31] Swift,[32] Object Pascal,[33] Kotlin,[34] JavaScript,[35] and OCaml.[36]
It has been adopted into a number of open-source projects, most notably libstdc++ (ver 4.6), nginx (ver 1.0.1),[37] Rubinius,[38] libmemcached (the C driver for Memcached),[39] npm (nodejs package manager),[40] maatkit,[41] Hadoop,[1] Kyoto Cabinet,[42] Cassandra,[43][44] Solr,[45] vowpal wabbit,[46] Elasticsearch,[47] Guava,[48] Kafka,[49] and RedHat Virtual Data Optimizer (VDO).[50]
Vulnerabilities
Hash functions can be vulnerable to collision attacks, where a user can choose input data in such a way so as to intentionally cause hash collisions. Jean-Philippe Aumasson and Daniel J. Bernstein were able to show that even implementations of MurmurHash using a randomized seed are vulnerable to so-called HashDoS attacks.[51] With the use of differential cryptanalysis, they were able to generate inputs that would lead to a hash collision. The authors of the attack recommend using their own SipHash instead.
Algorithm
algorithm Murmur3_32 is
// Note: In this version, all arithmetic is performed with unsigned 32-bit integers.
// In the case of overflow, the result is reduced modulo 232.
input: key, len, seed
c1 ← 0xcc9e2d51
c2 ← 0x1b873593
r1 ← 15
r2 ← 13
m ← 5
n ← 0xe6546b64
hash ← seed
for each fourByteChunk of key do
k ← fourByteChunk
k ← k × c1
k ← k ROL r1
k ← k × c2
hash ← hash XOR k
hash ← hash ROL r2
hash ← (hash × m) + n
with any remainingBytesInKey do
remainingBytes ← SwapToLittleEndian(remainingBytesInKey)
// Note: Endian swapping is only necessary on big-endian machines.
// The purpose is to place the meaningful digits towards the low end of the value,
// so that these digits have the greatest potential to affect the low range digits
// in the subsequent multiplication. Consider that locating the meaningful digits
// in the high range would produce a greater effect upon the high digits of the
// multiplication, and notably, that such high digits are likely to be discarded
// by the modulo arithmetic under overflow. We don't want that.
remainingBytes ← remainingBytes × c1
remainingBytes ← remainingBytes ROL r1
remainingBytes ← remainingBytes × c2
hash ← hash XOR remainingBytes
hash ← hash XOR len
hash ← hash XOR (hash >> 16)
hash ← hash × 0x85ebca6b
hash ← hash XOR (hash >> 13)
hash ← hash × 0xc2b2ae35
hash ← hash XOR (hash >> 16)
A sample C implementation follows (for little-endian CPUs):
static inline uint32_t murmur_32_scramble(uint32_t k) {
k *= 0xcc9e2d51;
k = (k << 15) | (k >> 17);
k *= 0x1b873593;
return k;
}
uint32_t murmur3_32(const uint8_t* key, size_t len, uint32_t seed)
{
uint32_t h = seed;
uint32_t k;
/* Read in groups of 4. */
for (size_t i = len >> 2; i; i--) {
// Here is a source of differing results across endiannesses.
// A swap here has no effects on hash properties though.
memcpy(&k, key, sizeof(uint32_t));
key += sizeof(uint32_t);
h ^= murmur_32_scramble(k);
h = (h << 13) | (h >> 19);
h = h * 5 + 0xe6546b64;
}
/* Read the rest. */
k = 0;
for (size_t i = len & 3; i; i--) {
k <<= 8;
k |= key[i - 1];
}
// A swap is *not* necessary here because the preceding loop already
// places the low bytes in the low places according to whatever endianness
// we use. Swaps only apply when the memory is copied in a chunk.
h ^= murmur_32_scramble(k);
/* Finalize. */
h ^= len;
h ^= h >> 16;
h *= 0x85ebca6b;
h ^= h >> 13;
h *= 0xc2b2ae35;
h ^= h >> 16;
return h;
}
| Test string | Seed value | Hash value (hexadecimal) | Hash value (decimal) |
|---|---|---|---|
0x00000000 |
0x00000000 |
0 | |
0x00000001 |
0x514E28B7 |
1,364,076,727 | |
0xffffffff |
0x81F16F39 |
2,180,083,513 | |
| test | 0x00000000 |
0xba6bd213 |
3,127,628,307 |
| test | 0x9747b28c |
0x704b81dc |
1,883,996,636 |
| Hello, world! | 0x00000000 |
0xc0363e43 |
3,224,780,355 |
| Hello, world! | 0x9747b28c |
0x24884CBA |
612,912,314 |
| The quick brown fox jumps over the lazy dog | 0x00000000 |
0x2e4ff723 |
776,992,547 |
| The quick brown fox jumps over the lazy dog | 0x9747b28c |
0x2FA826CD |
799,549,133 |
See also
References
External links
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
