This article details the author's ambitious project, "Hash Prospector," designed to computationally discover superior non-cryptographic integer hash functions. Focusing on 1:1 mapping and reversible operations, the tool iteratively generates, compiles, and evaluates random hash functions based on avalanche effect and low bias. Initial findings led to prospector32, a 32-bit function outperforming many existing ones, and uncovered a common "XOR-right-shift, multiply, XOR-right-shift, multiply, XOR-right-shift" structure in high-performing hashes. Subsequent research and community contributions (notably by TheIronBorn) further refined these designs, yielding 32-bit functions like lowbias32 and triple32 that approach theoretical bias limits, and even more optimized variants with exceptionally low bias scores. The article also discusses challenges with 64-bit hashes, specific operation inversions, and applications in contexts like JavaScript shaders.
Summary:
Introduction to Hash Prospector: The author developed "Hash Prospector," a tool to generate, compile, and evaluate random non-cryptographic integer hash functions. The goal was to better understand hash functions and potentially discover designs superior to existing ones like those by Thomas Wang and Bob Jenkins.
Principles of Hash Function Generation: The focus is on integer hash functions that map inputs 1:1 (no collisions). This is achieved by ensuring every operation used in the hash function is reversible (e.g., XOR with a constant, addition with a constant, multiplication by an odd number, bit shifts, and rotations).
Measuring Hash Function Quality: Two critical properties are measured: a high avalanche effect (where flipping one input bit results in a 50% chance of each output bit flipping) and low bias (no correlation between which output bits flip for a particular input bit change). A standard deviation of an N x N correlation table is used as a normalized score, where lower scores are better.
Addressing Computational Challenges: Exhaustive testing for a 32-bit hash function is time-consuming (about 1.5 hours), and a 64-bit function is impractical. The solution involves using Monte Carlo sampling for quick estimations, reserving full tests only for the most promising 32-bit candidates.
Discovery of prospector32: The tool successfully found a 32-bit hash function named prospector32 (using x ^= x >> 15; x *= 0x2c1b3c6dU; x ^= x >> 12; x *= 0x297a2d39U; x ^= x >> 15;) that initially outperformed many known 32-bit hash functions in terms of bias.
Emergence of a Common Structure: A significant finding was that the best-performing 32-bit hash functions (including prospector32, a H2 SQL Database hash, and MurmurHash3's finalizer) all exhibit a similar structure: "XOR-right-shift, multiply, XOR-right-shift, multiply, XOR-right-shift." This pattern, described as "sloshing" bits, effectively diffuses them.
64-bit Hash Functions: While the prospector found many 64-bit hash functions with similar estimated bias to existing ones like SplittableRandom / SplitMix64, no functions were discovered that were provably better than the current state-of-the-art.
Later Breakthroughs and Optimizations (Article Updates):
The author found lowbias32 (x ^= x >> 16; x *= 0x7feb352dU; x ^= x >> 15; x *= 0x846ca68bU; x ^= x >> 16;), a 32-bit hash function with even lower bias than MurmurHash3's finalizer.
A 3-round function, triple32, was found (x ^= x >> 17; x *= 0xed5ad4bbU; x ^= x >> 11; x *= 0xac4c1b51U; x ^= x >> 15; x *= 0x31848babU; x ^= x >> 14;) that achieved a bias score statistically indistinguishable from a random permutation (though later tests found second-order biases).
Community Contributions and Ongoing Research (GitHub Discussions):
TheIronBorn, using metaheuristic optimization and SIMD acceleration, found even better 32-bit hash functions with exceptionally low bias scores (e.g., [16 21f0aaad 15 735a2d97 15] achieving 0.10704308).
Discussions included the use of these hash functions in GLSL shaders and JavaScript environments, where 32-bit operations have specific limitations.
The mathematical inversion of bitwise operations (e.g., the inverse of x ^= x >>> 15; is x ^= x >>> 15; x ^= x >>> 30;) was clarified, demonstrating the reversibility of these functions.
Testing confirmed that even cryptographic hashes like SipHash achieve a bias close to the theoretical limit (~0.021), validating the low bias scores found by the prospector.
Key Takeaway: The "Hash Prospector" project successfully demonstrated a computational approach to discovering highly efficient and low-bias non-cryptographic integer hash functions, revealing a powerful common structure and setting new benchmarks in the field.