Foundations, Hash Functions & Load Factor

Topics Covered:
35. Hashing Principles & Direct Address Table Comparison • 36. Hash Functions & Uniform Distribution (SUHA, Division, Multiplication, Polynomial Rolling Hash) • 37. Collisions, The Birthday Paradox & Load Factor ($\alpha$) • Production Implementations & Formal Derivations

Direct address tables offer constant-time retrieval by assigning every possible key a distinct physical array index, but demand catastrophic memory allocations when key universes are sparse. Hashing bridges this efficiency gap by compressing vast key spaces into compact array bounds through deterministic mathematical transformations. This chapter examines the Direct Address Dilemma, Simple Uniform Hashing Assumptions (SUHA), division and multiplication hash generators, polynomial rolling hashes for strings, the mathematical inevitability of collisions under the Birthday Paradox, and load factor ($\alpha$) thresholds for dynamic rehashing.

• Contrast direct addressing with compact hash tables and quantify the memory savings achieved across sparse key spaces.
• Formalize the Simple Uniform Hashing Assumption (SUHA) and evaluate the mathematical properties of division, multiplication, and polynomial rolling hash functions.
• Prove why hash collisions are mathematically unavoidable using Dirichlet's Pigeonhole Principle.
• Derive the Birthday Paradox collision threshold $n\approx 1.177\sqrt{m}$ and explain why collisions occur far earlier than intuition suggests.
• Calculate the load factor $\alpha =n/m$ and define dynamic table resizing (rehashing) triggers to preserve $O(1)$ expected amortized bounds.
• Implement production-grade polynomial string hashing and universal hash generators across C++, Python, and Java.

In an ideal computational model, data retrieval executes in $\Theta (1)$ time by using the search key directly as an array index. This pattern is known as Direct Addressing.

The Direct Addressing Dilemma:

Suppose an enterprise needs to store employee profiles indexed by a 9-digit Social Security Number (SSN: 000-00-0000 to 999-99-9999):

• Universe of Keys ($\mathcal{U}$): Contains $10^9$ possible keys ($|\mathcal{U}|=1,000,000,000$).
• Direct Address Table: Requires allocating a contiguous array of $10^9$ pointers. At 8 bytes per pointer, this demands $8\text{ Gigabytes}$ of RAM!
• Sparsity Reality: If the company employs only $500$ workers, $99.99995\%$ of the allocated memory sits permanently empty and wasted.

The Hashing Resolution:

Rather than allocating memory for every conceivable key in universe $\mathcal{U}$, allocate a compact table of size $m\ll |\mathcal{U}|$ (e.g., $m=1,000$ slots, requiring mere kilobytes of RAM). A deterministic mathematical function $h(k)$, called a Hash Function, maps keys into table index slots:

1. Strict Determinism: For any identical key $k$, $h(k)$ must evaluate to the exact same integer every time across the process lifecycle.
2. Simple Uniform Hashing Assumption (SUHA): Every key is equally likely to hash into any of the $m$ slots, independently of where any other key has hashed:
   $$\mathrm{Pr}(h(k_1)=j)=\frac{1}{m}\text{for all }j\in \{0,\dots ,m-1\}$$
3. Computational Efficiency: Evaluates in $O(1)$ time for fixed-width numeric keys and $O(L)$ time for strings of length $L$.
4. The Avalanche Effect: Flipping a single bit in the input key should alter roughly $50\%$ of the bits in the output hash code, preventing clustered hash values for sequential keys.

A. The Division Method

• Rule for Table Size $m$: Choose $m$ to be a prime number not close to powers of 2 or 10.
• Why Avoid Powers of Two ($m=2^p$)? Computing $k(\mathrm{mod}{2}^p)$ simply isolates the lowest $p$ bits of $k$ (equivalent to a bitwise mask k & (m - 1)). All higher-order bits are completely ignored!

B. The Multiplication Method (Knuth's Golden Ratio Method)

C. Polynomial Rolling Hash for Strings

A string $S=s_0{s}_1\dots s_{L-1}$ is treated as a polynomial where character code units are coefficients evaluated at base $p$:

By Dirichlet's Pigeonhole Principle, if $n$ items are placed into $m$ containers and $n>m$, at least one container must hold more than one item. Because $|\mathcal{U}|\gg m$, collisions are mathematically guaranteed to occur:

How many randomly chosen people must gather in a room before the probability that at least two share a birthday exceeds $50\%$? The mathematical answer is just 23 people!

Formal Mathematical Derivation:

Let $n$ be the number of inserted keys and $m$ be the number of hash table slots. The probability that all $n$ keys hash into distinct slots (zero collisions) is:

A. C++20 Polynomial String Hash with Avalanche Bit-Mixer

#include <string_view>
#include <cstdint>

class HashUtil {
public:
    // Polynomial Rolling Hash for Strings
    static uint64_t polynomial_string_hash(std::string_view s, uint64_t p = 53, uint64_t m = 1'000'000'007) {
        uint64_t hash_val = 0;
        uint64_t p_power = 1;
        for (char c : s) {
            uint64_t char_val = static_cast<unsigned char>(c) + 1;
            hash_val = (hash_val + char_val * p_power) % m;
            p_power = (p_power * p) % m;
        }
        return hash_val;
    }

    // SplitMix64 64-bit Integer Avalanche Hash (Used in fast hashtables)
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
};

B. Python 3 Rolling Hash with Substring Slice O(1) Equality

class RollingHash:
    """Computes polynomial string hash and prefix hash powers for O(1) substring queries."""
    def __init__(self, s: str, base: int = 53, mod: int = 1_000_000_007):
        self.s = s
        self.base = base
        self.mod = mod
        n = len(s)
        self.prefix_hash = [0] * (n + 1)
        self.power = [1] * (n + 1)

        for i in range(n):
            val = ord(s[i]) + 1
            self.prefix_hash[i + 1] = (self.prefix_hash[i] * base + val) % mod
            self.power[i + 1] = (self.power[i] * base) % mod

    def query(self, left: int, right: int) -> int:
        """Returns the polynomial hash of substring s[left:right+1] in O(1) time."""
        total = self.prefix_hash[right + 1]
        subtract = (self.prefix_hash[left] * self.power[right - left + 1]) % self.mod
        return (total - subtract + self.mod) % self.mod

1. Direct Addressing vs. Hashing: Direct addressing trades infinite memory for $O(1)$ lookups; hashing achieves expected $O(1)$ performance in compact memory by mapping keys into $[0,m-1]$.
2. Prime Moduli: The classical division method utilizes prime table sizes $m$ to avoid harmonic bit-clustering.
3. The Birthday Paradox: Collisions occur with $50\%$ probability after only $O(\sqrt{m})$ insertions ($23$ keys for $m=365$).
4. Load Factor Governance: Maintaining $\alpha \le 0.75$ guarantees expected $O(1)$ operations across practical workloads.

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 11: Hash Tables. MIT Press.
2. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.), Section 6.4: Hashing. Addison-Wesley.
3. Mitzenmacher, M., & Upfal, E. (2017). Probability and Computing: Randomization and Probabilistic Techniques in Algorithms (2nd ed.), Chapter 5: Balls, Bins, and Random Graphs. Cambridge University Press.