Hash Tables

The abstract interface

A dictionary (also called map, associative array) supports three core operations on key-value pairs:

• INSERT(k, v) — associate value v with key k
• SEARCH(k) — return the value for key k, or report absent
• DELETE(k) — remove the pair with key k

Naive implementations

When keys are small integers

If every possible key is in {0, 1, ..., U-1} and U is small, store values in a plain array T[0..U-1].

T[k] = v       // INSERT
T[k]           // SEARCH
T[k] = NIL     // DELETE

All operations are O(1) worst case.

The problem

• When U is large (e.g. 64-bit integers, strings), allocating an array of size U is infeasible
• When only n << U keys are used, most of the array is wasted
• Solution: hash the key into a smaller index range [0, m-1] where m = O(n)

Requirements

A hash function h(k) maps a key from universe U to an index in {0, 1, ..., m-1}.

• Deterministic — same key always produces the same index
• Uniform distribution — keys spread evenly across slots
• Fast to compute — ideally O(1) or O(|key|)

Division method

h(k) = k mod m

Simple but sensitive to choice of m. Avoid powers of 2. Choose m as a prime not close to a power of 2.

Multiplication method

h(k) = floor(m * (k * A mod 1))
// where 0 < A < 1
// Knuth: A = (sqrt(5) - 1) / 2 ≈ 0.618

Practical hash functions

The adversary problem

Any single deterministic hash function has a worst case: an adversary can craft n keys that all hash to the same slot, degrading every operation to O(n).

Universal hash families

A family H is universal if for any two distinct keys x ≠ y:

Pr[h(x) = h(y)] ≤ 1/m
// where h chosen randomly from H

Carter-Wegman construction

For prime p ≥ |U|:

h_{a,b}(k) = ((a * k + b) mod p) mod m
// a ∈ {1, ..., p-1},  b ∈ {0, ..., p-1}

Properties

Stronger families

• k-independent — any k distinct keys hash independently
• 2-independent ≈ universal; 5-independent suffices for linear probing to achieve O(1) expected
• Tabulation hashing — 3-independent, fast, practical; suffices for chaining and cuckoo hashing

Collision resolution with linked lists

Each slot T[i] points to a linked list of all elements whose keys hash to i.

Operations

• INSERT — compute h(k), prepend to list at T[h(k)] — O(1)
• SEARCH — compute h(k), traverse list at T[h(k)] — O(chain length)
• DELETE — search then unlink — O(chain length)

Performance

With load factor α = n/m and a good hash function:

• Expected chain length = α
• Expected search time = O(1 + α)
• If n = O(m), all operations are O(1) expected

Open addressing principle

All elements stored directly in the table array. No pointers, no linked lists. On collision, probe a sequence of alternative slots until an empty one is found.

Linear probing

h(k, i) = (h'(k) + i) mod m
// for i = 0, 1, 2, ...

Slots checked sequentially. Cache-friendly but suffers from primary clustering — runs of occupied slots grow and merge.

Quadratic probing

h(k, i) = (h'(k) + c1*i + c2*i²) mod m

Spreads probes more than linear. Avoids primary clustering but can cause secondary clustering.

Comparison

Two independent hash functions

h(k, i) = (h1(k) + i * h2(k)) mod m
// h2(k) must never return 0
// Common: h2(k) = 1 + (k mod (m - 1)), m prime

Why it works

• Each key generates a distinct probe sequence — no clustering
• Approximates the ideal of uniform probing
• Expected probes for unsuccessful search: 1 / (1 - α)
• Expected probes for successful search: (1/α) * ln(1 / (1 - α))

Probe count at various load factors

Probing comparison

Load factor

α = n / m
// n = stored elements, m = table capacity

• Chaining: α can exceed 1.0. Performance degrades linearly: O(1 + α)
• Open addressing: α must stay below 1.0. Performance degrades non-linearly

Amortised O(1) argument

Maintain α ≤ c for constant c < 1 by doubling when threshold exceeded:

• Each insertion is O(1) expected
• Resizing costs O(n) but happens only every O(n) insertions
• Amortised cost per insertion: O(1)

Space-time trade-off

Expected longest chain (chaining)

For n keys in m slots with universal hashing, the expected longest chain is Θ(log n / log log n).

When to resize

Typically when α exceeds a threshold (e.g. 0.75). Some implementations also shrink when α drops below a lower bound (e.g. 0.25).

The rehashing process

1. Allocate new table of size m' = 2m (or next prime > 2m)
2. For every element, compute h(k) mod m' and insert into the new table
3. Free the old table

Cost: O(n) — must rehash every element because the modulus changed.

Incremental rehashing (Redis approach)

• Maintain two tables simultaneously
• On each operation, migrate a few keys from old to new
• Lookups check both tables during the transition
• After all keys migrated, free the old table

Growth strategies

Equalising probe distances

A variant of open-addressing (typically linear probing) where the probe distance of each element is tracked.

The Robin Hood rule

During insertion, if the new element's probe distance exceeds the occupant's, swap them — "steal from the rich, give to the poor."

Insert key K with probe distance d:
  While slot is occupied:
    If d > occupant's probe distance:
      Swap K with occupant
      Continue inserting displaced element
    Advance to next slot, d++
  Place K in empty slot

Benefits

Worst-case O(1) lookup

Uses two hash functions h1 and h2 and two tables T1, T2.

• SEARCH: check T1[h1(k)] and T2[h2(k)] — exactly 2 lookups, always
• DELETE: check both locations, remove — O(1) worst case

Insertion algorithm

Insert key k:
  If T1[h1(k)] empty -> place k, done
  Evict x from T1[h1(k)], place k
  If T2[h2(x)] empty -> place x, done
  Evict y from T2[h2(x)], place x
  ... repeat (max iteration limit)
  If cycle -> rehash with new functions

Properties

Bounded neighbourhood

Each slot has a "neighbourhood" of H consecutive slots (typically H = 32). An element hashing to slot i must reside within i to i + H - 1.

Lookup

Check all H slots in the neighbourhood — a single cache line or two. Uses a bitmap per slot to record which neighbours are occupied by elements hashing to that slot.

Insertion

1. Find an empty slot (may be beyond the neighbourhood)
2. Repeatedly swap elements to move the empty slot closer, into the neighbourhood
3. If no swap chain can bring the empty slot within range, resize

Advantages over linear probing

Google's flat_hash_map

Open-addressing with linear probing, but with SIMD-accelerated metadata lookups. Used in Abseil (absl::flat_hash_map) and Rust's hashbrown.

Architecture

• Table divided into groups of 16 slots
• Each group has a 16-byte control byte array (one byte per slot)
• Control byte: top 7 bits of hash (H2) + 1 bit for empty/deleted/full
• Probe sequence walks over groups, not individual slots

SIMD-powered lookup

1. h1 = hash(key)
2. group = h1 mod num_groups
3. H2 = top 7 bits of hash
4. Load 16 ctrl bytes → SIMD register
5. Compare all 16 vs H2 in ONE instr
   (SSE2 _mm_cmpeq_epi8)
6. Bitmask → check only matches

Performance characteristics

Zero collisions by construction

A perfect hash function maps n keys to m slots with no collisions. A minimal perfect hash uses m = n.

FKS two-level scheme

Level 1: Hash n keys into m primary slots using a universal hash function.

Level 2: For each primary slot j with n_j keys, build a secondary table of size n_j² with its own universal hash function.

Level 1:  h1(k) → primary slot j
Level 2:  h_j(k) → position in
          secondary table for slot j

Space and time

Practical tools

The problem

Concurrent reads and writes require synchronisation. A global lock serialises all operations and destroys throughput.

Lock striping (Java ConcurrentHashMap)

• Partition the table into segments (e.g. 16)
• Each segment has its own lock
• Operations on different segments proceed in parallel
• Java 8+: replaced segments with per-bucket CAS + synchronized on bucket head

Lock-free approaches

• RCU — readers lock-free; writers copy, modify, swap pointer
• Harris-style — CAS-based insertion/deletion on chains
• Cliff Click's NonBlockingHashMap — lock-free open addressing via CAS

Comparison

Applications

Limitations

Key takeaways

• Hash tables provide O(1) expected time for insert, search, delete — the fastest dictionary for point queries
• Hash function choice determines distribution quality and security against adversarial inputs
• Separate chaining is simple but cache-unfriendly; open addressing keeps data contiguous
• Robin Hood hashing equalises probe distances; cuckoo hashing guarantees O(1) worst-case lookup
• Swiss Table (SIMD + linear probing) is the current state of the art
• Perfect hashing achieves O(1) worst case for static key sets
• Load factor management and amortised resizing keep operations constant-time
• Thread safety requires lock striping, CAS, or RCU — never a single global lock

Recommended reading