Choosing a non-cryptographic hash function
- For user supplied data use SipHash to prevent hash flood attacks.
- Use xxHash as a fast hash for generic data.
- For integers or small data (less than 64 bits) use a mixing function as described below.
Integer hashing / mixing
When hashing small data (less than 64 bits) such as integers it’s worthwhile to use a specialized hash function that is small, fast and can be inlined by the compiler. In practice using the CRC32 instruction provides a very good speed versus collision trade-off. I have used it with linear probing hash tables with good results. I tried different hashes such as Murmur3 finalizer, rrmxmx and splitmix64, but CRC32 seems to provide the better speed vs collision trade-off. Linear probing hash tables needs a good hash function, but in my experience performance is not very sensitive to the hash function, it only needs to be good enough. Note that CRC32 is only fast when using a hardware implementation.
CRC32 implementation in C++:
struct crc32_hash {
size_t operator()(uint64_t h) const noexcept {
return _mm_crc32_u64(0, h);
}
};
Or seeded version with some hash flooding protection:
struct crc32_seeded_hash {
uint32_t seed;
crc32_seeded_hash() {
while (!_rdrand32_step(&seed));
}
size_t operator()(uint64_t h) const noexcept {
return _mm_crc32_u64(seed, h);
}
};
An alternative that doesn’t require a CRC32 instruction is the shift-xor-multiply style mixers. These are used as a finalizer in many of the fast hash functions, for example Murmur3, CityHash, clhash, xxHash, etc. It’s also used by the splitmix64 random number generator.
C++ implementation using optimized constants from Pelle Evensen:
struct moremur_hash {
size_t operator()(uint64_t x) const noexcept {
x ^= x >> 27;
x *= 0x3C79AC492BA7B653UL;
x ^= x >> 33;
x *= 0x1C69B3F74AC4AE35UL;
x ^= x >> 27;
return x;
}
};
Other alternative parametrizations of the above function:
- http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html
- http://xorshift.di.unimi.it/splitmix64.c
- https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp#L8
- https://nullprogram.com/blog/2018/07/31/
References
SMHasher is suite of hash function quality and speed tests: https://github.com/rurban/smhasher
Assorted list of hash functions:
- https://github.com/erthink/t1ha
- https://cyan4973.github.io/xxHash/
- https://github.com/vnmakarov/mum-hash
- https://github.com/demerphq/BeagleHash
- https://github.com/wangyi-fudan/wyhash
- https://github.com/google/farmhash
- https://github.com/google/cityhash
- https://github.com/lemire/clhash
- https://github.com/veorq/SipHash, https://131002.net/siphash/
- https://github.com/jandrewrogers/MetroHash
- https://github.com/cmuratori/meow_hash
Useful links:
- Bob Jenkins. “4-byte Integer Hashing”. https://burtleburtle.net/bob/hash/integer.html
- Stackoverflow. “What integer hash function are good that accepts an integer hash key?”. https://stackoverflow.com/questions/664014/what-integer-hash-function-are-good-that-accepts-an-integer-hash-key
- David Stafford. “Better Bit Mixing - Improving on MurmurHash3’s 64-bit Finalizer”. http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html
- xxHash. “Performance comparison”. https://github.com/Cyan4973/xxHash/wiki/Performance-comparison#benchmarks-concentrating-on-small-data
- “Hash Function Prospector”. https://github.com/skeeto/hash-prospector
- Chris Wellons. “Prospecting for Hash Functions”. https://nullprogram.com/blog/2018/07/31/
- Pelle Evensen. “Mostly mangling: On hashing and pseudo-random number generation.”. https://mostlymangling.blogspot.com/
- https://github.com/martinus/better-faster-stronger-mixer