Hash Function Design

A hash function h: U → {0, 1, …, m-1} maps an arbitrarily large universe of keys U (strings, integers, structs, anything) into a small integer range [0, m) used to index a Hash Table’s bucket array. A good hash function for hash tables is deterministic, fast (a handful of CPU cycles per byte), uniform (each output bucket equally likely across realistic inputs), avalanching (one input bit flip changes ~50% of output bits), and — for adversarial environments — keyed so an attacker cannot precompute colliding inputs. This note unpacks each property, walks through the universal hashing framework introduced by Carter and Wegman in 1979, and surveys the production non-cryptographic hash functions actually shipped in standard libraries: MurmurHash3, xxHash, CityHash / FarmHash, and SipHash. Cryptographic hashes (MD5, SHA-1, SHA-2, SHA-3) are deliberately excluded as overkill — they are tens of times slower per byte than the production options and provide guarantees (preimage and second-preimage resistance) that hash tables do not need.

1. Intuition — A Lossy Fingerprint

A hash function is a lossy fingerprint generator for a value. You hand it any blob of data — a 4-byte integer, a 30-character string, a 4 KB struct — and it hands back a fixed-width integer (typically 32, 64, or 128 bits) that “represents” the input. The same input always returns the same fingerprint (determinism); two different inputs almost always return different fingerprints, but because the input space is unbounded and the output is bounded, collisions are unavoidable in principle by the pigeonhole principle.

The design problem is therefore not “avoid all collisions” — that is mathematically impossible — but make collisions look random so they are evenly distributed across the output space and no realistic input pattern produces clusters.

A useful analogy: imagine assigning every person in a country a four-digit “seat number” for a stadium with 10,000 seats. There are more people than seats, so two people will share a seat sometimes. A good assignment scatters people by seemingly arbitrary attributes — birth-second, last-digit-of-zip, parity of name length — so that any plausible group (everyone named “Smith”, everyone from one city, everyone born in 1990) is spread across the stadium rather than clumped on one row. A bad assignment would, say, group people by surname’s first letter — “Smith” overflows row 19 while row 26 (“Z”) is empty. The bad assignment is deterministic and fast, but it fails the uniform distribution requirement.

2. The Five Properties of a Good Hash-Table Hash Function

2.1 Determinism

h(k) must always return the same value for the same k. Without this, you could insert a key, walk away, walk back, and not find it because h(k) returned a different bucket the second time. This is so fundamental it is rarely stated explicitly, yet violations sneak in: hashing a Python object whose __hash__ depends on its memory address and then pickling/unpickling moves it; hashing a struct that includes uninitialized padding bytes; hashing a string in a language with hash randomization without realizing the randomization changes between processes. The contract is “stable within a single process run” at minimum, “stable across runs” if the hash is to be persisted.

2.2 Speed

A hash table promises O(1) per lookup. If h(k) itself takes Θ(|k|) time — which it does for any string-keyed input, since you have to read the bytes — then the lookup cost is really Θ(|k|), not Θ(1). We treat key length as a constant in the asymptotic analysis, but the constant matters: a hash function that takes 100 ns per byte versus 1 ns per byte can dominate the runtime of a hash-heavy program. Production non-cryptographic hashes target single-digit cycles per byte on modern x86; xxHash3 is benchmarked above 30 GB/s on a single core for large inputs (xxHash benchmarks). Cryptographic hashes like SHA-256 hit perhaps 0.5–1 GB/s on the same hardware (without AES-NI/SHA-NI extensions) — slower by an order of magnitude or more.

2.3 Uniformity

Across the realistic distribution of inputs, the output should be distributed uniformly over [0, m). Formally, for any two distinct keys k₁ ≠ k₂, we want:

Pr[h(k₁) = h(k₂)] ≈ 1/m

— the same as if buckets were chosen by a fair die roll. If the hash function maps too many inputs into a few buckets (poor uniformity), chains in separate chaining become long, or probe sequences in open addressing grow, and the O(1) story collapses to O(n).

This is hard to prove for any single function on real inputs — input distribution is application-dependent. The universal hashing framework (§3) sidesteps this by making the proof depend on randomness in the function, not the input.

2.4 Avalanche

The avalanche criterion, due to Feistel in the cryptography literature, states: flipping any one input bit should flip approximately half (50%) of the output bits, with each output bit flipping independently. The strict avalanche criterion (SAC), introduced by Webster and Tavares in 1985 for cryptographic block ciphers, is the formal version.

Why this matters for hash tables: real keys are not random. They have correlated bits — the first 4 characters of URLs are almost always “http”, the last 6 digits of US phone numbers cluster by exchange, sequential integers differ in only their low bits. A hash function that fails the avalanche criterion on its low bits will map sequential integers into a tiny region of the output space — and many implementations then take the result mod m to pick a bucket, which only looks at those very low bits. The result: catastrophic clustering. A good hash function “diffuses” every input bit into every output bit, breaking up these correlations.

2.5 Sensitivity to All Input Bits

Closely related to avalanche but worth stating separately: every byte of the input must influence the output. A naive hash like h(s) = s[0] + s[1] + s[2] ignores bytes 3 and beyond — strings with the same first three characters all collide. Production hashes mix every input byte into a state register through a chain of multiplies, XORs, and rotations.

3. Universal Hashing — The Carter-Wegman 1979 Framework

3.1 The Adversarial Setting

Suppose you publish your hash function publicly: it is a fixed deterministic function h : U → [0, m). An adversary who controls the keys can compute h(k) for any candidate k and pick n keys that all hash to the same bucket. Now your O(1) hash table is O(n) per lookup — they have engineered worst-case behavior. This is the hash-collision DoS attack discussed in Hash Table §10.3.

The solution: make the hash function itself random. Don’t publish h; pick h at runtime from a family H = {h₁, h₂, …} of hash functions, then keep the choice secret. The adversary now has to engineer collisions without knowing which function you picked.

3.2 The Definition

Carter and Wegman’s 1979 paper “Universal classes of hash functions” (Journal of Computer and System Sciences 18(2), pp. 143–154) defined a family H = {h : U → [0, m)} to be universal if for any two distinct keys k₁ ≠ k₂ ∈ U:

Pr_{h ~ H}[h(k₁) = h(k₂)]  ≤  1/m

— the probability is taken over the random choice of h from the family. The keys k₁, k₂ are arbitrary and adversarial; the randomness is in our hash-function selection. This is exactly the same probability as if h were a truly random function.

Why this fixes the adversary problem: the adversary picks n keys before you reveal your h. The expected number of pairwise collisions among those n keys is bounded:

E[collisions]  =  Σ_{i<j} Pr[h(k_i) = h(k_j)]  ≤  C(n, 2) · (1/m)  ≈  n² / (2m)

For m ≥ n (load factor ≤ 1), this is O(n) total collisions across the entire table — i.e., O(1) average chain length. The adversary can no longer engineer worst-case behavior because they cannot predict our random choice.

3.3 A Concrete Universal Family

Carter and Wegman gave an explicit construction. Let p be a prime larger than |U|, and pick a ∈ {1, 2, …, p-1}, b ∈ {0, 1, …, p-1} uniformly at random. Define:

h_{a,b}(k)  =  ((a · k + b) mod p) mod m

The family H = {h_{a,b} : a ∈ [1, p), b ∈ [0, p)} is universal. The proof is a short modular-arithmetic argument: for any two distinct keys k₁ ≠ k₂, the system a·k₁ + b ≡ y₁, a·k₂ + b ≡ y₂ (mod p) has a unique solution (a, b) for any pair (y₁, y₂). Counting pairs (y₁, y₂) with y₁ ≡ y₂ (mod m) and dividing by p(p-1) yields the 1/m bound. Full proof in [CLRS §11.3.3] or the original paper.

Observe: this family has only O(p²) members (parameterized by two integers), so picking h requires only O(log p) random bits — cheap. And h_{a,b} is fast to evaluate: one multiply, one add, one mod-by-prime, one mod-by-m.

3.4 k-Independence — The Stronger Property

Universal families guarantee pairwise collision probability. A stronger property, k-wise independence, demands that the hash values of any k distinct keys behave like k independent uniform random variables in [0, m). Formally, for any distinct k₁, …, k_k and any values v₁, …, v_k ∈ [0, m):

Pr_{h ~ H}[h(k₁) = v₁ ∧ … ∧ h(k_k) = v_k]  =  1/m^k

Universal hashing is essentially 2-independent (slightly weaker — universal only bounds pairwise collisions, not the joint distribution). 4-independence and 5-independence are sufficient for stronger algorithmic guarantees: linear probing’s expected O(1) lookup time was famously proven by [Pagh, Pagh, Ružić 2007] and Pătraşcu-Thorup 2011 to require 5-independent hash functions in the worst case. With only 2-independent hashing, linear probing can degrade in adversarial settings.

The simple tabulation hashing scheme (Pătraşcu and Thorup, “The power of simple tabulation hashing”, arXiv:1011.5200 in 2010, published at STOC 2011 and in JACM 2012) provides surprisingly strong properties from a very simple construction: split the key into characters b₀ b₁ … b_{c-1}, look up each in a precomputed random table T_i[·] of random hash-width values, and XOR the results. The scheme itself dates to Carter and Wegman (1977); simple tabulation is exactly 3-independent but not 4-independent (Tabulation hashing, Wikipedia). Pătraşcu and Thorup’s contribution was to show it behaves far better than its 3-independence would predict: it gives the same constant-time guarantee for linear probing that normally requires 5-independence, supports Chernoff-style concentration, min-wise hashing for set-intersection estimation, and cuckoo hashing (though with a higher insertion-failure probability than higher-independence families) (Pătraşcu & Thorup 2011, arXiv:1011.5200). It is also faster in practice than algebraic universal families because it replaces multiplications with table lookups and XORs.

Uncertain

Verify: the quantitative bounds simple tabulation gives for each downstream algorithm (e.g. the exact cuckoo-hashing failure-probability constant). Reason: Pătraşcu-Thorup 2011 is the foundational result and the 3-independent/not-4-independent characterization is firm, but the precise constants for individual applications have been tightened by follow-up work (e.g. mixed/twisted tabulation). To resolve: consult the JACM 2012 version and subsequent tabulation-hashing papers for the exact constant in the specific application. uncertain

4. Production Non-Cryptographic Hash Functions

These are the hashes actually shipped in standard libraries and high-performance code. None are cryptographically secure (you can construct collisions if you try — except SipHash, which is keyed-secure). All are fast and avalanching.

4.1 MurmurHash3

Author: Austin Appleby, 2008. Variants: 32-bit (MurmurHash3_x86_32), 128-bit (MurmurHash3_x86_128, MurmurHash3_x64_128).

Inner loop (32-bit version, simplified):

k *= 0xcc9e2d51;
k = ROTL32(k, 15);
k *= 0x1b873593;
h ^= k;
h = ROTL32(h, 13);
h = h * 5 + 0xe6546b64;

The two odd 32-bit multiplier constants and two rotation amounts were tuned by Appleby through extensive avalanche-test searches. The mixing pattern — multiply, rotate, multiply, xor — is the canonical MurmurHash recipe. It diffuses every input bit through every output bit within a few rounds.

Speed: ~3 GB/s for 32-bit MurmurHash3 on modern x86 (single core), ~6 GB/s for the 128-bit version.

Properties: excellent avalanche, passes the SMHasher test suite (designed by Appleby specifically to torture-test hash functions). Not keyed — so vulnerable to hash-flooding attacks if the seed is publicly known. The 2012 disclosures of hash-flooding DoS in Java, Ruby, and PHP partially motivated the move to SipHash for security-sensitive uses; languages that still use MurmurHash (e.g., older versions of Cassandra, Redis for some internal uses) accept the security trade-off for speed.

4.2 xxHash (xxHash3 / xxHash64 / xxHash32)

Author: Yann Collet, 2012-present. Versions: xxHash32, xxHash64, xxHash3 (introduced 2019), xxHash128.

xxHash uses an even simpler inner loop than MurmurHash but processes multiple lanes in parallel to exploit modern CPU pipelines:

acc = (acc + input * PRIME64_2) * PRIME64_1;
acc = ROTL64(acc, 31);

xxHash3 in particular processes input in 64-byte chunks (a CPU cache line) using 8 parallel accumulators, each updated independently — this is vectorizable and saturates the integer-multiply units of modern x86. The result: >30 GB/s on a single core for inputs ≥ 1 MB (benchmarks on the xxHash repository). For small inputs (< 64 bytes), xxHash3 has hand-tuned short-input fast paths.

Where used: lz4 and zstd compression for checksums, RocksDB, ClickHouse, file-system tools for fast hashing of large blobs.

Properties: excellent avalanche and SMHasher scores; has a “secret key” parameter in xxHash3 making it weakly keyed (full collision resistance under unknown key is not claimed — for security use SipHash). Does not provide DoS resistance against an adversary who knows the secret.

4.3 CityHash and FarmHash

Author: Geoff Pike (Google), 2011 (CityHash) and 2014 (FarmHash). FarmHash supersedes CityHash; CityHash was tuned for x86_64, FarmHash adapts to multiple platforms (ARM, PowerPC).

The Google “fast hash” lineage — CityHash → FarmHash → and the family of absl::Hash variants used internally at Google — emphasizes:

• Throughput on long strings (multi-megabyte inputs).
• Fast small-string hashing (< 64 bytes), which dominates real-world hash-table use where keys are short.
• Multiple parallel state words (4, 8, or more) updated in lockstep.

Like xxHash, these are not cryptographically secure; they assume the seed is private but provide no formal guarantees against an adversary who knows it.

Where used: widely inside Google, in absl::flat_hash_map (Google’s open-source SwissTable hash map). Many Google open-source projects ship a vendored CityHash/FarmHash for compatibility.

4.4 SipHash — The DoS-Resistant Default

Authors: Jean-Philippe Aumasson and Daniel J. Bernstein, 2012 (paper).

SipHash is a keyed pseudorandom function (PRF) — not just a hash. It takes a 128-bit secret key in addition to the input and produces a 64-bit (or 128-bit, in SipHash-128) output. Without knowledge of the key, an adversary cannot predict the output, even with unlimited query access (under standard cryptographic assumptions).

Variants: SipHash-2-4 (2 rounds per input block, 4 finalization rounds — the “default” balance of speed and security), SipHash-1-3 (faster, slightly less margin), SipHash-4-8 (more conservative).

Speed: ~1-2 GB/s on x86_64 for SipHash-2-4 — slower than MurmurHash/xxHash by ~3×, but still vastly faster than cryptographic hashes (SHA-256 is < 1 GB/s without hardware acceleration). The slowdown is the cost of the cryptographic guarantee.

Where used:

• Python (CPython): PEP 456 made SipHash-2-4 the default string/bytes hash in Python 3.4; CPython then switched the default to the faster SipHash-1-3 in Python 3.11 (bpo-29410 / GH-73596, merged Oct 2021) — not 3.12 as is sometimes misremembered. The per-process key is randomized via PYTHONHASHSEED=random (default since 3.3), so hash("foo") differs between runs.
• Rust (std::collections::HashMap): the default hasher is SipHash-1-3 (adopted in PR #33940, May 2016), though the docs explicitly reserve the right to change it (HashMap docs). Each HashMap’s RandomState draws a random key, so iteration order and bucket placement vary between program runs.
• Perl 5.18+, Ruby 2.0+, the Linux kernel’s hash table, OpenBSD’s arc4random-driven random data structures.

Why this matters: before SipHash adoption, attackers could send HTTP requests with carefully crafted POST bodies that all hashed to the same bucket in the server’s dict of form parameters, turning what should be O(n) parsing into O(n²) and DoSing the server. The 2011 Klink and Wälde 28C3 talk demonstrated this attack against PHP, ASP.NET, Java, Python (pre-3.3), Ruby, and others; SipHash with random per-process keys closes the attack surface because the adversary cannot precompute colliding inputs.

4.5 Side-by-Side Comparison

Function	Output	Speed (large input, single core, x86_64)	Keyed?	DoS-resistant?	Typical use
MurmurHash3 (32)	32 bits	~3 GB/s	weak (32-bit seed)	❌	Bloom filters, sharding when adversary irrelevant
MurmurHash3 (128)	128 bits	~6 GB/s	weak	❌	Cassandra token, content-addressed storage
xxHash64	64 bits	~13 GB/s	weak	❌	File checksums, in-memory KV stores
xxHash3 (64)	64 bits	~31 GB/s	weak (with secret)	❌	LZ4, Zstd, performance-critical hash tables
CityHash64	64 bits	~12 GB/s	weak	❌	Google internal hash maps (older)
FarmHash64	64 bits	~12-15 GB/s	weak	❌	Google internal hash maps (current)
SipHash-2-4	64 bits	~1-2 GB/s	✅ (128-bit)	✅	Default standard-library hash (Python, Rust, …)
SipHash-1-3	64 bits	~2-3 GB/s	✅	✅ (slightly less margin)	Python ≥3.11, Rust default
SHA-256	256 bits	~0.5-1 GB/s (no hw) / ~2 GB/s (SHA-NI)	✅ (HMAC)	✅	Cryptographic integrity, NOT hash tables

Uncertain

Verify: the specific GB/s figures in the table. Reason: throughput depends heavily on CPU generation, compiler, input size, and whether SIMD/SHA-NI is used — the numbers here are order-of-magnitude only. The one firmly sourced figure is xxHash3 at >30 GB/s on a single core for large inputs (xxHash benchmarks); the rest are representative. To resolve: run SMHasher and the xxHash repo’s benchmark on the target hardware. uncertain

5. Why Cryptographic Hashes Are Overkill for Hash Tables

Cryptographic hash functions like MD5, SHA-1, SHA-2, SHA-3, BLAKE2/3 provide three guarantees that hash tables do not need:

1. Preimage resistance. Given h(k), infeasible to find k. Hash tables don’t care — the keys are stored in the table anyway.
2. Second-preimage resistance. Given k, infeasible to find k' ≠ k with h(k) = h(k'). Hash tables tolerate collisions; they handle them via chaining or probing.
3. Collision resistance. Infeasible to find any k ≠ k' with h(k) = h(k'). The hash table doesn’t need this — the table’s invariants don’t depend on the absence of collisions, only on their being rare.

Achieving these guarantees requires expensive mixing — cryptographic hashes typically run dozens of rounds of nonlinear transformations and have substantial state. SHA-256 does 64 rounds of mixing for every 64 input bytes. MurmurHash3 does one multiply-rotate-multiply-xor per 4 input bytes. The factor-of-tens speed difference is exactly the cost of cryptographic safety margin — a margin you don’t need in a hash table.

The one exception is when you do need the cryptographic guarantees — for example, content-addressed storage (Git, IPFS) where two different inputs hashing to the same address would corrupt the data store. Then you accept the slowdown for the security property. But for dict.get() in Python, SipHash-1-3 is vastly more appropriate than SHA-256.

6. Pseudocode — A Universal Hash Function for Strings

A textbook universal hash for variable-length strings combines polynomial hashing with universal-family seeding:

poly_hash(s, a, p, m):
    h := 0
    for c in s:
        h := (h * a + ord(c)) mod p
    return h mod m

Choosing a uniformly at random in [1, p-1] and p a prime larger than the universe (typically p = 2^61 - 1 for 64-bit speed via Mersenne tricks) yields a universal family in the Carter-Wegman sense over strings (with caveats — strict universality requires bounded length; the family is “almost universal” otherwise). This is the same construction underlying Rabin-Karp string matching and String Hashing for substring problems.

7. Python Implementation — Toy Universal Hash + Avalanche Test

import os
import random
from typing import Callable
 
# A toy 32-bit "MurmurHash-style" mixer for pedagogy. Not production-grade.
def murmur32_mix(h: int) -> int:
    M = 0xFFFFFFFF
    h = (h ^ (h >> 16)) & M
    h = (h * 0x85ebca6b) & M
    h = (h ^ (h >> 13)) & M
    h = (h * 0xc2b2ae35) & M
    h = (h ^ (h >> 16)) & M
    return h
 
def murmur32(data: bytes, seed: int = 0) -> int:
    M = 0xFFFFFFFF
    c1, c2 = 0xcc9e2d51, 0x1b873593       # carefully-tuned mixing primes
    h = seed & M
    # Process 4-byte blocks.
    for i in range(0, len(data) - 3, 4):
        k = int.from_bytes(data[i:i+4], "little")
        k = (k * c1) & M
        k = ((k << 15) | (k >> 17)) & M    # rotate left 15
        k = (k * c2) & M
        h ^= k
        h = ((h << 13) | (h >> 19)) & M    # rotate left 13
        h = (h * 5 + 0xe6546b64) & M
    # Tail bytes — omitted for brevity in this pedagogical version.
    h ^= len(data)
    return murmur32_mix(h)
 
# A Carter-Wegman universal family h_{a,b}(k) = ((a*k + b) mod p) mod m for integer keys.
def make_universal_int_hash(m: int, p: int = (1 << 61) - 1) -> Callable[[int], int]:
    a = random.randint(1, p - 1)
    b = random.randint(0, p - 1)
    def h(k: int) -> int:
        return ((a * k + b) % p) % m
    return h
 
# Avalanche test: flip one bit, count how many output bits change.
def avalanche_test(hash_fn, n_trials: int = 10000) -> float:
    total_bits_flipped = 0
    for _ in range(n_trials):
        x = os.urandom(8)
        y = bytearray(x)
        bit = random.randrange(64)
        y[bit // 8] ^= 1 << (bit % 8)             # flip one bit
        h1 = hash_fn(bytes(x))
        h2 = hash_fn(bytes(y))
        diff = h1 ^ h2
        total_bits_flipped += bin(diff).count("1")
    return total_bits_flipped / (n_trials * 32)   # for a 32-bit output

A good hash function will have avalanche_test return ~0.5 (half the output bits flip on average per input bit flip). A bad one — say, the identity function — will return ~0.03 (almost no diffusion).

The two odd 32-bit multiplicative constants 0xcc9e2d51 and 0x1b873593 were chosen by Austin Appleby through extensive avalanche testing — they have no closed-form derivation, just empirical optimality on Appleby’s SMHasher test suite. Hash function constants are notoriously fragile: a single bit-flip in one of these constants typically degrades avalanche measurably, which is why production implementations carry these magic numbers verbatim from the reference source.

8. Complexity

Quantity	Cost
Hashing a key of length b bytes	Θ(b) — but treated as O(1) when keys are bounded length
Per-byte cost (production hashes)	~0.1–1 ns/byte (xxHash3 at the low end, SipHash at the high end)
Per-byte cost (cryptographic hashes)	~1–10 ns/byte (SHA-256 ~3 ns/byte without HW accel)
Universal-family selection	O(log p) random bits — a few hundred bits at most

The “treat hashing as O(1)” simplification is fair when keys are bounded — but for very long keys (megabyte blobs), the linear cost matters and choosing xxHash3 over SipHash can be a 20× difference in throughput.

9. Pitfalls

9.1 Using Modulo with a Non-Prime m

h(k) mod m only redistributes bits well if m is a prime not too close to a power of 2. With m = 2^k (a power of two), h(k) mod m is just the low k bits of h(k) — and if your hash has weak avalanche on its low bits, you cluster catastrophically. Many production hash maps use m = 2^k for fast bit-mask indexing but compensate by using a hash function with strong low-bit avalanche (e.g., CPython’s dict uses a perturbation scheme; SwissTable uses the high 7 bits of the hash separately as a metadata “tag”). If you control both, prefer m prime; if m must be 2^k, ensure the hash diffuses to the low bits.

9.2 Forgetting Avalanche on Integer Keys

A common bug: h(k) = k for integer keys, then h(k) mod m for an m that is a small power of two. Sequential keys 0, 1, 2, 3 land in buckets 0, 1, 2, 3 — fine — but then keys m, 2m, 3m, … all collide. If your real input is “user IDs” generated as autoincrementing integers, you may get unlucky. The standard fix: post-mix the integer with one round of MurmurHash3-style mixing (the murmur32_mix function in §7 is exactly this — sometimes called the “fmix32” finalizer). Java’s HashMap does this internally with (h = key.hashCode()) ^ (h >>> 16).

9.3 Adversarial Inputs in Web Servers

Outlined in §3.1 — if user-controlled input is hashed, use SipHash with a process-random key. This is not optional in 2026 for any web-facing service. The 2011-2012 wave of hash-flooding DoS exploits caused emergency patches to most major scripting languages; modern code should not regress.

9.4 Hash Persistence Across Process Restarts

If you hash with a process-random key (Python’s default PYTHONHASHSEED=random), hash("foo") returns different values across runs. Don’t persist these hashes to disk or send them across the wire expecting them to mean the same thing in another process. Use a deterministic hash (xxHash with a fixed seed, or SHA-256) for cross-process consistency.

9.5 Hash Function vs. Hash Code

In Java, Object.hashCode() returns a 32-bit int. The hash table then post-processes this with its own mixing (HashMap.hash()). It is a frequent bug to override hashCode() with a poor implementation (e.g., return name.length()) — your table works but performance collapses to O(n). The Effective Java rule: combine all equality-relevant fields into the hash code, e.g., Objects.hash(field1, field2, …).

9.6 Hash Function Mismatch with equals

The contract: a.equals(b) ⇒ a.hashCode() == b.hashCode(). The reverse direction is not required (collisions are allowed). Violating the forward direction breaks the table — two equal objects map to different buckets, and a get after a put returns null. This is the most common Java/Python hash-table bug.

9.7 Mutable Keys

Never mutate a key after inserting it. The hash changes; the entry becomes lost in the wrong bucket. Languages either prevent this (Python raises TypeError: unhashable type: 'list') or trust the programmer (Java lets you do it and silently breaks). Hash Table §10.1 discusses this in more depth.

9.8 Confusing “Hash” and “Encryption”

hash(password) is not encryption. Hashes are one-way; encryption is reversible. And — critically — don’t use a fast hash like SipHash for passwords. Password storage requires a slow hash designed to resist brute force: Argon2, scrypt, bcrypt, or PBKDF2. A SipHash of a password can be brute-forced at billions per second on a GPU; an Argon2id of the same password takes seconds per attempt by design. See Password Hashing for the full discussion.

10. Diagram — The Hash Function Pipeline

flowchart LR
  K[Input key bytes] --> R[Read bytes into state register]
  R --> M{Mixing rounds}
  M -->|multiply by prime| M1[state ⊕= rot rotate state]
  M1 -->|XOR shifts| M2[state *= prime2]
  M2 -->|finalization| F[fmix avalanche pass]
  F --> H["64-bit hash output"]
  H --> IDX["bucket = h mod m"]
  IDX --> B[Bucket index in 0,m]

What this diagram shows. A typical non-cryptographic hash function processes input through a series of mixing rounds — each combining a multiply by a carefully-chosen large odd constant, a bitwise rotation, and an XOR. The final finalization step (“fmix” in MurmurHash terminology) ensures the output avalanches: any input bit affects approximately half the output bits. The final mod m step reduces the 64-bit hash to a bucket index in [0, m). The entire pipeline is engineered to take a few cycles per byte while passing statistical randomness tests like SMHasher.

11. Common Interview Problems

Problem	Connection
Design a hash function for strings	This note’s §6 polynomial hash
Implement a hash map from scratch	Combines this note + Hash Table
Detect duplicate URLs in a stream	Bloom Filter backed by a strong hash function
Distribute keys across N servers	Consistent Hashing uses a strong hash to place keys on the ring
Rolling hash for substring matching	Rabin-Karp / String Hashing — polynomial hash with sliding window
Avoid hash flooding in a web server	Use SipHash with random per-process key

These are not “hash-function-design” problems literally — they are applications where the choice of hash function determines whether your O(1)/O(log n) algorithm holds in practice.

12. Open Questions

• Is the gap between “universal” (2-independent) and 5-independent hashing visible in practical benchmarks of linear probing on real (non-adversarial) data, or only in adversarial constructions?
• Will hardware-accelerated cryptographic hashes (Intel SHA-NI, ARM v8 SHA extensions) close the speed gap to the point where SHA-256 becomes practical for hash tables? As of 2026 the gap is still ~10×; SipHash remains the right default.
• Cuckoo hashing requires near-perfectly random hashes for its theoretical bounds; how robust is absl::flat_hash_map’s SwissTable to weakly random hashes in practice?

13. See Also

• Hash Table — the data structure that consumes hash functions
• HyperLogLog — cardinality estimation that depends on uniform, avalanching hashes; its 1.04/√m error bound assumes the leading bits of hash(x) behave like fair coin flips (see HLL §9.2)
• Bloom Filter — uses multiple independent hashes
• Consistent Hashing — distributed hashing across machines
• String Hashing — polynomial hashing for substring problems
• Rabin-Karp — rolling hash for string matching
• Cuckoo Hashing — needs strong hash independence
• Skip List — alternative randomized data structure with hashing-like analysis
• Big-O Notation
• SWE Interview Preparation MOC