Module fasthash::murmur2 [] [src]

Murmur2, a suite of non-cryptographic hash functions that was used for hash-based lookups.

by Austin Appleby (aappleby (AT) gmail)

https://sites.google.com/site/murmurhash/

Extremely simple - compiles down to ~52 instructions on x86.

Excellent distribution - Passes chi-squared tests for practically all keysets & bucket sizes.

Excellent avalanche behavior - Maximum bias is under 0.5%.

Excellent collision resistance - Passes Bob Jenkin's frog.c torture-test. No collisions possible for 4-byte keys, no small (1- to 7-bit) differentials.

Excellent performance - measured on an Intel Core 2 Duo @ 2.4 ghz

Variants

The current version is MurmurHash3, which yields a 32-bit or 128-bit hash value.

The older MurmurHash2 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–Damgård 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.

Attacks

MurmurHash was a recommended hash function for hash table implementations. Jean-Philippe Aumasson and Daniel J. Bernstein were able to show that even randomized implementations of MurmurHash are vulnerable to so-called HashDoS attacks. With the use of differential cryptanalysis they were able to generate inputs that would lead to a hash collision. This can be abused to cause very slow operations of a hash table implementation. The authors of the attack recommend to use SipHash instead.

Example

use std::hash::{Hash, Hasher};

use fasthash::{murmur2, Murmur2Hasher};

fn hash<T: Hash>(t: &T) -> u64 {
    let mut s: Murmur2Hasher = Default::default();
    t.hash(&mut s);
    s.finish()
}

let h = murmur2::hash64(b"hello world\xff");

assert_eq!(h, hash(&"hello world"));

Structs

Murmur2

MurmurHash2 32-bit hash functions

Murmur2A

MurmurHash2A 32-bit hash functions

Murmur2AHasher

An implementation of std::hash::Hasher.

Murmur2Hasher

An implementation of std::hash::Hasher.

Murmur2Hasher_x64_64

An implementation of std::hash::Hasher.

Murmur2Hasher_x86_64

An implementation of std::hash::Hasher.

Murmur2_x64_64

MurmurHash2 64-bit hash functions for 64-bit processors

Murmur2_x86_64

MurmurHash2 64-bit hash functions for 32-bit processors

MurmurAligned2

MurmurHash2 32-bit aligned hash functions for the little-endian aligned-read-only implementation

MurmurAligned2Hasher

An implementation of std::hash::Hasher.

MurmurNeutral2

MurmurHash2 32-bit neutral hash functions for the (slower) endian-neutral implementation

MurmurNeutral2Hasher

An implementation of std::hash::Hasher.

Functions

hash32

MurmurHash2 32-bit hash functions for a byte array.

hash32_with_seed

MurmurHash2 32-bit hash function for a byte array. For convenience, a 32-bit seed is also hashed into the result.

hash64

MurmurHash2 64-bit hash functions for a byte array.

hash64_with_seed

MurmurHash2 64-bit hash function for a byte array. For convenience, a 64-bit seed is also hashed into the result.