This document, originating from the "Prospecting for Hash Functions" article and its accompanying GitHub issue discussion, details an extensive empirical search for optimal non-cryptographic integer hash functions. The author's custom "Hash Prospector" tool, utilizing JIT compilation, systematically generates, compiles, and evaluates random hash functions based on their avalanche effect and low bias. Key findings include the identification of a prevalent "XOR-right-shift, multiply, XOR-right-shift, multiply, XOR-right-shift" pattern in high-performing functions. The ongoing project has seen significant community contributions, particularly from TheIronBorn, employing advanced optimization techniques like metaheuristics and SIMD acceleration. This collaborative effort has led to the discovery of progressively less biased 32-bit and 16-bit hash functions, culminating in the triple32 function which approaches the theoretical bias limit for 32-bit integers, and the most recent 2-round function by TheIronBorn demonstrating the best performance in its class.
Summary:
Initial Project Conception (July 31, 2018):
The author initiated a project to design non-cryptographic integer hash functions, aiming to understand avalanche effects and potentially surpass existing functions.
Developed "Hash Prospector," a JIT-compiling tool for x86-64 to generate, evaluate, and identify high-quality hash functions through rapid iteration.
Focused on integer hash functions (n-bit to n-bit) with a 1:1 mapping (no collisions), achieved by using only reversible operations (e.g., XOR with constant, addition, multiplication by odd number, rotations, XOR/add/subtract with shifts).
Hash Function Evaluation:
Two key properties were measured: high avalanche effect (50% bit flip chance for single input bit flips) and low bias (no correlation between specific input/output bit flips).
A method involving an N x N table (input bits vs. output bits) and standard deviation calculation was used to quantify bias.
Monte Carlo sampling provided fast estimates for pre-screening functions, reserving full evaluation for promising 32-bit candidates.
Initial Discoveries:
The prospector found prospector32, a 32-bit hash function (x ^= x >> 15; x *= 0x2c1b3c6dU; x ^= x >> 12; x *= 0x297a2d39U; x ^= x >> 15; return x;) that outperformed some known functions like the H2 SQL Database's hash32, though it was slightly more biased than MurmurHash3's 32-bit finalizer.
A common pattern emerged: XOR-right-shift, multiply, XOR-right-shift, multiply, XOR-right-shift (a five-tuple structure), found independently by the prospector.
No provably better 64-bit functions were found compared to SplittableRandom / SplitMix64 or hash64 (which also follow the five-tuple pattern).
Significant Breakthroughs (Update after one week of publishing):
Discovery of lowbias32 (x ^= x >> 16; x *= 0x7feb352dU; x ^= x >> 15; x *= 0x846ca68bU; x ^= x >> 16; return x;), a 2-round hash with an exact bias of 0.17353355999581582, less biased than MurmurHash3's finalizer.
Discovery of triple32 (x ^= x >> 17; x *= 0xed5ad4bbU; x ^= x >> 11; x *= 0xac4c1b51U; x ^= x >> 15; x *= 0x31848babU; x ^= x >> 14; return x;), a 3-round hash with an exact bias of 0.020888578919738908, which effectively reaches the theoretical bias limit for 32-bit integers, making it statistically indistinguishable from a random permutation. This is the best overall hash function found and described in the document.
Further Developments (February 2020 Update):
The hash functions were successfully implemented and tested in GLSL shaders.
Community Contributions & New Records (April/May 2022 - TheIronBorn):
TheIronBorn significantly advanced the search using metaheuristics and exact search with SIMD acceleration for bias calculation.
A new best-known 32-bit 2-round function was found: [16 21f0aaad 15 735a2d97 15] with a bias of 0.10704308166917044, improving upon previous 2-round designs.
New best 16-bit 2-round, 3-round, and 4-round (without multiply) functions were also identified.
Ongoing Discussions & Insights (November 2023 - April 2024):
SipHash's full 2^32 input bias was measured at ~0.0211, confirming the theoretical bias target.
Discussion on designing 64-bit hashes using 32-bit operations (e.g., in JavaScript) by intermixing two 32-bit hash variables.
Clarification on reversing XOR-right-shift operations: x ^= x >>> C; is reversed by x ^= x >>> C; x ^= x >>> (2*C); ... (for shifts up to the bit width).
Key Takeaway: The project demonstrates a successful computational and collaborative approach to finding highly effective non-cryptographic hash functions, constantly pushing the boundaries of known minimal bias through systematic search and community refinement.