MurmurHash

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^[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]

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.

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][22] PHP,^[23][24] Common Lisp,^[25] Haskell,^[26] Elm,^[27] Clojure,^[28] Scala,^[29] Java,^[30][31][32] Erlang,^[33] Swift,^[34] Object Pascal,^[35] Kotlin,^[36] JavaScript,^[37] OCaml^[38] and Microsoft Excel.^[39]

It has been adopted into a number of open-source projects, most notably libstdc++ (ver 4.6), nginx (ver 1.0.1),^[40] Rubinius,^[41] libmemcached (the C driver for Memcached),^[42] npm (nodejs package manager),^[43] maatkit,^[44] Hadoop,^[1] Kyoto Cabinet,^[45] Cassandra,^[46][47] Solr,^[48] vowpal wabbit,^[49] Elasticsearch,^[50] Guava,^[51] Kafka,^[52] and RedHat Virtual Data Optimizer (VDO).^[53]

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.^[54] 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 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;
}

• Non-cryptographic hash functions