Hashing
Algorithms

What is a hash function?

A hash function h(k) maps keys from a universe U to a fixed-size set of integers {0, 1, ..., m-1}, where m is the table size.

Desirable properties

• Deterministic — the same key always produces the same hash value
• Uniform distribution — keys spread evenly across the output range to minimise collisions
• Efficiency — computing the hash should be O(1) or near-constant time
• Avalanche effect — a small change in input produces a large change in output
• Minimised collisions — different keys should map to different indices as often as possible

Formula

h(k) = k mod m

The simplest hash function. The key k is divided by the table size m, and the remainder is the hash value.

Choosing m

• Avoid powers of 2 — k mod 2^p uses only the lowest p bits, ignoring high-order information
• Avoid powers of 10 — same issue for decimal-encoded keys
• Prefer primes — a prime m not close to a power of 2 gives good distribution
• Example: for ~2000 slots, m = 2003 (prime) is better than m = 2048

Example

Keys: 56, 72, 129, 183, 245
m = 7

h(56)  = 56  mod 7 = 0
h(72)  = 72  mod 7 = 2
h(129) = 129 mod 7 = 3
h(183) = 183 mod 7 = 1
h(245) = 245 mod 7 = 0  ← collision with 56

Multiplication method

h(k) = ⌊m × (k × A mod 1)⌋

Where A is a constant in (0, 1). Knuth recommends A ≈ (√5 − 1) / 2 ≈ 0.6180339887.

• Works well with any table size m — no need for primes
• Extracts information from all bits of the key
• Easy to implement with fixed-point arithmetic

Universal hashing

Choose h randomly from a family of hash functions at runtime. A family H is universal if for any two distinct keys x ≠ y:

Pr[h(x) = h(y)] ≤ 1/m

Carter-Wegman family

h_a,b(k) = ((a × k + b) mod p) mod m

Where p is a prime larger than the universe, a ∈ {1, ..., p-1}, b ∈ {0, ..., p-1}.

Each table slot holds a pointer to a linked list. All keys that hash to the same index are stored in that list.

Performance

α = n/m is the load factor.

Trade-offs

• Simple to implement; deletion is straightforward
• Load factor can exceed 1 — table never "fills up"
• Cache-unfriendly due to pointer chasing
• Extra memory for pointers (8 bytes each on 64-bit)

Concept

All elements stored directly in the table array. On collision, probe the next slot in sequence until an empty slot is found.

h(k, i) = (h'(k) + i) mod m

Primary clustering

Contiguous blocks of occupied slots grow and merge, increasing average probe lengths. A cluster of size k has probability (k+1)/m of growing on the next insert.

Example

Insert 56, 72, 129, 183, 245
m = 7,  h(k) = k mod 7

h(56)  = 0 → slot 0 ✓
h(72)  = 2 → slot 2 ✓
h(129) = 3 → slot 3 ✓
h(183) = 1 → slot 1 ✓
h(245) = 0 → slot 0 full
             slot 1 full
             slot 2 full
             slot 3 full
             slot 4 ✓

Key 245 required 4 probes due to the cluster at slots 0–3.

Probe sequence

h(k, i) = (h'(k) + c₁·i + c₂·i²) mod m

Common choice: c₁ = 0, c₂ = 1, giving h(k, i) = (h'(k) + i²) mod m.

Advantages over linear probing

• Eliminates primary clustering — probes jump over occupied runs
• Still has reasonable cache performance for small probe distances

Caveat

Quadratic probing does not guarantee visiting all slots. To guarantee a full cycle: m must be prime, or m must be a power of 2 with c₁ = c₂ = 1/2.

Secondary clustering

Keys that hash to the same initial slot follow the same probe sequence. This is secondary clustering — less severe than primary clustering but still suboptimal.

Requirements for h₂

• h₂(k) ≠ 0 for all k — otherwise the probe sequence never advances
• h₂(k) must be coprime to m — ensures the full table is probed
• Common: h₂(k) = 1 + (k mod (m - 1)) with m prime

Performance comparison

Load factor α = n / m

Rehashing

When α exceeds a threshold, allocate a new table (typically 2m or next prime > 2m), then re-insert every element.

Rehash triggered: α > 0.75
1. Allocate new table of size 2m
2. For each entry in old table:
     compute new_index = h(key) mod 2m
     insert into new table
3. Free old table

Most implementations also shrink the table when α drops below ~0.25 to reclaim memory.

FKS scheme (Fredman, Komlos, Szemeredi, 1984)

Two-level hashing with O(n) space and O(1) worst-case lookup.

Level 1: h₁ maps n keys into m = n slots
         Some slots have collisions (sⱼ keys)

Level 2: For each bucket j with sⱼ keys,
         use secondary table of size sⱼ²
         Choose h₂ⱼ from universal family
         → guaranteed collision-free

Space analysis

Total space across all secondary tables is O(n) in expectation when m = n at level 1. The sⱼ² sizes sound wasteful, but the sum of squares stays linear because the level-1 hash distributes keys well.

Use cases

• Compilers — keyword recognition
• Network routers — forwarding lookup tables
• Read-only dictionaries — build time amortised over millions of lookups

Construction algorithms

Theoretical lower bound: ~1.44 bits per key. Modern algorithms approach this limit.

Practical use cases

The problem

Standard hash(key) mod n breaks when n (number of servers) changes — nearly all keys remap, causing a rehashing storm.

The ring

Map both keys and servers onto a circular hash space [0, 2³²). Each key is assigned to the next server clockwise on the ring.

Adding or removing a node

When server S₄ joins, only the keys between S₃ and S₄ need to move. All other mappings remain unchanged.

• Keys remapped: O(K/n) on average
• hash mod n: remaps O(K) keys

Karger et al. (1997) — backbone of Memcached, DynamoDB, Cassandra, Akamai CDN.

The balance problem

With few physical nodes, ring partitions are uneven. One server may own 60% of the key space while another owns 5%.

Virtual nodes (vnodes)

Each physical server is represented by v virtual nodes spread across the ring. More vnodes = more uniform distribution.

Physical S₁ → S₁_0, S₁_1, S₁_2, ...
Physical S₂ → S₂_0, S₂_1, S₂_2, ...

Benefits

• Load balance — with v = 150, std dev of load drops below 5%
• Heterogeneous capacity — assign more vnodes to more powerful servers
• Smoother rebalancing — departing node's vnodes scatter load across many survivors

Implementations

Properties beyond standard hashing

Common algorithms

SHA-256

Merkle-Damgard construction. Processes input in 512-bit blocks through 64 rounds of mixing.

• Output: 256 bits (32 bytes, 64 hex chars)
• Used in: TLS, Bitcoin, Git, JWT signatures
• Speed: ~500 MB/s with SHA-NI extensions

SHA-256("hello") =
2cf24dba5fb0a30e26e83b2ac5b9e29e
1b161e5c1fa7425e7304362938b62494

BLAKE3

Tree-based Merkle construction. Unlimited parallelism across chunks.

• Output: 256 bits (extendable)
• Speed: ~5 GB/s single-threaded; scales with cores
• Used in: Bao, content-addressable storage, build caches

When to use which

Concept

Two hash functions h₁, h₂ and two tables T₁, T₂. Each key lives in exactly one of its two possible positions.

Insert algorithm

def insert(key):
  if T1[h1(key)] is empty:
    place key there; return
  if T2[h2(key)] is empty:
    place key there; return
  # Evict occupant of T1[h1(key)]
  displaced = T1[h1(key)]
  T1[h1(key)] = key
  # Re-insert displaced into alternate
  # Repeat until stable or cycle → rehash

Properties

Concept

Open addressing with linear probing, but elements are reordered during insertion to equalise probe distances. "Rob from the rich, give to the poor."

Insert rule

If the new key's probe distance exceeds the current occupant's, swap them and continue inserting the displaced element.

def insert(key):
  dist, idx = 0, h(key)
  while table[idx] is occupied:
    if dist > probe_dist(table[idx]):
      swap(key, table[idx])
      dist = probe_dist(table[idx])
    idx = (idx + 1) % m
    dist += 1
  table[idx] = key

Benefits

Concept

Standard hashes make similar inputs diverge. LSH does the opposite: similar items hash to the same bucket with high probability.

Common LSH families

Applications

• Approximate nearest-neighbour search in high dimensions
• Near-duplicate web page detection (Google, Bing)
• Audio fingerprinting (Shazam uses a related technique)
• Genome sequence alignment (fast seed generation)

Formal definition

A family H is (d₁, d₂, p₁, p₂)-sensitive if close points (dist ≤ d₁) collide with probability ≥ p₁ and far points (dist ≥ d₂) collide with probability ≤ p₂.

Key takeaways

• Hash functions must be deterministic, efficient, and distribute keys uniformly
• Division method requires careful choice of m; multiplication method is more robust
• Chaining tolerates high load factors; open addressing is cache-friendly but load-sensitive
• Double hashing eliminates clustering; cuckoo hashing guarantees worst-case O(1) lookup
• Robin Hood hashing bounds probe-distance variance for predictable performance
• Consistent hashing with vnodes is the backbone of distributed storage
• Cryptographic hashes add pre-image and collision resistance — essential for security
• Perfect hashing achieves zero collisions for static key sets
• LSH inverts the hash contract — similar items hash together for ANN search
• Real-world hash tables combine open addressing with SIMD and careful engineering

Recommended reading