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
OneAtATime
- 354.163715 mb/secFNV
- 443.668038 mb/secSuperFastHash
- 985.335173 mb/seclookup3
- 988.080652 mb/secMurmurHash
1.0 - 1363.293480 mb/secMurmurHash
2.0 - 2056.885653 mb/sec
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 |
|
Murmur2A |
|
Murmur2AHasher |
An implementation of |
Murmur2Hasher |
An implementation of |
Murmur2Hasher_x64_64 |
An implementation of |
Murmur2Hasher_x86_64 |
An implementation of |
Murmur2_x64_64 |
|
Murmur2_x86_64 |
|
MurmurAligned2 |
|
MurmurAligned2Hasher |
An implementation of |
MurmurNeutral2 |
|
MurmurNeutral2Hasher |
An implementation of |
Functions
hash32 |
|
hash64 |
|
hash32_with_seed |
|
hash64_with_seed |
|