hesela.devUniversal hashing
Universal hashing selects a hash function at random from a family with a bounded collision probability for every fixed pair of distinct keys.
For a range of m values, universality requires Pr[h(x) = h(y)] <= 1/m for each fixed x != y, with probability over the randomly chosen function h. The keys are independent of that choice. This is an average over functions, not a worst-case promise for the chosen function. [1] [2]
With n stored keys and a fixed absent query, the expected number of stored keys in its bucket is at most n/m. A chained table still compares keys to resolve bucket collisions; expected bucket occupancy is not an exact-membership guarantee from the hash alone. [2]
A finite example maps three input bits to two output bits using a random binary matrix. All 28 distinct key pairs collide under exactly 16 of the 64 matrices, yet the zero key always maps to zero. Adding an independent, uniform two-bit offset gives 256 affine maps and uniform, independent outputs for each pair. [3]
Strong universality requires each ordered output pair to occur with probability 1/m^2 for distinct input keys. Plain universality does not require that stronger property. Nor does it promise collision resistance: in the finite example, choosing a colliding pair after seeing the matrix succeeds for every matrix. [2] [3]
Relations
Limitations
- A pairwise collision bound alone does not supply all independence assumptions needed by other randomized data structures. [2]
Citations
- Carter and Wegman. Universal Classes of Hash Functions. JCSS 18(2), 143-154 (1979). DOI: 10.1016/0022-0000(79)90044-8.
- Thorup. High Speed Hashing for Integers and Strings. arXiv:1504.06804v9 (2020), sections 2, 2.1, 3 and 6.
- Hesela: exhaustive binary-matrix hashing example, including output bias and fixed-versus-adaptive pairs.
Sources & caveats
- The finite example enumerates every seed and input pair in a toy family; it is a mathematical demonstration, not a storage benchmark or security evaluation.