Hash Functions: Division, Multiplicative, Universal & k-Independent Families

Deterministic Hashing vs Carter-Wegman Universal Families

Classical textbooks begin with the Simple Uniform Hashing Assumption (SUHA), which posits that keys are drawn independently and uniformly from the universe $\mathcal{U}$. In production systems, keys are never uniform: memory addresses are aligned multiples of $8$ or $16$, IPv4 subnets cluster in high bits, and sequential database IDs exhibit arithmetic progressions.

• Division Method ($h(k) = k \bmod m$): If $m = 2^r$, $k \bmod 2^r$ simply extracts the lowest $r$ bits of $k$, ignoring the upper $w - r$ bits completely. For pointer keys aligned to 16-byte heap boundaries, the lowest 4 bits are always $0000_2$, leaving $15/16$ of buckets permanently empty. Choosing a prime $m$ not close to a power of $2$ mixes bits better, but 64-bit integer division (DIV r64) costs 20–40 cycles on modern x86-64 cores.
• Fibonacci Multiplicative & Multiply-Shift Hashing: Given word size $w = 64$ and table size $m = 2^r$, Knuth's multiplicative method multiplies $k$ by an odd constant $A \approx \phi^{-1} \cdot 2^{64} = \text{0x9E3779B97F4A7C15}$ (derived from the golden ratio $\phi = (1+\sqrt{5})/2$) and extracts the top $r$ bits: $h(k) = (k \cdot A) \gg (64 - r)$. Dietzfelbinger et al. proved that selecting a random odd 64-bit multiplier $a$ at startup makes $h_a(k) = (a \cdot k) \gg (64 - r)$ a 2-approximate universal family with collision probability $\le 2/m$.
• Carter-Wegman Universal Family ($\mathcal{H}_{p,m}$): Choose a prime $p > |\mathcal{U}|$ (e.g., Mersenne prime $p = 2^{61} - 1$), and draw random $a \in \{1, \dots, p-1\}$, $b \in \{0, \dots, p-1\}$. Then $h_{a,b}(k) = ((ak + b) \bmod p) \bmod m$ satisfies strict universality: $\Pr_{h \in \mathcal{H}}[h(x) = h(y)] \le 1/m$ for all $x \ne y$.

Visualizing Multiply-Shift & Carter-Wegman Bit Dispersion

The SVG diagram below contrasts naive modulo masking against 64-bit Multiply-Shift hashing, where low-entropy key bits are diffused upward into the top $r$ index bits via multiplication by an odd 64-bit random seed.

Production C++20 Implementation: Pairwise-Independent & Mersenne $k$-Independent Hashers

// C++20: Dietzfelbinger Multiply-Add-Shift (2-Independent) & Carter-Wegman mod (2^61 - 1)
#include <cstdint>
#include <array>

// 1. Strongly 2-Universal (Pairwise Independent) Multiply-Add-Shift from 64-bit to r bits
struct MultiplyAddShiftHash {
    __uint128_t a; // Random odd 128-bit multiplier
    __uint128_t b; // Random 128-bit additive offset
    uint32_t r;    // log2(table_size)

    uint64_t operator()(uint64_t key) const noexcept {
        // Full 128-bit arithmetic modulo 2^128, then extract top r bits of low 64-bit half
        uint64_t mixed = static_cast<uint64_t>((a * key + b) >> 64);
        return mixed >> (64 - r);
    }
};

// 2. Branchless Mersenne Prime (p = 2^61 - 1) k-Independent Polynomial Hash
template <size_t K>
class MersenneKIndependentHash {
    static constexpr uint64_t P = (1ULL << 61) - 1;
    std::array<uint64_t, K> coeff_; // Random seeds in [0, P - 1]

    static uint64_t modMersenne(__uint128_t z) noexcept {
        uint64_t res = static_cast<uint64_t>(z & P) + static_cast<uint64_t>(z >> 61);
        return (res >= P) ? (res - P) : res;
    }

public:
    explicit constexpr MersenneKIndependentHash(std::array<uint64_t, K> seeds) noexcept
        : coeff_(seeds) {}

    uint64_t evaluate(uint64_t x) const noexcept {
        x = modMersenne(x);
        uint64_t acc = coeff_[K - 1];
        for (size_t i = K - 1; i-- > 0; ) {
            acc = modMersenne(static_cast<__uint128_t>(acc) * x + coeff_[i]);
        }
        return acc; // Uniformly distributed in [0, 2^61 - 2]
    }

    // Lemire's FastRange reduction to [0, m - 1] without integer division
    uint32_t bucket(uint64_t x, uint32_t m) const noexcept {
        uint64_t h32 = evaluate(x) & 0xFFFFFFFFULL;
        return static_cast<uint32_t>((h32 * static_cast<uint64_t>(m)) >> 32);
    }
};