On this page

Hash Tables

Hash Tables & Hashing in Depth — from the hash function to the SIMD probe.

Hash tables are the single most important data structure in practical programming. They power dictionaries, sets, caches, database indexes, routers, and virtually every system that needs fast key-value access. The average lookup time they provide is so ubiquitous that most programmers take it for granted — but understanding how they work under the hood is critical for knowing when that guarantee breaks down.

This lesson closes the core of Module 1 (module index). It covers the whole stack: what makes a hash function good, the collision strategies and the mathematics of their probe counts, the modern designs (Robin Hood, cuckoo, Swiss tables), how Python, Java, C++ and V8 actually implement their maps, how attackers break hash tables and how languages defend them, and the interview patterns built on top. Approximate cousins — Bloom filters and count-min sketches — have their own page, Probabilistic Data Structures.

Why hash tables exist

Searching a sorted array costs ; searching a balanced tree costs the same. Both rely on comparisons, and comparisons is the information-theoretic floor for comparison-based search. Hashing escapes that floor by not comparing at all: it computes where a key should be. Turn the key into an integer, reduce it to an array index, look there. If the computation spreads keys evenly, the expected number of keys sharing a slot is a constant, and lookup is on average regardless of .

The idea appeared almost simultaneously at IBM in 1953–54. Hans Peter Luhn wrote an internal memo describing buckets with chained overflow; Gene Amdahl, Elaine McGraw, Nathaniel Rochester and Arthur Samuel used open addressing with linear probing in an assembler for the IBM 701. The name "hashing" took another decade to reach print (Robert Morris's 1968 CACM survey "Scatter Storage Techniques" still preferred "scatter storage"). Donald Knuth's 1963 analysis of linear probing — the expected-probe formulas below — is often called the first analysis of an algorithm in the modern sense.

Seventy years later hash tables are everywhere: every Python object's attributes live in one, every JavaScript Map is one, compilers keep symbol tables in them, databases build them for hash joins and hash indexes, routers keep flow tables in them, and distributed systems spread data across machines with their big brother, consistent hashing. The is real but conditional — on a good hash function, a bounded load factor, and an adversary who cannot choose your keys. This page is about those three conditions.

Pattern triggers

If the problem says… / has…Think ofWhy
"have I seen this before?", "duplicate", "contains"Hash set membership
"pair that sums to target" (unsorted), "complement"Hash map value → indexLook up target − x as you go
"count", "frequency", "most common", "top k"Hash map value → count (+ heap or bucket sort)Counting is a map from key to integer
"group by", "anagrams", "same pattern"Hash map canonical key → listEqual canonical forms collide on purpose
"subarray sum equals k", "divisible by k", "equal 0s and 1s"Prefix sum + hash map (Prefix Sums)A subarray is a difference of two prefixes
"longest consecutive", "sequence without sorting"Hash set + start-of-run checkEach run is walked once from its smallest element
"O(1) get and put", "evict least recently used"Hash map + doubly linked list (LRU capstone)Map finds, list orders
"insert, delete, get random in O(1)"Hash map value → index + arraySwap-with-last deletion keeps the array dense
"bijection", "isomorphic", "one-to-one mapping"Two hash maps (forward and backward)Both directions must be consistent
"within distance k", "nearby duplicate"Hash map value → last index or a sliding hash setOnly the last occurrence matters
"substring equality", "many string comparisons"Polynomial rolling hash (String Algorithms)Compare hashes in
"approximately", "probably in the set", "memory is tight"Bloom filter / count-min sketch (Probabilistic Data Structures)Trade exactness for space
"servers join and leave", "minimise remapping"Consistent or rendezvous hashing (Consistent Hashing)Changing moves only of keys

How Hash Tables Work

A hash table maps keys to values through three components:

  1. Hash function: Converts a key into an integer (the hash code)
  2. Array: Stores key-value pairs at positions determined by the hash
  3. Collision resolution: Handles the inevitable case where two keys hash to the same position
graph LR
    K1["key: 'alice'"] --> H["Hash Function<br/>h('alice') = 2"] --> A2["Array[2]"]
    K2["key: 'bob'"] --> H2["Hash Function<br/>h('bob') = 5"] --> A5["Array[5]"]
    K3["key: 'carol'"] --> H3["Hash Function<br/>h('carol') = 2"] --> A2
    style A2 fill:#f96

'alice' and 'carol' hash to the same index — a collision.

Collisions are not a defect of bad hash functions; they are unavoidable. With slots and keys, the birthday paradox says a collision becomes more likely than not once : with a million slots, about 1,178 keys already give a 50% chance that two share a slot. Every hash table is therefore a hash function plus a collision strategy, and the strategy determines the performance profile far more than the function does — as long as the function is not actively bad.

It helps to separate two steps that are often blurred:

  1. Hashing: key → a full-width integer (32 or 64 bits). This is __hash__, hashCode, std::hash.
  2. Reduction: integer → index in . Usually h mod m (prime ) or h & (m − 1) (power-of-two ), or Lemire's multiply-high trick (h * m) >> 32. Power-of-two masks are fast but use only the low bits of the hash, so a weak hash with poor low bits (identity on integers, Java String.hashCode on short strings) needs an extra mixing step first. That is why Java spreads h ^ (h >>> 16) and CPython perturbs its probe sequence with the high bits.

Hash Functions

A good hash function satisfies three properties:

  1. Deterministic: Same input always produces same output
  2. Uniform distribution: Outputs are spread evenly across the range
  3. Efficiency: Fast to compute

Hash Function Examples

TypeScript:

// Simple string hash (djb2 algorithm)
function hash(key: string, tableSize: number): number {
  let h = 5381;
  for (let i = 0; i < key.length; i++) {
    h = ((h << 5) + h + key.charCodeAt(i)) & 0xffffffff;
  }
  return Math.abs(h) % tableSize;
}

// Integer hash (multiply-shift)
function hashInt(key: number, tableSize: number): number {
  // Knuth's multiplicative hash
  const A = 2654435769; // 2^32 * (sqrt(5) - 1) / 2
  return ((key * A) >>> 0) % tableSize;
}

Correction: multiplicative hashing takes the high bits

hashInt above has two problems. First, key * A is computed in floating point; for keys above about the product exceeds and low-order bits are lost before >>> 0 truncates. Use Math.imul(key, 0x9E3779B9) for an exact 32-bit product. Second, Knuth's multiplicative method keeps the top bits of the product, not the product modulo the table size: the low bits of are as poorly mixed as the low bits of (if is even, so is ). The correct form for a table of slots is Math.imul(key, 0x9E3779B9) >>> (32 - b). The 64-bit version is shown in "Integer hashing" below.

Python:

def hash_string(key: str, table_size: int) -> int:
    """djb2 hash function."""
    h = 5381
    for char in key:
        h = ((h << 5) + h + ord(char)) & 0xFFFFFFFF
    return h % table_size

# Python's built-in hash() is already excellent:
# hash("hello") → deterministic integer
# Use hash(key) % table_size for indexing

A nuance on that last comment: Python's hash() for str and bytes is a keyed SipHash and is excellent — but "deterministic" only within one process: the key is randomised at interpreter start unless PYTHONHASHSEED is set, so hash("hello") differs between runs. For int, hash(n) is simply n reduced modulo the Mersenne prime (with the quirk hash(-1) == -2, because -1 is the C-level error code). An identity hash is fine for CPython's own dict, which perturbs its probes with the high bits, but hash(key) % table_size with consecutive or strided integer keys inherits all their regularity.

WARNING

Never use a hash function as a security mechanism. Cryptographic hash functions (SHA-256, bcrypt) are designed for security. Hash table hash functions are designed for speed and distribution — they are not collision-resistant against an adversary.

Hash Function Quality

A poor hash function causes clustering — many keys landing in the same bucket. This degrades operations to . Example of a terrible hash function: h(key) = len(key) % table_size — all strings of the same length collide.

What "good" means, precisely

"Uniform distribution" is not quite the right target, because any fixed function has bad inputs: by pigeonhole, at least keys from the universe map to some single slot, and an adversary who knows the function can pick them. Two precise notions are used instead.

  • Avalanche / statistical quality (for non-adversarial data): flipping any single input bit should flip each output bit with probability about ½. Structured inputs — sequential IDs, pointers aligned to 16 bytes, strings sharing long prefixes — then spread like random ones. Test suites such as SMHasher measure this.
  • Universality (for worst-case guarantees): choose the function at random from a family such that for any two distinct keys, (Carter and Wegman, 1979). Then for any fixed set of keys — even adversarially chosen, as long as the adversary does not see — the expected chain length is at most (CLRS Theorem 11.3). Keyed hashes like SipHash are the practical descendant of this idea: the random key plays the role of choosing .

And speed matters: a hash table that spends 50 ns hashing a key to save one 5 ns probe has lost. The functions below are all a few cycles per byte or per word.

Integer hashing: multiplicative, Fibonacci and splitmix64

Multiplicative (Fibonacci) hashing. Multiply by a large odd constant and keep the top bits: for a table of slots. With (the golden ratio's reciprocal scaled to 64 bits) this is Fibonacci hashing, recommended by Knuth (TAOCP Vol. 3, §6.4) because consecutive keys land far apart. Multiplication propagates low input bits upward, and the top bits of the product depend on all input bits, which is why the top bits are the ones to keep. With a random odd this multiply-shift scheme is also approximately universal (Dietzfelbinger, Hagerup, Katajainen and Penttonen, 1997). Computed for an 8-slot table ():

keysFibonacci hash, top 3 bitskey mod 8
1, 2, 3, 4, 5, 6, 7, 84, 1, 6, 3, 0, 5, 2, 71, 2, 3, 4, 5, 6, 7, 0
0, 8, 16, 24, 32, 40, 48, 560, 7, 7, 6, 6, 5, 5, 40, 0, 0, 0, 0, 0, 0, 0

Both handle consecutive keys well, but for strided keys (multiples of 8 — think aligned pointers or IDs allocated in blocks) mod 8 puts everything in slot 0, while the multiplicative hash still uses five of the eight slots.

splitmix64 is the finaliser from Sebastiano Vigna's SplitMix64 generator (derived from Steele, Lea and Flood's SplittableRandom, OOPSLA 2014): add the golden-ratio constant, then three xor-shift-multiply rounds. Every input bit affects every output bit, it is a bijection on 64-bit integers (no two keys collide before reduction), and it costs a handful of cycles. It is the standard fix for integer keys in competitive programming (below) and a good default whenever you need to hash integers yourself.

MASK64 = (1 << 64) - 1

def splitmix64(x: int) -> int:
    x = (x + 0x9E3779B97F4A7C15) & MASK64
    x = ((x ^ (x >> 30)) * 0xBF58476D1CE4E5B9) & MASK64
    x = ((x ^ (x >> 27)) * 0x94D049BB133111EB) & MASK64
    return x ^ (x >> 31)

def fibonacci_hash(x: int, bits: int) -> int:
    """Top `bits` bits of x * floor(2^64 / golden ratio)."""
    return ((x * 11400714819323198485) & MASK64) >> (64 - bits)

assert splitmix64(0) == 0xE220A8397B1DCDAF
assert splitmix64(1) == 0x910A2DEC89025CC1
assert [fibonacci_hash(x, 3) for x in range(1, 9)] == [4, 1, 6, 3, 0, 5, 2, 7]
assert [fibonacci_hash(x, 3) for x in range(0, 64, 8)] == [0, 7, 7, 6, 6, 5, 5, 4]
# splitmix64 is a bijection: no collisions among 100k distinct inputs.
assert len({splitmix64(i) for i in range(100_000)}) == 100_000
print("integer hashing OK")

String hashing: polynomial, FNV-1a, MurmurHash3, SipHash

Polynomial hashing. Treat the string as digits in base : , evaluated left to right by Horner's rule h = h * B + c. Java's String.hashCode is exactly this with and (overflowing int). djb2 above is with a starting value of 5381. Polynomial hashes are cheap and rollable (the hash of a sliding window updates in , the basis of Rabin–Karp below), but with a fixed public base they are trivially attackable: in Java, "Aa".hashCode() == "BB".hashCode() == 2112, so every string built from blocks of Aa/BB — strings — shares one hash. That observation powered the 2011 hash-flooding attacks.

FNV-1a (Fowler, Noll, Vo): start from an offset basis, and for each byte XOR it in, then multiply by the FNV prime. The 32-bit constants are basis 0x811C9DC5 and prime 16777619; the 64-bit ones are 0xCBF29CE484222325 and 0x100000001B3. FNV-1a is tiny, decent on short keys and widely used in non-adversarial settings (it is the hash in the implementations on this page). For "hello", FNV-1a 32 is 0x4F9F2CAB and FNV-1a 64 is 0xA430D84680AABD0B.

MurmurHash3 (Austin Appleby, 2011) processes 4 or 16 bytes per step with multiply-rotate-multiply mixing and ends with a strong finaliser (fmix32: xor-shift by 16, multiply by 0x85EBCA6B, xor-shift 13, multiply by 0xC2B2AE35, xor-shift 16). It has excellent avalanche, is fast on long keys, and is used by Guava, Cassandra's default partitioner (Murmur3Partitioner) and many Bloom filter implementations. xxHash and wyhash/rapidhash are faster modern alternatives in the same niche. None of these are designed to resist an attacker who can find collisions; seed-independent multicollisions are known for MurmurHash2 and 3 and CityHash (shown at 29C3, below).

SipHash (Jean-Philippe Aumasson and Daniel J. Bernstein, "SipHash: a fast short-input PRF", INDOCRYPT 2012) is a keyed pseudorandom function: given a secret 128-bit key, its outputs are computationally indistinguishable from random to someone who does not know the key, so an attacker cannot precompute collisions. It is slower than Murmur on long inputs but fast on the short keys typical of hash tables. Python (since 3.4, PEP 456; SipHash-1-3 since 3.11), Rust's default HashMap hasher (SipHash-1-3), Ruby, Perl and the Linux kernel's network hashing (siphash.h) use it, each with a random key chosen at process or boot start.

def java_string_hash(s: str) -> int:
    """Java's String.hashCode: polynomial base 31, wrapping 32-bit signed int."""
    h = 0
    for ch in s:
        h = (31 * h + ord(ch)) & 0xFFFFFFFF
    return h - (1 << 32) if h >= 1 << 31 else h

def fnv1a_32(data: bytes) -> int:
    h = 0x811C9DC5
    for b in data:
        h = ((h ^ b) * 0x01000193) & 0xFFFFFFFF
    return h

def fnv1a_64(data: bytes) -> int:
    h = 0xCBF29CE484222325
    for b in data:
        h = ((h ^ b) * 0x100000001B3) & 0xFFFFFFFFFFFFFFFF
    return h

assert java_string_hash("Aa") == java_string_hash("BB") == 2112
# 2^3 = 8 distinct strings, one hash: the seed of a hash-flooding attack.
from itertools import product
blocks = ["".join(p) for p in product(["Aa", "BB"], repeat=3)]
assert len(set(blocks)) == 8 and len({java_string_hash(s) for s in blocks}) == 1
assert fnv1a_32(b"hello") == 0x4F9F2CAB
assert fnv1a_64(b"hello") == 0xA430D84680AABD0B
assert fnv1a_64(b"") == 0xCBF29CE484222325        # empty input = offset basis
print("string hashing OK")

Hash flooding and keyed hashes

In 2003 Scott Crosby and Dan Wallach ("Denial of Service via Algorithmic Complexity Attacks", USENIX Security) showed that sending inputs that all collide turns a hash table's into per operation and overall. At 28C3 (December 2011), Alexander Klink and Julian Wälde demonstrated it against PHP, Java, ASP.NET, Python and Ruby web frameworks: a single POST request of a few megabytes, full of form-field names with equal hashes, could occupy a CPU core for minutes because the framework parsed the fields into a hash map. Vendors responded with randomised seeds for their existing hash functions. A year later, at 29C3 (December 2012), Aumasson, Bernstein and Martin Boßlet presented "Hash-flooding DoS reloaded: attacks and defenses", showing that seeds do not help when the function has seed-independent collisions — they produced such multicollisions for MurmurHash2, MurmurHash3 and CityHash, and showed that Python's randomised hash of the time leaked its seed — and proposed SipHash as the fix. Languages moved to SipHash over the following years (Ruby 2.0 in 2013 was early; Python 3.4 in 2014 via PEP 456; Rust used it from its first stable release in 2015).

This is why the defaults differ by language:

  • Keyed hash by default (Python, Rust, Ruby, Perl, V8's string hash seed): every process gets a random key, so attackers cannot predict collisions, and iteration order of hash-based containers can differ between runs (Python set iteration of strings, for example).
  • Unkeyed hash + structural defence (Java): String.hashCode is part of the language specification and cannot change, so Java 8 bounded the damage instead: long chains are converted to balanced trees, making the worst case per operation for comparable keys.
  • Unkeyed hash, no defence (C++ std::hash in common implementations is the identity for integers and a fixed hash for strings): fine for trusted data, exploitable for untrusted data — see "Anti-hash tests" below.

Collision Resolution

Method 1: Separate Chaining

Each bucket stores a linked list (or another collection) of entries that hash to that index.

graph TD
    subgraph "Hash Table with Chaining"
        A0["[0]: empty"]
        A1["[1]: empty"]
        A2["[2]: alice→42"] --> A2b["carol→17"]
        A3["[3]: empty"]
        A4["[4]: dave→99"]
        A5["[5]: bob→73"]
    end

TypeScript:

class HashTableChaining<V> {
  private buckets: [string, V][][];
  private count: number = 0;
  private capacity: number;

  constructor(capacity = 16) {
    this.capacity = capacity;
    this.buckets = Array.from({ length: capacity }, () => []);
  }

  private hash(key: string): number {
    let h = 5381;
    for (let i = 0; i < key.length; i++) {
      h = ((h << 5) + h + key.charCodeAt(i)) & 0xffffffff;
    }
    return Math.abs(h) % this.capacity;
  }

  set(key: string, value: V): void {
    const idx = this.hash(key);
    const bucket = this.buckets[idx];

    for (const entry of bucket) {
      if (entry[0] === key) {
        entry[1] = value;
        return;
      }
    }

    bucket.push([key, value]);
    this.count++;

    if (this.count / this.capacity > 0.75) {
      this.resize();
    }
  }

  get(key: string): V | undefined {
    const idx = this.hash(key);
    for (const [k, v] of this.buckets[idx]) {
      if (k === key) return v;
    }
    return undefined;
  }

  delete(key: string): boolean {
    const idx = this.hash(key);
    const bucket = this.buckets[idx];

    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket.splice(i, 1);
        this.count--;
        return true;
      }
    }
    return false;
  }

  private resize(): void {
    const oldBuckets = this.buckets;
    this.capacity *= 2;
    this.buckets = Array.from({ length: this.capacity }, () => []);
    this.count = 0;

    for (const bucket of oldBuckets) {
      for (const [key, value] of bucket) {
        this.set(key, value);
      }
    }
  }
}

Python:

class HashTableChaining:
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.buckets: list[list[tuple[str, any]]] = [[] for _ in range(capacity)]
        self.count = 0

    def _hash(self, key: str) -> int:
        return hash(key) % self.capacity

    def set(self, key: str, value) -> None:
        idx = self._hash(key)
        bucket = self.buckets[idx]

        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return

        bucket.append((key, value))
        self.count += 1

        if self.count / self.capacity > 0.75:
            self._resize()

    def get(self, key: str):
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        return None

    def delete(self, key: str) -> bool:
        idx = self._hash(key)
        bucket = self.buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.count -= 1
                return True
        return False

    def _resize(self) -> None:
        old_buckets = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.count = 0
        for bucket in old_buckets:
            for key, value in bucket:
                self.set(key, value)

These two implementations use a dynamic array per bucket rather than a linked list — a sensible modern choice, since a short array is more cache-friendly than a chain of nodes. Expected cost: with load factor and a hash that behaves randomly, an unsuccessful search examines entries on average and a successful one about (CLRS Theorems 11.1–11.2), so both are .

Trace: chaining with a resize at load 0.75

A 4-bucket table, , resizing (doubling) when the load exceeds 0.75 after an insert. Keys 1, 5, 9, 2, 6, 13 (computed by script):

inserth = key mod capbuckets after insertload n/capresize?
11[[], [1], [], []]1/4 = 0.25no
51[[], [1, 5], [], []]2/4 = 0.50no
91[[], [1, 5, 9], [], []]3/4 = 0.75no (not > 0.75)
22[[], [1, 5, 9], [2], []]4/4 = 1.00yes → cap 8: [[], [1, 9], [2], [], [], [5], [], []]
66[[], [1, 9], [2], [], [], [5], [6], []]5/8 = 0.62no
135[[], [1, 9], [2], [], [], [5, 13], [6], []]6/8 = 0.75no

Two things to notice. Keys 1, 5, 9 were a chain of three in a 4-bucket table because they are congruent mod 4 — the identity hash with a modulus that divides their stride. After doubling, the modulus 8 separates 5 from 1 and 9 (1 and 9 are still congruent mod 8): rehashing does not just make room, it redistributes, because every index changes. With power-of-two tables each old bucket splits into exactly two new buckets, and , depending on one more bit of the hash — Java's HashMap.resize exploits this to split each chain into a "lo" and a "hi" list without recomputing indices from scratch.

Java 8 treeification

Java's HashMap keeps chains as linked lists of Node objects, but when adding a node makes a bin's chain longer than TREEIFY_THRESHOLD = 8, it converts that bin into a red-black tree of TreeNodes — provided the table has at least MIN_TREEIFY_CAPACITY = 64 buckets; below that it simply doubles the table. A tree bin shrinking to UNTREEIFY_THRESHOLD = 6 or fewer nodes during a resize reverts to a list. The source comment explains the thresholds: under random hash codes and the default 0.75 load factor, bin sizes follow a Poisson distribution with mean about 0.5, so a bin of 8 has probability about — trees should essentially never appear except under attack or with a broken hashCode. Within a tree bin, nodes are ordered by hash, then by compareTo if the keys implement Comparable, then by a tie-breaker; with identical hashes and non-comparable keys, a lookup may have to search both subtrees, so the bound really holds only for comparable keys such as String.

Method 2: Open Addressing

All entries are stored in the array itself. When a collision occurs, probe for the next available slot.

Linear Probing: Check index , , , ... (wrapping around). Simple but suffers from primary clustering.

Quadratic Probing: Check , , , , ... Reduces primary clustering but can miss slots.

Double Hashing: Use a second hash function for the probe step: . Best distribution.

TypeScript (Linear Probing):

class HashTableLinearProbe<V> {
  private keys: (string | null)[];
  private values: (V | null)[];
  private capacity: number;
  private count: number = 0;
  private readonly DELETED = "__DELETED__";

  constructor(capacity = 16) {
    this.capacity = capacity;
    this.keys = new Array(capacity).fill(null);
    this.values = new Array(capacity).fill(null);
  }

  private hash(key: string): number {
    let h = 5381;
    for (let i = 0; i < key.length; i++) {
      h = ((h << 5) + h + key.charCodeAt(i)) & 0xffffffff;
    }
    return Math.abs(h) % this.capacity;
  }

  set(key: string, value: V): void {
    if (this.count / this.capacity > 0.5) this.resize();

    let idx = this.hash(key);
    while (this.keys[idx] !== null && this.keys[idx] !== this.DELETED) {
      if (this.keys[idx] === key) {
        this.values[idx] = value;
        return;
      }
      idx = (idx + 1) % this.capacity;
    }

    this.keys[idx] = key;
    this.values[idx] = value;
    this.count++;
  }

  get(key: string): V | undefined {
    let idx = this.hash(key);
    while (this.keys[idx] !== null) {
      if (this.keys[idx] === key) return this.values[idx]!;
      idx = (idx + 1) % this.capacity;
    }
    return undefined;
  }

  delete(key: string): boolean {
    let idx = this.hash(key);
    while (this.keys[idx] !== null) {
      if (this.keys[idx] === key) {
        this.keys[idx] = this.DELETED as any;
        this.values[idx] = null;
        this.count--;
        return true;
      }
      idx = (idx + 1) % this.capacity;
    }
    return false;
  }

  private resize(): void {
    const oldKeys = this.keys;
    const oldValues = this.values;
    this.capacity *= 2;
    this.keys = new Array(this.capacity).fill(null);
    this.values = new Array(this.capacity).fill(null);
    this.count = 0;

    for (let i = 0; i < oldKeys.length; i++) {
      if (oldKeys[i] !== null && oldKeys[i] !== this.DELETED) {
        this.set(oldKeys[i]!, oldValues[i]!);
      }
    }
  }
}

Correction: two bugs in the linear-probing class above

  1. Duplicate keys. set stops at the first tombstone (DELETED) and inserts there, without checking whether the key already exists further along the probe chain. Run by script: two keys with the same home slot ("k1" and "k10" in a 16-slot table), set(a); set(b); delete(a); set(b, 3) leaves two copies of b in the table and count = 2; a later delete(b) removes the first copy and get(b) then returns the stale value 2. The fix: while probing, remember the first tombstone but keep going until you find the key or an empty slot; only then insert, reusing the remembered tombstone.
  2. Tombstones are never cleaned up. count is decremented on delete but tombstones still occupy slots, and the load check ignores them. After 40 insert/delete cycles of distinct keys on a 16-slot table, only 3 slots were still null; once none are, get on a missing key loops forever. The fix: count tombstones in the load check and rebuild the table (at the same size if few live entries remain) when live + tombstones exceeds the threshold.

The four-language implementation later on this page does both. Also note that storing the sentinel as the string "__DELETED__" means a real key with that value is silently treated as deleted; a separate state array avoids that.

Trace: linear probing in an 8-slot table

, no resizing, keys inserted in order 7, 15, 3, 23, 11, 8, 16 (computed by script; · is an empty slot):

insert keyhome h = key mod 8probe sequencelands intable after
7777[·, ·, ·, ·, ·, ·, ·, 7]
1577 → 00[15, ·, ·, ·, ·, ·, ·, 7]
3333[15, ·, ·, 3, ·, ·, ·, 7]
2377 → 0 → 11[15, 23, ·, 3, ·, ·, ·, 7]
1133 → 44[15, 23, ·, 3, 11, ·, ·, 7]
800 → 1 → 22[15, 23, 8, 3, 11, ·, ·, 7]
1600 → 1 → 2 → 3 → 4 → 55[15, 23, 8, 3, 11, 16, ·, 7]

This is primary clustering in action. The keys that hashed to 7 wrapped around into slots 0 and 1; key 8, whose home is 0, then had to walk past them; and when key 8 filled slot 2 the run 7, 0, 1, 2 merged with the run 3, 4 into one cluster of six slots. Key 16 — home slot 0, no relation to the keys hashing to 3 — paid six probes because it landed in the merged cluster. A cluster of length is hit by any key whose home is in the cluster, so it grows with probability proportional to : big clusters get bigger. At load 7/8 a search for a missing key starting at slot 0 now costs seven probes.

Expected probe counts: Knuth's formulas

Knuth (1963; TAOCP Vol. 3, §6.4) proved that for linear probing with a random hash function and load factor , the expected number of probes is approximately

for a successful and an unsuccessful search respectively. The miss cost blows up quadratically in . Compare the idealised uniform hashing model (every probe sequence is a random permutation, approximated by double hashing), where a miss costs at most and a hit at most . Values computed from the formulas, and measured by simulation (linear probing on a -slot table, random keys, 5 trials):

load αhit, Knuthmiss, Knuthhit, simulatedmiss, simulatedmiss, uniform hashing 1/(1−α)
0.251.171.391.171.391.33
0.51.502.501.492.492.00
0.752.508.502.528.634.00
0.95.5050.505.3246.8410.00
0.9510.50200.5010.56190.7820.00

At linear probing is excellent (2.5 probes per miss, and those probes are adjacent in memory, often in the same cache line). At 0.75 a miss averages 8.5 probes; at 0.9, about 50. This table is the quantitative reason open-addressing tables keep their load at or below about 0.5–0.875 depending on the probing scheme, and it is the reason linear probing is still popular despite clustering: probes are cheap when they are contiguous, so 2.5 sequential probes beat 2 random ones.

Quadratic probing () breaks up primary clustering: keys with different home slots follow different paths. It still has secondary clustering (keys with the same home follow the same path), and a careless choice of constants can leave slots unreachable; with a power-of-two table, the triangular sequence (offsets ) is guaranteed to visit every slot, which is what Swiss tables use at the group level. Double hashing (, with odd for power-of-two tables or nonzero mod a prime ) eliminates both kinds of clustering and approaches uniform hashing, at the cost of a second hash computation and scattered memory accesses.

Chaining vs Open Addressing

CriterionChainingOpen Addressing
Load factor toleranceWorks well even above 1.0Degrades badly above 0.7
Cache performancePoor (pointer chasing)Excellent (contiguous memory)
DeletionSimple (remove from list)Requires tombstones
Memory overheadExtra pointers per nodeNone (but needs lower load factor)
ImplementationSimplerMore complex
Used byJava HashMap, Go map (before 1.24), C++ unordered_mapPython dict, Rust HashMap, Go map (1.24+), Abseil, Folly

Correction: the "Used by" row originally listed Go's map under chaining without qualification. Until Go 1.23 the runtime used buckets of 8 slots with overflow buckets chained off them — a hybrid closer to chaining. Go 1.24 (February 2025) replaced it with a Swiss-table design, which is open addressing. Rust's HashMap has been a port of Google's SwissTable (the hashbrown crate) since Rust 1.36 (2019); before that it used Robin Hood open addressing. Also, "degrades badly above 0.7" depends on the probing scheme: linear probing at 0.75 averages 8.5 probes per miss, while Swiss tables run comfortably at 7/8 because they compare 16 slots per probe.

The "Deletion" row deserves the detail the table hides. In chaining, deleting unlinks a node. In open addressing you cannot simply empty a slot: a later key may have probed past it, and an empty slot would make searches for that key stop early and report it missing. The two standard remedies:

  • Tombstones (lazy deletion): mark the slot as "deleted"; searches continue past it, insertions may reuse it. Tombstones count against the load factor and must be purged by periodic rebuilding, or a workload that inserts and deletes distinct keys will fill the table with them (see the correction above).
  • Backward-shift deletion (linear probing and Robin Hood only): after emptying the slot, walk forward and pull each subsequent entry back one slot as long as that does not move it before its home slot, until reaching an empty slot or an entry already at home. No tombstones ever accumulate. Knuth gives this as Algorithm R (TAOCP Vol. 3, §6.4).

Robin Hood, cuckoo, hopscotch and Swiss tables

Plain linear probing has good average behaviour and a bad tail: some keys sit far from home. Four designs attack the tail or the constant factor.

Robin Hood hashing

Pedro Celis's 1986 PhD thesis (University of Waterloo) introduced Robin Hood hashing: during insertion, compare the probe-sequence length (PSL, distance from home) of the key you are carrying with that of the resident in the current slot. If the resident is "richer" (smaller PSL), take its slot and carry the resident onward instead. Rich keys give up their slots to poor ones. The average PSL is unchanged — the same set of slots is occupied — but the variance collapses, so the worst-case lookup is much shorter, and a search can stop early: once you reach a slot whose resident has a smaller PSL than your current distance, your key cannot be further along. Deletion uses backward shift.

Trace in an 8-slot table, , inserting 8, 16, 1, 24, 9, 17 (computed by script; entries are (key, psl)):

inserthomestepslotresident (key, psl)carrying (key, psl)action
8000empty(8, 0)place
16000(8, 0)(16, 0)resident psl 0 ≥ 0: move on
16011empty(16, 1)place
1101(16, 1)(1, 0)resident psl 1 ≥ 0: move on
1112empty(1, 1)place
24000(8, 0)(24, 0)resident psl 0 ≥ 0: move on
24011(16, 1)(24, 1)resident psl 1 ≥ 1: move on
24022(1, 1)(24, 2)resident poorer (psl 1 < 2): swap, carry (1, 1) on
24033empty(1, 2)place
9101(16, 1)(9, 0)resident psl 1 ≥ 0: move on
9112(24, 2)(9, 1)resident psl 2 ≥ 1: move on
9123(1, 2)(9, 2)resident psl 2 ≥ 2: move on
9134empty(9, 3)place
17101(16, 1)(17, 0)resident psl 1 ≥ 0: move on
17112(24, 2)(17, 1)resident psl 2 ≥ 1: move on
17123(1, 2)(17, 2)resident psl 2 ≥ 2: move on
17134(9, 3)(17, 3)resident psl 3 ≥ 3: move on
17145empty(17, 4)place

Final table [(8,0), (16,1), (24,2), (1,2), (9,3), (17,4), ·, ·]. The displacement happens when 24 arrives: it has travelled 2 slots, the resident 1 only 1, so 24 takes slot 2 and 1 moves to slot 3. In plain linear probing 1 would have stayed at PSL 1 and 24 would have gone to slot 3 with PSL 3. Notice also that the entries end up sorted by home slot (homes 0, 0, 0, 1, 1, 1) — Robin Hood keeps each cluster ordered by home, which is what makes early termination and backward shift work.

class RobinHoodMap:
    """Robin Hood hashing with linear probing and backward-shift deletion (int keys)."""

    def __init__(self, capacity: int = 8):
        self.cap = capacity
        self.slots: list[tuple[int, int, int] | None] = [None] * capacity   # (key, value, psl)
        self.size = 0

    def _home(self, key: int) -> int:
        return key % self.cap                      # identity hash, to match the trace

    def put(self, key: int, value: int) -> None:
        assert self.size < self.cap - 1, "demo has no resizing"
        i, entry = self._home(key), (key, value, 0)
        while True:
            cur = self.slots[i]
            if cur is None:
                self.slots[i] = entry
                self.size += 1
                return
            if cur[0] == entry[0]:                 # update existing key
                self.slots[i] = (cur[0], entry[1], cur[2])
                return
            if cur[2] < entry[2]:                  # resident is richer: rob it
                self.slots[i], entry = entry, cur
            i = (i + 1) % self.cap
            entry = (entry[0], entry[1], entry[2] + 1)

    def _find(self, key: int) -> int:
        i, dist = self._home(key), 0
        while True:
            cur = self.slots[i]
            if cur is None or cur[2] < dist:       # early termination
                return -1
            if cur[0] == key:
                return i
            i, dist = (i + 1) % self.cap, dist + 1

    def get(self, key: int) -> int | None:
        i = self._find(key)
        return None if i < 0 else self.slots[i][1]

    def remove(self, key: int) -> bool:
        i = self._find(key)
        if i < 0:
            return False
        nxt = (i + 1) % self.cap                   # backward shift
        while self.slots[nxt] is not None and self.slots[nxt][2] > 0:
            k, v, d = self.slots[nxt]
            self.slots[i] = (k, v, d - 1)
            i, nxt = nxt, (nxt + 1) % self.cap
        self.slots[i] = None
        self.size -= 1
        return True


rh = RobinHoodMap()
for k in [8, 16, 1, 24, 9, 17]:
    rh.put(k, k * 10)
assert [(s[0], s[2]) if s else None for s in rh.slots] == [(8, 0), (16, 1), (24, 2), (1, 2), (9, 3), (17, 4), None, None]
assert rh.get(17) == 170 and rh.get(25) is None
assert rh.remove(16)                               # shifts 24, 1, 9, 17 back by one
assert [(s[0], s[2]) if s else None for s in rh.slots] == [(8, 0), (24, 1), (1, 1), (9, 2), (17, 3), None, None, None]
assert all(rh.get(k) == k * 10 for k in [8, 1, 24, 9, 17]) and rh.get(16) is None
print("robin hood OK")

Robin Hood was the basis of Rust's HashMap until 2019 and of many high-performance C++ maps (Martin Ankerl's robin_hood::unordered_map, Malte Skarupke's flat_hash_map). Its weakness is that inserts and deletes move many entries, which is a problem when values are large or when references to entries must stay valid.

Cuckoo hashing

Rasmus Pagh and Flemming Friche Rodler ("Cuckoo Hashing", ESA 2001; Journal of Algorithms 2004) use two tables and two hash functions. Every key lives in exactly one of two places: or . A lookup checks both — two memory accesses, worst case, which is the headline property. Insertion places the key in ; if that slot was occupied, the evicted key moves to its alternative slot in the other table, possibly evicting another key, and so on, like a cuckoo chick pushing eggs out of the nest. If the chain of evictions runs too long (it has entered a cycle), pick new hash functions and rehash everything. With each table somewhat larger than (load below 50% overall), insertions take expected amortised time.

import random

class CuckooMap:
    """Two-table cuckoo hashing; O(1) worst-case lookup."""
    MAX_KICKS = 32

    def __init__(self, capacity: int = 16):
        self._setup(capacity)

    def _setup(self, cap: int) -> None:
        self.cap = cap
        self.t = [[None] * cap, [None] * cap]
        self.seeds = (random.getrandbits(64) | 1, random.getrandbits(64) | 1)

    def _h(self, which: int, key: int) -> int:
        x = (key * self.seeds[which]) & ((1 << 64) - 1)
        return (x >> 32) % self.cap

    def get(self, key: int):
        for w in (0, 1):                           # exactly two probes
            e = self.t[w][self._h(w, key)]
            if e is not None and e[0] == key:
                return e[1]
        return None

    def put(self, key: int, value) -> None:
        for w in (0, 1):                           # update in place if present
            i = self._h(w, key)
            if self.t[w][i] is not None and self.t[w][i][0] == key:
                self.t[w][i] = (key, value)
                return
        entry, w = (key, value), 0
        for _ in range(self.MAX_KICKS):
            i = self._h(w, entry[0])
            entry, self.t[w][i] = self.t[w][i], entry   # place, evict the resident
            if entry is None:
                return
            w ^= 1                                 # evictee goes to its other table
        self._rehash(entry)

    def _rehash(self, pending) -> None:
        items = [e for tab in self.t for e in tab if e is not None] + [pending]
        self._setup(self.cap * 2)                  # grow and pick new hash functions
        for k, v in items:
            self.put(k, v)


random.seed(42)
cm = CuckooMap()
keys = random.sample(range(10**9), 500)
for k in keys:
    cm.put(k, k % 97)
assert all(cm.get(k) == k % 97 for k in keys)
assert cm.get(-1) is None
cm.put(keys[0], "updated")
assert cm.get(keys[0]) == "updated"
print("cuckoo OK, table size", cm.cap)

Variants pack 4 or 8 keys per bucket (bucketized cuckoo), which pushes the usable load factor above 90%; cuckoo filters (Fan, Andersen, Kaminsky and Mitzenmacher, CoNEXT 2014) store short fingerprints instead of keys to make a deletable Bloom-filter alternative (Probabilistic Data Structures). Cuckoo hashing is popular in hardware and network switches, where a fixed number of memory accesses per lookup matters more than insertion cost.

Hopscotch hashing

Herlihy, Shavit and Tzafrir (DISC 2008) bound how far an entry can be from home: each bucket owns a neighbourhood of slots (typically 32) and keeps a bitmap of which of them hold its keys, so a lookup reads one bitmap and at most adjacent slots. Insertion finds an empty slot by linear probing and, if it is outside the neighbourhood, "hops" it closer by displacing entries that are allowed to move. It was designed for concurrent use; in single-threaded practice Robin Hood and Swiss tables have largely won.

Swiss tables and F14: SIMD group probing

Google's SwissTable (Abseil's absl::flat_hash_map; Matt Kulukundis, CppCon 2017, "Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step") rethinks open addressing around the CPU:

  • Alongside the slot array, keep a control byte per slot: 0x80 = empty, 0xFE = deleted (tombstone), or, for a full slot, the low 7 bits of the hash (H2). The remaining 57 bits (H1) choose where probing starts.
  • Probe in groups of 16 slots. One SSE2 instruction compares H2 against all 16 control bytes at once and produces a 16-bit mask of candidate matches; another finds empty slots. Only candidates (on average far fewer than one false match per group) have their full keys compared.
  • Groups are visited in triangular order, and the table is resized at 7/8 load. Because one probe examines 16 slots, the effective load per probe is low even when the table is 87.5% full.
flowchart LR
    K["key"] --> HF["64-bit hash"]
    HF --> H1["H1: high 57 bits pick start group"]
    HF --> H2["H2: low 7 bits"]
    H1 --> G["control bytes of a 16-slot group"]
    H2 --> CMP["SIMD compare H2 with all 16 bytes"]
    G --> CMP
    CMP --> MASK["bitmask of candidate slots"]
    MASK --> EQ["compare full keys only for candidates"]
    CMP --> EMPTY["any empty byte in group? stop: key absent"]

Facebook's F14 (Folly; "Open-sourcing F14 for faster, more memory-efficient hash tables", Facebook Engineering blog, April 2019) is the same idea with chunks of 14 slots plus tag bytes and a little metadata — hence the name — and several storage policies (values inline, values in a separate array, values behind pointers) chosen by size. Both replace the "one probe per slot" cost model of classic open addressing with "one probe per group", and both outperform node-based std::unordered_map substantially on most benchmarks. Go 1.24's map, Rust's hashbrown and CPython's dict (in a different, non-SIMD way) all sit in this family of compact, open-addressed, metadata-assisted tables.

Load Factor and Resizing

The load factor is where is the number of entries and is the table size.

  • For chaining: expected chain length is . Performance degrades linearly.
  • For open addressing: expected probes per lookup is . At : 2 probes. At : 10 probes. At : 100 probes.

Correction: is the bound for an unsuccessful search under the idealised uniform hashing assumption (approximately achieved by double hashing). For linear probing, the scheme most implementations actually use, an unsuccessful search costs about probes — 2.5 at , 50.5 at , and about 5,000 at — and a successful one about . See the Knuth table above.

DANGER

Open addressing with a load factor above 0.7 is a performance disaster. Most implementations resize at 0.5-0.75. Python's dict resizes when the table is 2/3 full.

(The danger box applies to one-slot-per-probe schemes. SIMD group-probing tables such as Swiss tables are designed to run at up to 7/8.)

Resizing Strategy

When the load factor exceeds the threshold:

  1. Allocate a new table with 2x capacity
  2. Rehash all existing entries (hash values change because the modulus changes)
  3. This is per resize, but happens infrequently enough that amortized insertion is still

Why 0.75, why 2/3, and why double

The threshold trades memory for probe length. Java chose 0.75 for HashMap ("a good tradeoff between time and space costs", in the class Javadoc): chaining tolerates high load, and 0.75 keeps the expected chain short (the Poisson argument above). The default capacity is 16, so the threshold is 12 entries and the table doubles when the 13th is inserted. CPython resizes its dict when it is 2/3 full (USABLE_FRACTION), because it uses open addressing; the new size is the smallest power of two greater than three times the number of live entries (GROWTH_RATE), so a dict that grew by insertion lands at load between roughly 1/3 and 2/3. Swiss tables use 7/8; libstdc++'s unordered_map defaults to max_load_factor() == 1.0. Redis resizes its dict when the number of entries reaches the number of buckets (load 1) — but defers resizing while a fork for persistence is running, to avoid copy-on-write page duplication, unless the load becomes extreme.

Growth factor. Doubling keeps capacities powers of two (so reduction is a mask), and any geometric factor gives amortised insertion; additive growth would make it amortised. The argument is the same as for dynamic arrays (Arrays & Strings, section "Dynamic arrays").

Amortised cost of resizing, by the potential method. Consider a table that doubles from capacity to when an insert would exceed load 1 (the argument adapts to any constant threshold). Define the potential

where is the number of entries and the capacity; right after a doubling so , and stays non-negative because between doublings. Count one unit per entry inserted or moved.

  • Insert without resize: actual cost 1, , amortised cost .
  • Insert that triggers a resize at : actual cost (move entries, insert one). Before, ; after, and capacity , so . Amortised cost .

Every insert has amortised cost 3, so inserts cost at most plus the initial potential: amortised per insert. The full treatment of the potential method is in Complexity Analysis. If deletions should shrink the table, shrink at a lower threshold than you grow (e.g. halve at load 1/4, double at load 1): shrinking at the same threshold lets an alternating insert/delete sequence trigger a resize on every operation.

Incremental rehashing (Redis)

Amortised still means one insert occasionally costs . For a server holding 100 million keys, a single stop-the-world rehash is a multi-second latency spike. Redis avoids it with incremental rehashing (dict.c): during a resize it keeps two tables, ht[0] (old) and ht[1] (new), and a cursor rehashidx. Every lookup, insert and delete first migrates one bucket from old to new (and a background timer migrates more for about a millisecond at a time when the server is idle). Lookups check both tables; inserts go to the new table only. When the old table is empty, it is freed and the new one becomes ht[0]. The total work is the same, but it is spread across many operations, giving worst-case per operation at the cost of temporarily holding two tables. See Redis Internals. The same idea appears in garbage collectors (incremental copying) and in some database hash indexes; linear hashing (Litwin, 1980) achieves it by splitting one bucket at a time.

flowchart LR
    OP["any get, set or del"] --> STEP["move one bucket from ht0 to ht1"]
    STEP --> LOOK{"key lookup"}
    LOOK -->|"check"| HT0["ht0: old table, shrinking"]
    LOOK -->|"check"| HT1["ht1: new table, 2x size"]
    INS["new inserts"] --> HT1
    HT0 -->|"rehashidx reaches end"| SWAP["free ht0, ht1 becomes ht0"]

How real implementations work

The same few ideas, combined differently. The language-level view (which container to reach for, iteration guarantees, idioms) is in Your Language's Data Structures; this section is the engine room.

Python dict: compact, ordered, perturbed

Since CPython 3.6 (made a language guarantee in 3.7), a dict is two arrays (Objects/dictobject.c):

  • an indices array of size (minimum 8), each entry a small signed integer — 1 byte while the table has at most 128 slots, then 2, 4 or 8 bytes — holding either "empty", "dummy" (deleted), or an index into
  • a dense entries array of (hash, key, value) records, appended in insertion order.
flowchart LR
    subgraph IDX ["indices: 8 slots, 1 byte each"]
        I0["0: 1"]
        I1["1: empty"]
        I3["3: 0"]
        I5["5: 2"]
    end
    subgraph ENT ["entries: dense, insertion order"]
        E0["0: hash, 'apple', 3"]
        E1["1: hash, 'pear', 7"]
        E2["2: hash, 'fig', 1"]
    end
    I3 --> E0
    I0 --> E1
    I5 --> E2

Lookup hashes the key, probes the indices array, follows the index to the entries array and compares the stored hash and then the key. Iteration simply walks the entries array, which is why dicts preserve insertion order and why iteration is fast and cache-friendly. The layout also saves memory: the sparse part is the tiny indices array, while the 24-byte entries are dense (Raymond Hettinger's 2012 python-dev proposal estimated 30–95% savings depending on size).

Probing is not linear. CPython uses the perturb recurrence

starting from perturb = hash and i = hash & mask. The 5i + 1 part alone would visit every slot of a power-of-two table (it is a full-period linear congruential generator); mixing in perturb feeds the high bits of the hash into the sequence, so keys that share low bits — like consecutive integers with their identity hash — diverge quickly. Trace in an 8-slot table with keys whose hash is themselves:

insert key (hash = key)i0 = hash & 7probes (perturb >>= 5; i = (5i + perturb + 1) & 7)slot
0000
800 → 11
1600 → 1 → 66
2400 → 1 → 6 → 77
111 → 6 → 7 → 44

(This simulates only the probe sequence; a real dict of this size would already have resized at 5 entries.) Deleting leaves a "dummy" index; dummies are cleared on the next resize, and dicts never shrink on deletion alone. set uses a separate implementation (setobject.c) that combines linear probing within a short run of slots with perturbation, since sets are often used for membership tests on large collections.

Java HashMap: power-of-two tables, spreading, treeification

java.util.HashMap keeps a Node<K,V>[] table whose length is always a power of two (default 16, load factor 0.75). It computes hash = h ^ (h >>> 16) where h = key.hashCode(), then indexes with (n - 1) & hash. The XOR folds the high 16 bits into the low 16, because a mask of a small table would otherwise ignore them entirely. Example computed by script: for h = 0x12340000 (low 16 bits all zero), the unspread index in a 16-slot table would be 0 — as it would be for every hash differing only in the high bits — while the spread hash 0x12341234 indexes slot 4.

Collisions chain as linked Nodes and treeify past 8 per bin (above). resize() doubles the table and splits each bin into "lo" and "hi" lists by testing one bit (hash & oldCap), preserving relative order. null is allowed as a key (it hashes to 0). LinkedHashMap adds a doubly linked list through all entries for insertion or access order — the LRU building block (Linked Lists). ConcurrentHashMap (Java 8+) uses the same table layout with CAS on empty bins and a lock per bin head for updates, and resizes cooperatively with multiple threads.

C++ std::unordered_map: node-based with a bucket interface

The C++ standard effectively mandates separate chaining: it requires that references and pointers to elements stay valid across rehashing and exposes a bucket interface — bucket_count(), bucket(key), bucket_size(n), local iterators — plus load_factor(), max_load_factor() (default 1.0), rehash(n) and reserve(n). Every element is a separately allocated node. libstdc++ links all nodes into one singly linked list and has each bucket point to the node before its first element, so iteration is a single list walk; bucket counts are prime numbers from a precomputed table (_Prime_rehash_policy), which makes the identity std::hash<int> tolerable for strided keys. The costs are one allocation per insert, a pointer chase per lookup and poor locality — the reason Abseil's flat_hash_map, Folly's F14 and Boost's unordered_flat_map exist. Two practical tips: call reserve(n) before bulk inserts to avoid repeated rehashing, and never rely on unordered_map iteration order.

V8 Map and Set: deterministic ordered hash tables

ECMAScript requires Map and Set to iterate in insertion order. V8 implements them as OrderedHashMap / OrderedHashSet, following Tyler Close's "deterministic hash table" design: a bucket array of chain heads plus an entries array in insertion order, where each entry stores the index of the next entry in its chain. Deleted entries are marked and compacted on rehash. Keys are compared with SameValueZero (NaN equals NaN, +0 equals -0). Strings cache their hash, which V8 computes with a per-isolate hash seed; objects get a random identity hash stored lazily on first use. Plain objects used as dictionaries are a different story — V8 represents them with hidden classes while they look like records and switches to a dictionary-mode hash table when they behave like maps, which is why Map is the right tool for dynamic keys.

Anti-hash tests in competitive programming

On Codeforces, contestants can hack each other's solutions by submitting inputs designed to break them, and for years std::unordered_map<long long, int> was a favourite target. The reason is visible above: in libstdc++, std::hash<long long> is the identity, and the bucket count follows a fixed, public sequence of primes. Inserting many multiples of the current bucket count puts them all in one bucket, and because the map rehashes through known primes, the attacker can choose keys that are multiples of every prime the table will pass through. Each insert then walks a long chain, and inserts take — a time-limit-exceeded verdict on a solution that is correct and "O(n)". The standard reference is neal's Codeforces blog post "Blowing up unordered_map, and how to stop getting hacked on it" (2018).

The fix has two parts, and both are necessary: a strong mixing function (splitmix64) so that structured keys spread, and a runtime random seed so the attacker cannot precompute collisions against your exact function.

#include <cassert>
#include <chrono>
#include <cstdint>
#include <iostream>
#include <unordered_map>

struct SplitMixHash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        // Seed chosen once per run from the clock: the attacker cannot know it.
        static const uint64_t FIXED_RANDOM =
            std::chrono::steady_clock::now().time_since_epoch().count();
        return static_cast<size_t>(splitmix64(x + FIXED_RANDOM));
    }
};

int main() {
    assert(SplitMixHash::splitmix64(0) == 0xe220a8397b1dcdafULL);   // matches the Python version
    std::unordered_map<long long, int, SplitMixHash> m;
    m.reserve(1 << 16);
    // Keys that are all multiples of a large prime: harmless with the custom hash.
    const long long step = 107897;
    for (int i = 0; i < 50000; ++i) m[step * i] = i;
    for (int i = 0; i < 50000; ++i) assert(m.at(step * i) == i);
    assert(m.count(1) == 0);
    std::cout << "custom hash OK, buckets = " << m.bucket_count() << "\n";
}

Other options people use: __gnu_pbds::gp_hash_table (a faster open-addressing table in GCC's policy-based data structures, which needs the same custom hash for safety), coordinate compression to small integers followed by plain arrays, or sorting plus binary search — which has no worst case at all. The same lesson applies outside contests: any service that inserts attacker-controlled keys into a hash table with a fixed, public hash function is exposed.

Rolling hash and Rabin–Karp preview

A polynomial rolling hash lets you compare substrings in after preprocessing. With prefix hashes and powers , the hash of is . Rabin–Karp (Karp and Rabin, 1987) slides a window of the pattern's length over the text, compares hashes, and verifies only on a match: expected time.

Choose prime and large (for example , or with 128-bit multiplication) and random in : for two distinct strings of length , the probability over the choice of that their hashes collide is at most , because their difference is a nonzero polynomial of degree below in with at most roots. With a fixed, public base, or with (letting unsigned overflow do the modulus), there are known anti-hash constructions — Thue–Morse strings break any base modulo — so competitive programmers use a random base and either a large prime modulus or two independent moduli. The full treatment is in String Algorithms; the arrays overview has a first implementation in Arrays & Strings.

import random

def find_all(text: str, pattern: str) -> list[int]:
    """Rabin-Karp: all start indices of pattern in text."""
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []
    MOD = (1 << 61) - 1
    base = random.randrange(256, MOD)              # random base: no fixed bad inputs
    high = pow(base, m - 1, MOD)                   # weight of the outgoing character
    hp = hw = 0
    for i in range(m):
        hp = (hp * base + ord(pattern[i])) % MOD
        hw = (hw * base + ord(text[i])) % MOD
    out = []
    for i in range(n - m + 1):
        if hw == hp and text[i:i + m] == pattern:  # verify: hash equality is only a hint
            out.append(i)
        if i + m < n:                              # roll: drop text[i], add text[i+m]
            hw = ((hw - ord(text[i]) * high) * base + ord(text[i + m])) % MOD
    return out

assert find_all("abracadabra", "abra") == [0, 7]
assert find_all("aaaaa", "aa") == [0, 1, 2, 3]
assert find_all("abc", "d") == []
random.seed(3)
t = "".join(random.choice("ab") for _ in range(2000))
assert find_all(t, "abba") == [i for i in range(len(t) - 3) if t[i:i + 4] == "abba"]
print("rabin-karp OK")

A complete hash map in four languages

Two implementations with the same API — put(key, value), get(key), remove(key), size — and the same test in every language. Keys are strings hashed with 32-bit FNV-1a over their UTF-8 bytes; values are integers. Capacities are powers of two so the index is hash & (capacity − 1).

Open addressing: linear probing, tombstones, resizing

Design decisions, each answering a bug from the correction above:

  • A state array (EMPTY, FULL, TOMB) instead of a sentinel key.
  • find walks the probe sequence, remembers the first tombstone, and stops only at the key or at an EMPTY slot. It returns the key's slot if found, else the best insertion slot (first tombstone if any). Insertion therefore never duplicates a key.
  • The load check counts live entries plus tombstones and keeps their sum at most half the capacity. When it would be exceeded, the table is rebuilt: doubled if live entries exceed a quarter of capacity, otherwise rebuilt at the same size, which simply purges tombstones.
EMPTY, FULL, TOMB = 0, 1, 2


def fnv1a(key: str) -> int:
    h = 0x811C9DC5
    for b in key.encode("utf-8"):
        h = ((h ^ b) * 0x01000193) & 0xFFFFFFFF
    return h


class OpenAddressingMap:
    def __init__(self, capacity: int = 8):
        self._init(capacity)

    def _init(self, cap: int) -> None:
        self.cap = cap
        self.keys: list[str | None] = [None] * cap
        self.vals = [0] * cap
        self.state = [EMPTY] * cap
        self.size = 0
        self.tombs = 0

    def _find(self, key: str) -> tuple[bool, int]:
        """(found, slot): the key's slot, or the best slot to insert it."""
        mask = self.cap - 1
        i = fnv1a(key) & mask
        first_tomb = -1
        while True:
            s = self.state[i]
            if s == EMPTY:
                return False, (first_tomb if first_tomb >= 0 else i)
            if s == TOMB:
                if first_tomb < 0:
                    first_tomb = i
            elif self.keys[i] == key:
                return True, i
            i = (i + 1) & mask

    def _rebuild(self, new_cap: int) -> None:
        old = [(k, v) for k, v, s in zip(self.keys, self.vals, self.state) if s == FULL]
        self._init(new_cap)
        for k, v in old:
            self.put(k, v)

    def put(self, key: str, value: int) -> None:
        if (self.size + self.tombs + 1) * 2 > self.cap:          # keep (live + tombs) <= cap/2
            grow = (self.size + 1) * 4 > self.cap
            self._rebuild(self.cap * 2 if grow else self.cap)    # same size = purge tombstones
        found, i = self._find(key)
        if found:
            self.vals[i] = value
            return
        if self.state[i] == TOMB:
            self.tombs -= 1
        self.keys[i], self.vals[i], self.state[i] = key, value, FULL
        self.size += 1

    def get(self, key: str) -> int | None:
        found, i = self._find(key)
        return self.vals[i] if found else None

    def remove(self, key: str) -> bool:
        found, i = self._find(key)
        if not found:
            return False
        self.state[i], self.keys[i] = TOMB, None
        self.size -= 1
        self.tombs += 1
        return True


# --- the shared test (identical in all four languages) ---
assert fnv1a("hello") == 0x4F9F2CAB
m = OpenAddressingMap()
for i in range(100):
    m.put(f"k{i}", i * i)
assert m.size == 100 and m.cap == 256
assert all(m.get(f"k{i}") == i * i for i in range(100))
m.put("k5", -1)                                   # update, not insert
assert m.get("k5") == -1 and m.size == 100
for i in range(0, 100, 2):
    assert m.remove(f"k{i}")
assert not m.remove("k0") and m.size == 50
assert m.get("k0") is None and m.get("k1") == 1 and m.get("nope") is None
for i in range(1000):                             # tombstone churn
    m.put(f"tmp{i}", i)
    assert m.remove(f"tmp{i}")
assert m.size == 50 and m.cap == 256              # no unbounded growth, no infinite loop
m.put("k0", 7)
assert m.get("k0") == 7 and m.size == 51
print("OpenAddressingMap OK")
import java.nio.charset.StandardCharsets;

public class OpenAddressingMap {
    private static final byte EMPTY = 0, FULL = 1, TOMB = 2;
    private String[] keys;
    private int[] vals;
    private byte[] state;
    private int cap, size, tombs;

    public OpenAddressingMap() { init(8); }

    private void init(int capacity) {
        cap = capacity;
        keys = new String[cap];
        vals = new int[cap];
        state = new byte[cap];
        size = 0;
        tombs = 0;
    }

    static int fnv1a(String key) {
        int h = 0x811C9DC5;
        for (byte b : key.getBytes(StandardCharsets.UTF_8)) {
            h ^= (b & 0xFF);
            h *= 0x01000193;                 // int overflow = mod 2^32
        }
        return h;
    }

    /** Returns slot | (found ? 1 << 31 : 0); low bits = key's slot or best insert slot. */
    private int find(String key) {
        int mask = cap - 1, i = fnv1a(key) & mask, firstTomb = -1;
        while (true) {
            byte s = state[i];
            if (s == EMPTY) return firstTomb >= 0 ? firstTomb : i;
            if (s == TOMB) { if (firstTomb < 0) firstTomb = i; }
            else if (keys[i].equals(key)) return i | (1 << 31);
            i = (i + 1) & mask;
        }
    }

    private void rebuild(int newCap) {
        String[] ok = keys; int[] ov = vals; byte[] os = state;
        init(newCap);
        for (int j = 0; j < ok.length; j++) if (os[j] == FULL) put(ok[j], ov[j]);
    }

    public void put(String key, int value) {
        if ((size + tombs + 1) * 2 > cap) {
            boolean grow = (size + 1) * 4 > cap;
            rebuild(grow ? cap * 2 : cap);
        }
        int r = find(key), i = r & 0x7FFFFFFF;
        if (r < 0) { vals[i] = value; return; }        // found: sign bit set
        if (state[i] == TOMB) tombs--;
        keys[i] = key; vals[i] = value; state[i] = FULL;
        size++;
    }

    public Integer get(String key) {
        int r = find(key);
        return r < 0 ? vals[r & 0x7FFFFFFF] : null;
    }

    public boolean remove(String key) {
        int r = find(key);
        if (r >= 0) return false;
        int i = r & 0x7FFFFFFF;
        state[i] = TOMB; keys[i] = null;
        size--; tombs++;
        return true;
    }

    public int size() { return size; }
    public int capacity() { return cap; }

    static void check(boolean c, String msg) { if (!c) throw new AssertionError(msg); }

    public static void main(String[] args) {
        check(fnv1a("hello") == 0x4F9F2CAB, "fnv");
        OpenAddressingMap m = new OpenAddressingMap();
        for (int i = 0; i < 100; i++) m.put("k" + i, i * i);
        check(m.size() == 100 && m.capacity() == 256, "size/cap");
        for (int i = 0; i < 100; i++) check(m.get("k" + i) == i * i, "get");
        m.put("k5", -1);
        check(m.get("k5") == -1 && m.size() == 100, "update");
        for (int i = 0; i < 100; i += 2) check(m.remove("k" + i), "remove");
        check(!m.remove("k0") && m.size() == 50, "double remove");
        check(m.get("k0") == null && m.get("k1") == 1 && m.get("nope") == null, "after remove");
        for (int i = 0; i < 1000; i++) { m.put("tmp" + i, i); check(m.remove("tmp" + i), "churn"); }
        check(m.size() == 50 && m.capacity() == 256, "churn bounded");
        m.put("k0", 7);
        check(m.get("k0") == 7 && m.size() == 51, "reinsert");
        System.out.println("OpenAddressingMap OK");
    }
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <optional>
#include <string>
#include <utility>
#include <vector>

class OpenAddressingMap {
    enum : uint8_t { EMPTY = 0, FULL = 1, TOMB = 2 };
    std::vector<std::string> keys_;
    std::vector<int> vals_;
    std::vector<uint8_t> state_;
    size_t cap_ = 0, size_ = 0, tombs_ = 0;

    void init(size_t cap) {
        cap_ = cap;
        keys_.assign(cap, std::string());
        vals_.assign(cap, 0);
        state_.assign(cap, EMPTY);
        size_ = tombs_ = 0;
    }

    // {found, slot}: the key's slot, or the best slot to insert it.
    std::pair<bool, size_t> find(const std::string& key) const {
        size_t mask = cap_ - 1, i = fnv1a(key) & mask;
        long long firstTomb = -1;
        while (true) {
            if (state_[i] == EMPTY) return {false, firstTomb >= 0 ? static_cast<size_t>(firstTomb) : i};
            if (state_[i] == TOMB) { if (firstTomb < 0) firstTomb = static_cast<long long>(i); }
            else if (keys_[i] == key) return {true, i};
            i = (i + 1) & mask;
        }
    }

    void rebuild(size_t newCap) {
        auto oldKeys = std::move(keys_);
        auto oldVals = std::move(vals_);
        auto oldState = std::move(state_);
        init(newCap);
        for (size_t j = 0; j < oldKeys.size(); ++j)
            if (oldState[j] == FULL) put(oldKeys[j], oldVals[j]);
    }

public:
    OpenAddressingMap() { init(8); }

    static uint32_t fnv1a(const std::string& key) {     // std::string holds UTF-8 bytes
        uint32_t h = 0x811C9DC5u;
        for (unsigned char b : key) { h ^= b; h *= 0x01000193u; }
        return h;
    }

    void put(const std::string& key, int value) {
        if ((size_ + tombs_ + 1) * 2 > cap_) {
            bool grow = (size_ + 1) * 4 > cap_;
            rebuild(grow ? cap_ * 2 : cap_);
        }
        auto [found, i] = find(key);
        if (found) { vals_[i] = value; return; }
        if (state_[i] == TOMB) --tombs_;
        keys_[i] = key; vals_[i] = value; state_[i] = FULL;
        ++size_;
    }

    std::optional<int> get(const std::string& key) const {
        auto [found, i] = find(key);
        if (!found) return std::nullopt;
        return vals_[i];
    }

    bool remove(const std::string& key) {
        auto [found, i] = find(key);
        if (!found) return false;
        state_[i] = TOMB; keys_[i].clear();
        --size_; ++tombs_;
        return true;
    }

    size_t size() const { return size_; }
    size_t capacity() const { return cap_; }
};

int main() {
    assert(OpenAddressingMap::fnv1a("hello") == 0x4F9F2CABu);
    OpenAddressingMap m;
    for (int i = 0; i < 100; ++i) m.put("k" + std::to_string(i), i * i);
    assert(m.size() == 100 && m.capacity() == 256);
    for (int i = 0; i < 100; ++i) assert(m.get("k" + std::to_string(i)) == i * i);
    m.put("k5", -1);
    assert(m.get("k5") == -1 && m.size() == 100);
    for (int i = 0; i < 100; i += 2) assert(m.remove("k" + std::to_string(i)));
    assert(!m.remove("k0") && m.size() == 50);
    assert(!m.get("k0") && m.get("k1") == 1 && !m.get("nope"));
    for (int i = 0; i < 1000; ++i) {
        m.put("tmp" + std::to_string(i), i);
        bool removed = m.remove("tmp" + std::to_string(i));
        assert(removed);
        (void)removed;
    }
    assert(m.size() == 50 && m.capacity() == 256);
    m.put("k0", 7);
    assert(m.get("k0") == 7 && m.size() == 51);
    std::cout << "OpenAddressingMap OK\n";
}
const EMPTY = 0, FULL = 1, TOMB = 2;
const encoder = new TextEncoder();

function fnv1a(key: string): number {
  let h = 0x811c9dc5;
  for (const b of encoder.encode(key)) {
    h ^= b;
    h = Math.imul(h, 0x01000193) >>> 0;     // exact 32-bit multiply
  }
  return h >>> 0;
}

class OpenAddressingMap {
  private keys: (string | null)[] = [];
  private vals: number[] = [];
  private state: Uint8Array = new Uint8Array(0);
  cap = 0;
  size = 0;
  private tombs = 0;

  constructor(capacity = 8) { this.init(capacity); }

  private init(cap: number): void {
    this.cap = cap;
    this.keys = new Array(cap).fill(null);
    this.vals = new Array(cap).fill(0);
    this.state = new Uint8Array(cap);
    this.size = 0;
    this.tombs = 0;
  }

  /** [found, slot]: the key's slot, or the best slot to insert it. */
  private find(key: string): [boolean, number] {
    const mask = this.cap - 1;
    let i = fnv1a(key) & mask;
    let firstTomb = -1;
    while (true) {
      const s = this.state[i];
      if (s === EMPTY) return [false, firstTomb >= 0 ? firstTomb : i];
      if (s === TOMB) { if (firstTomb < 0) firstTomb = i; }
      else if (this.keys[i] === key) return [true, i];
      i = (i + 1) & mask;
    }
  }

  private rebuild(newCap: number): void {
    const oldKeys = this.keys, oldVals = this.vals, oldState = this.state;
    this.init(newCap);
    for (let j = 0; j < oldKeys.length; j++) if (oldState[j] === FULL) this.put(oldKeys[j]!, oldVals[j]);
  }

  put(key: string, value: number): void {
    if ((this.size + this.tombs + 1) * 2 > this.cap) {
      const grow = (this.size + 1) * 4 > this.cap;
      this.rebuild(grow ? this.cap * 2 : this.cap);
    }
    const [found, i] = this.find(key);
    if (found) { this.vals[i] = value; return; }
    if (this.state[i] === TOMB) this.tombs--;
    this.keys[i] = key; this.vals[i] = value; this.state[i] = FULL;
    this.size++;
  }

  get(key: string): number | undefined {
    const [found, i] = this.find(key);
    return found ? this.vals[i] : undefined;
  }

  remove(key: string): boolean {
    const [found, i] = this.find(key);
    if (!found) return false;
    this.state[i] = TOMB; this.keys[i] = null;
    this.size--; this.tombs++;
    return true;
  }
}

function check(c: boolean, msg: string): void { if (!c) throw new Error(msg); }

check(fnv1a("hello") === 0x4f9f2cab, "fnv");
const m = new OpenAddressingMap();
for (let i = 0; i < 100; i++) m.put(`k${i}`, i * i);
check(m.size === 100 && m.cap === 256, "size/cap");
for (let i = 0; i < 100; i++) check(m.get(`k${i}`) === i * i, "get");
m.put("k5", -1);
check(m.get("k5") === -1 && m.size === 100, "update");
for (let i = 0; i < 100; i += 2) check(m.remove(`k${i}`), "remove");
check(!m.remove("k0") && m.size === 50, "double remove");
check(m.get("k0") === undefined && m.get("k1") === 1 && m.get("nope") === undefined, "after remove");
for (let i = 0; i < 1000; i++) { m.put(`tmp${i}`, i); check(m.remove(`tmp${i}`), "churn"); }
check(m.size === 50 && m.cap === 256, "churn bounded");
m.put("k0", 7);
check(m.get("k0") === 7 && m.size === 51, "reinsert");
console.log("OpenAddressingMap OK");

Why the loop in find always terminates. The invariant size + tombs ≤ cap / 2 (enforced before every insertion) guarantees at least half the slots are EMPTY, and linear probing visits every slot before repeating, so every probe sequence reaches an empty slot within cap steps. Without counting tombstones — as in the corrected TypeScript class — that guarantee disappears.

Separate chaining

The same API with singly linked nodes per bucket, doubling when the load exceeds 0.75. Removing is a linked-list unlink with the pointer-to-link idiom; there are no tombstones to manage, which is chaining's main implementation advantage.

def fnv1a(key: str) -> int:
    h = 0x811C9DC5
    for b in key.encode("utf-8"):
        h = ((h ^ b) * 0x01000193) & 0xFFFFFFFF
    return h


class _Node:
    __slots__ = ("key", "val", "next")

    def __init__(self, key: str, val: int, next: "_Node | None"):
        self.key, self.val, self.next = key, val, next


class ChainingMap:
    def __init__(self, capacity: int = 8):
        self.cap = capacity
        self.buckets: list[_Node | None] = [None] * capacity
        self.size = 0

    def _index(self, key: str) -> int:
        return fnv1a(key) & (self.cap - 1)

    def put(self, key: str, value: int) -> None:
        i = self._index(key)
        node = self.buckets[i]
        while node:
            if node.key == key:
                node.val = value
                return
            node = node.next
        self.buckets[i] = _Node(key, value, self.buckets[i])   # prepend: O(1)
        self.size += 1
        if self.size * 4 > self.cap * 3:                        # load > 0.75
            self._resize(self.cap * 2)

    def get(self, key: str) -> int | None:
        node = self.buckets[self._index(key)]
        while node:
            if node.key == key:
                return node.val
            node = node.next
        return None

    def remove(self, key: str) -> bool:
        i = self._index(key)
        prev, node = None, self.buckets[i]
        while node:
            if node.key == key:
                if prev:
                    prev.next = node.next
                else:
                    self.buckets[i] = node.next
                self.size -= 1
                return True
            prev, node = node, node.next
        return False

    def _resize(self, new_cap: int) -> None:
        old = self.buckets
        self.cap, self.buckets = new_cap, [None] * new_cap
        for node in old:
            while node:
                nxt = node.next
                j = self._index(node.key)
                node.next, self.buckets[j] = self.buckets[j], node   # relink, no allocation
                node = nxt


# --- the shared test ---
m = ChainingMap()
for i in range(100):
    m.put(f"k{i}", i * i)
assert m.size == 100 and m.cap == 256
assert all(m.get(f"k{i}") == i * i for i in range(100))
m.put("k5", -1)
assert m.get("k5") == -1 and m.size == 100
for i in range(0, 100, 2):
    assert m.remove(f"k{i}")
assert not m.remove("k0") and m.size == 50
assert m.get("k0") is None and m.get("k1") == 1 and m.get("nope") is None
for i in range(1000):
    m.put(f"tmp{i}", i)
    assert m.remove(f"tmp{i}")
assert m.size == 50 and m.cap == 256
m.put("k0", 7)
assert m.get("k0") == 7 and m.size == 51
print("ChainingMap OK")
import java.nio.charset.StandardCharsets;

public class ChainingMap {
    private static final class Node {
        final String key;
        int val;
        Node next;
        Node(String key, int val, Node next) { this.key = key; this.val = val; this.next = next; }
    }

    private Node[] buckets = new Node[8];
    private int size;

    static int fnv1a(String key) {
        int h = 0x811C9DC5;
        for (byte b : key.getBytes(StandardCharsets.UTF_8)) { h ^= (b & 0xFF); h *= 0x01000193; }
        return h;
    }

    private int index(String key) { return fnv1a(key) & (buckets.length - 1); }

    public void put(String key, int value) {
        int i = index(key);
        for (Node n = buckets[i]; n != null; n = n.next) {
            if (n.key.equals(key)) { n.val = value; return; }
        }
        buckets[i] = new Node(key, value, buckets[i]);
        size++;
        if (size * 4 > buckets.length * 3) resize(buckets.length * 2);
    }

    public Integer get(String key) {
        for (Node n = buckets[index(key)]; n != null; n = n.next) if (n.key.equals(key)) return n.val;
        return null;
    }

    public boolean remove(String key) {
        int i = index(key);
        Node prev = null;
        for (Node n = buckets[i]; n != null; prev = n, n = n.next) {
            if (n.key.equals(key)) {
                if (prev == null) buckets[i] = n.next; else prev.next = n.next;
                size--;
                return true;
            }
        }
        return false;
    }

    private void resize(int newCap) {
        Node[] old = buckets;
        buckets = new Node[newCap];
        for (Node head : old) {
            for (Node n = head; n != null; ) {
                Node next = n.next;
                int j = index(n.key);
                n.next = buckets[j];
                buckets[j] = n;
                n = next;
            }
        }
    }

    public int size() { return size; }
    public int capacity() { return buckets.length; }

    static void check(boolean c, String msg) { if (!c) throw new AssertionError(msg); }

    public static void main(String[] args) {
        ChainingMap m = new ChainingMap();
        for (int i = 0; i < 100; i++) m.put("k" + i, i * i);
        check(m.size() == 100 && m.capacity() == 256, "size/cap");
        for (int i = 0; i < 100; i++) check(m.get("k" + i) == i * i, "get");
        m.put("k5", -1);
        check(m.get("k5") == -1 && m.size() == 100, "update");
        for (int i = 0; i < 100; i += 2) check(m.remove("k" + i), "remove");
        check(!m.remove("k0") && m.size() == 50, "double remove");
        check(m.get("k0") == null && m.get("k1") == 1 && m.get("nope") == null, "after remove");
        for (int i = 0; i < 1000; i++) { m.put("tmp" + i, i); check(m.remove("tmp" + i), "churn"); }
        check(m.size() == 50 && m.capacity() == 256, "churn bounded");
        m.put("k0", 7);
        check(m.get("k0") == 7 && m.size() == 51, "reinsert");
        System.out.println("ChainingMap OK");
    }
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <memory>
#include <optional>
#include <string>
#include <vector>

class ChainingMap {
    struct Node {
        std::string key;
        int val;
        std::unique_ptr<Node> next;
    };
    std::vector<std::unique_ptr<Node>> buckets_ = std::vector<std::unique_ptr<Node>>(8);
    size_t size_ = 0;

    size_t index(const std::string& key) const { return fnv1a(key) & (buckets_.size() - 1); }

    void resize(size_t newCap) {
        std::vector<std::unique_ptr<Node>> old(newCap);
        old.swap(buckets_);                       // buckets_ is now empty with newCap slots
        for (auto& head : old) {
            while (head) {
                std::unique_ptr<Node> n = std::move(head);
                head = std::move(n->next);
                auto& slot = buckets_[index(n->key)];
                n->next = std::move(slot);        // relink, no reallocation
                slot = std::move(n);
            }
        }
    }

public:
    static uint32_t fnv1a(const std::string& key) {
        uint32_t h = 0x811C9DC5u;
        for (unsigned char b : key) { h ^= b; h *= 0x01000193u; }
        return h;
    }

    void put(const std::string& key, int value) {
        auto& head = buckets_[index(key)];
        for (Node* n = head.get(); n; n = n->next.get())
            if (n->key == key) { n->val = value; return; }
        head = std::make_unique<Node>(Node{key, value, std::move(head)});
        ++size_;
        if (size_ * 4 > buckets_.size() * 3) resize(buckets_.size() * 2);
    }

    std::optional<int> get(const std::string& key) const {
        for (const Node* n = buckets_[index(key)].get(); n; n = n->next.get())
            if (n->key == key) return n->val;
        return std::nullopt;
    }

    bool remove(const std::string& key) {
        // Pointer-to-link: no special case for the bucket head.
        for (std::unique_ptr<Node>* link = &buckets_[index(key)]; *link; link = &(*link)->next) {
            if ((*link)->key == key) {
                *link = std::move((*link)->next);
                --size_;
                return true;
            }
        }
        return false;
    }

    size_t size() const { return size_; }
    size_t capacity() const { return buckets_.size(); }
};

int main() {
    ChainingMap m;
    for (int i = 0; i < 100; ++i) m.put("k" + std::to_string(i), i * i);
    assert(m.size() == 100 && m.capacity() == 256);
    for (int i = 0; i < 100; ++i) assert(m.get("k" + std::to_string(i)) == i * i);
    m.put("k5", -1);
    assert(m.get("k5") == -1 && m.size() == 100);
    for (int i = 0; i < 100; i += 2) assert(m.remove("k" + std::to_string(i)));
    assert(!m.remove("k0") && m.size() == 50);
    assert(!m.get("k0") && m.get("k1") == 1 && !m.get("nope"));
    for (int i = 0; i < 1000; ++i) {
        m.put("tmp" + std::to_string(i), i);
        bool removed = m.remove("tmp" + std::to_string(i));
        assert(removed);
        (void)removed;
    }
    assert(m.size() == 50 && m.capacity() == 256);
    m.put("k0", 7);
    assert(m.get("k0") == 7 && m.size() == 51);
    std::cout << "ChainingMap OK\n";
}
const enc = new TextEncoder();

function fnv1a(key: string): number {
  let h = 0x811c9dc5;
  for (const b of enc.encode(key)) { h ^= b; h = Math.imul(h, 0x01000193) >>> 0; }
  return h >>> 0;
}

interface ChainNode { key: string; val: number; next: ChainNode | null; }

class ChainingMap {
  private buckets: (ChainNode | null)[] = new Array(8).fill(null);
  size = 0;

  get cap(): number { return this.buckets.length; }

  private index(key: string): number { return fnv1a(key) & (this.buckets.length - 1); }

  put(key: string, value: number): void {
    const i = this.index(key);
    for (let n = this.buckets[i]; n; n = n.next) {
      if (n.key === key) { n.val = value; return; }
    }
    this.buckets[i] = { key, val: value, next: this.buckets[i] };
    this.size++;
    if (this.size * 4 > this.buckets.length * 3) this.resize(this.buckets.length * 2);
  }

  get(key: string): number | undefined {
    for (let n = this.buckets[this.index(key)]; n; n = n.next) if (n.key === key) return n.val;
    return undefined;
  }

  remove(key: string): boolean {
    const i = this.index(key);
    let prev: ChainNode | null = null;
    for (let n = this.buckets[i]; n; prev = n, n = n.next) {
      if (n.key === key) {
        if (prev) prev.next = n.next; else this.buckets[i] = n.next;
        this.size--;
        return true;
      }
    }
    return false;
  }

  private resize(newCap: number): void {
    const old = this.buckets;
    this.buckets = new Array(newCap).fill(null);
    for (let head of old) {
      while (head) {
        const next: ChainNode | null = head.next;
        const j = this.index(head.key);
        head.next = this.buckets[j];
        this.buckets[j] = head;
        head = next;
      }
    }
  }
}

function check(c: boolean, msg: string): void { if (!c) throw new Error(msg); }

const m = new ChainingMap();
for (let i = 0; i < 100; i++) m.put(`k${i}`, i * i);
check(m.size === 100 && m.cap === 256, "size/cap");
for (let i = 0; i < 100; i++) check(m.get(`k${i}`) === i * i, "get");
m.put("k5", -1);
check(m.get("k5") === -1 && m.size === 100, "update");
for (let i = 0; i < 100; i += 2) check(m.remove(`k${i}`), "remove");
check(!m.remove("k0") && m.size === 50, "double remove");
check(m.get("k0") === undefined && m.get("k1") === 1 && m.get("nope") === undefined, "after remove");
for (let i = 0; i < 1000; i++) { m.put(`tmp${i}`, i); check(m.remove(`tmp${i}`), "churn"); }
check(m.size === 50 && m.cap === 256, "churn bounded");
m.put("k0", 7);
check(m.get("k0") === 7 && m.size === 51, "reinsert");
console.log("ChainingMap OK");

Both maps reach capacity 256 for 100 keys, but for different reasons: the open-addressing map keeps live + tombstones at most 1/2 of capacity, the chaining map keeps live entries at most 3/4. Neither shrinks on deletion — a deliberate simplification that matches CPython and Java.

Consistent Hashing

Standard hash tables break catastrophically when the table size changes — all entries must be rehashed. In distributed systems, this means adding or removing a server requires moving most data. Consistent hashing solves this by minimizing data movement.

See the full deep dive at Consistent Hashing.

Key insight: Map both keys and servers onto a ring (hash space). Each key is handled by the nearest server clockwise on the ring. Adding/removing a server only affects the keys in its arc.

How catastrophic is "catastrophic"? With server = hash(key) mod N, going from to servers keeps a key in place only if , which happens for about of keys — so roughly of all data moves (for , about 91%). Consistent hashing (Karger et al., STOC 1997) moves only about , the theoretical minimum. In practice each server is placed at many points on the ring (virtual nodes) so load evens out. Rendezvous (highest-random-weight) hashing (Thaler and Ravishankar, 1996) achieves the same minimal movement without a ring: each key goes to the server with the highest . Google's jump consistent hash (Lamping and Veach, 2014) does it in time with no memory, for servers numbered .

Common Interview Patterns

Pattern 1: Frequency Counting

Count occurrences of elements. The most basic hash map pattern.

Python:

from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    count = Counter(nums)
    return [num for num, _ in count.most_common(k)]

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups: dict[str, list[str]] = {}
    for s in strs:
        key = "".join(sorted(s))
        groups.setdefault(key, []).append(s)
    return list(groups.values())

Counter.most_common(k) uses a heap (heapq.nlargest), so top_k_frequent is for distinct values. The bucket-sort alternative — an array of lists indexed by frequency, read from the highest index down — is . For group_anagrams, sorting each word costs ; a count tuple key (26 counts) costs and is the better answer for long words:

from collections import defaultdict

def group_anagrams_counts(strs: list[str]) -> list[list[str]]:
    groups: dict[tuple[int, ...], list[str]] = defaultdict(list)
    for s in strs:
        counts = [0] * 26
        for ch in s:
            counts[ord(ch) - 97] += 1
        groups[tuple(counts)].append(s)          # tuples are hashable, lists are not
    return list(groups.values())

def top_k_bucket(nums: list[int], k: int) -> list[int]:
    freq: dict[int, int] = {}
    for x in nums:
        freq[x] = freq.get(x, 0) + 1
    buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
    for x, f in freq.items():
        buckets[f].append(x)
    out: list[int] = []
    for f in range(len(nums), 0, -1):
        for x in buckets[f]:
            out.append(x)
            if len(out) == k:
                return out
    return out

assert sorted(map(sorted, group_anagrams_counts(["eat", "tea", "tan", "ate", "nat", "bat"]))) == \
       [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]
assert sorted(top_k_bucket([1, 1, 1, 2, 2, 3], 2)) == [1, 2]
print("frequency patterns OK")

Pattern 2: Two Sum (Hash Map Complement Lookup)

For each element, check if its complement exists in the map.

TypeScript:

function twoSum(nums: number[], target: number): [number, number] {
  const seen = new Map<number, number>(); // value → index

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) {
      return [seen.get(complement)!, i];
    }
    seen.set(nums[i], i);
  }

  return [-1, -1];
}

Python:

def two_sum(nums: list[int], target: int) -> tuple[int, int]:
    seen: dict[int, int] = {}  # value → index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return (-1, -1)

Complexity: time, space.

Why look up before inserting: checking complement in seen before seen[num] = i prevents pairing an element with itself (for target = 6 and a single 3), while still finding [3, 3] when two 3s exist, because the first 3 is in the map when the second arrives. Correctness: if the answer is with , then when the loop reaches , nums[i] has been inserted (possibly overwritten by a later equal value, which is an equally valid partner), so the lookup succeeds. If the array is sorted, the two-pointer version on Arrays & Strings needs no extra space.

Pattern 3: Subarray with Given Sum (Prefix Sum + Hash Map)

Use a hash map to store prefix sums. See Arrays & Strings: Prefix Sums.

Python:

def subarray_sum(nums: list[int], k: int) -> int:
    prefix_count = {0: 1}
    current_sum = 0
    count = 0

    for num in nums:
        current_sum += num
        count += prefix_count.get(current_sum - k, 0)
        prefix_count[current_sum] = prefix_count.get(current_sum, 0) + 1

    return count

The whole family — divisible by k (store sum mod k; in Python % is already non-negative, in Java/C++ normalise with ((s % k) + k) % k), longest subarray with sum k (store the first index of each prefix), equal 0s and 1s (map 0 to −1) — is catalogued on Prefix Sums & Difference Arrays.

Pattern 4: Sliding Window + Hash Map

Track character frequencies in a window. See Arrays & Strings: Sliding Window.

Pattern 5: Hash Set for O(1) Existence Check

Python:

def longest_consecutive(nums: list[int]) -> int:
    """Find the longest consecutive sequence."""
    num_set = set(nums)
    max_length = 0

    for num in num_set:
        # Only start counting from the beginning of a sequence
        if num - 1 not in num_set:
            length = 1
            while num + length in num_set:
                length += 1
            max_length = max(max_length, length)

    return max_length

Complexity: time despite the nested while loop — each number is visited at most twice (once in the for loop, once in the while loop).

Proof of . Partition the distinct values into maximal runs of consecutive integers. The while loop runs only from a value with , i.e. from the smallest element of a run, and walks exactly to the end of that run. So each element is stepped over by the while loop at most once (only from its own run's start), giving at most inner iterations in total, plus outer iterations and expected- set operations each. Total: expected. Two remarks: iterating over num_set rather than nums matters — with many duplicates of a run start in nums, the run would be walked once per duplicate, which is for an input like [1]*n/2 + list(range(1, n/2)); and the "expected" is about the hash set, which an adversary could degrade (see hash flooding), whereas sorting gives a guaranteed .

Pattern 6: Design Hash Map / Hash Set

A common interview question — implement a hash map from scratch. The implementations in the "Collision Resolution" section above cover this fully.

What the interviewer is checking, in order: a hash plus reduction to an index; a collision strategy you can justify (chaining is easier to get right at a whiteboard); correct update-vs-insert; deletion (and, for open addressing, why you need tombstones or backward shift); resizing with the amortised argument; and edge cases such as negative keys (hash % m is negative in Java/C++ for negative hashes — use Math.floorMod or mask). The four-language complete hash map section is a model answer; LeetCode 705/706 restrict keys to , so a fixed bucket array of, say, 1,009 chains with key % 1009 is enough.

Pattern 7: LRU cache (hash map + doubly linked list)

get and put in with eviction of the least recently used key: the hash map maps key → node, the doubly linked list keeps nodes in recency order, and both are updated on every access. The implementation and its sentinel trick are on Linked Lists; the module capstone, Build an LRU Cache & Benchmark It, builds and measures it in four languages.

Pattern 8: Hash map + array for O(1) random access

"Insert, delete and getRandom in average " (LeetCode 380): keep values in a dynamic array (for uniform random choice by index) and a map value → index. Delete by swapping the target with the last array element, updating the moved element's index in the map, and popping.

import random

class RandomizedSet:
    def __init__(self):
        self.pos: dict[int, int] = {}
        self.items: list[int] = []

    def insert(self, x: int) -> bool:
        if x in self.pos:
            return False
        self.pos[x] = len(self.items)
        self.items.append(x)
        return True

    def remove(self, x: int) -> bool:
        i = self.pos.pop(x, None)
        if i is None:
            return False
        last = self.items.pop()
        if i < len(self.items):            # x was not the last element: move last into its hole
            self.items[i] = last
            self.pos[last] = i
        return True

    def get_random(self) -> int:
        return random.choice(self.items)

rs = RandomizedSet()
assert rs.insert(1) and not rs.insert(1) and rs.insert(2) and rs.insert(3)
assert rs.remove(1) and not rs.remove(1)
assert sorted(rs.items) == [2, 3] and rs.pos == {v: i for i, v in enumerate(rs.items)}
assert {rs.get_random() for _ in range(200)} == {2, 3}
assert rs.remove(3) and rs.items == [2]
print("RandomizedSet OK")

Hash Tables in Production

Language Implementations

LanguageHash MapHash SetCollision Strategy
PythondictsetOpen addressing (probing)
JavaScriptMap / ObjectSetHash table (V8 uses transition trees for objects)
JavaHashMapHashSetChaining (linked list → red-black tree at 8)
GomapN/A (use map[K]bool)Buckets of 8 with overflow chains (before 1.24); Swiss tables since Go 1.24
C++unordered_mapunordered_setChaining
RustHashMapHashSetSwissTable (hashbrown) since Rust 1.36; Robin Hood before

Correction: this table originally gave Go as "chaining with buckets of 8" and Rust as "Robin Hood open addressing (SwissTable)". Robin Hood and SwissTable are different designs: Rust used Robin Hood hashing until 1.36 (July 2019) and has used the hashbrown port of SwissTable since. Go's map was rewritten as a Swiss table in Go 1.24 (February 2025). The Python row is right but understated: dict is the compact indices-plus-entries design described above, with perturbed probing. For JavaScript, Map and Set are deterministic ordered hash tables with chaining inside a flat array; "transition trees" refers to how V8 represents plain objects (hidden classes), which fall back to a dictionary-mode hash table when used as maps. Go's map[K]struct{} is the idiomatic set (zero bytes per value), better than map[K]bool.

Java 8+ Optimization

Java's HashMap converts chains to red-black trees when a bucket exceeds 8 entries. This bounds worst-case lookup to instead of , preventing hash-flooding DoS attacks.

Two caveats to the tip, from the HashMap source: treeification happens only once the table has at least 64 buckets (smaller tables double instead), and the bound relies on the keys being Comparable when their hashes are equal — for non-comparable keys with identical hashes, a tree bin may still need to search both subtrees. "Mitigating" is a better word than "preventing".

Hash-Based DoS Attacks

An attacker who knows your hash function can craft inputs that all collide, turning operations into . Mitigations:

  • Randomized hash seeds: Python randomizes hash() per process (since 3.3)
  • SipHash: A cryptographically strong hash function used by Rust, Python, and Ruby for strings
  • Tree-ification: Java's fallback to red-black trees at bucket size 8

Detail and history are in "Hash flooding and keyed hashes" above. Precisely: Python 3.3 enabled randomisation by default but its hash function then was a seeded FNV variant whose seed could be recovered (29C3, 2012); SipHash-2-4 replaced it in Python 3.4 (PEP 456) and SipHash-1-3 in 3.11. Operational mitigations matter as much as algorithms: web frameworks cap the number of form fields and JSON keys per request (PHP's max_input_vars was added in response to the 2011 disclosure), and parsers limit input size.

Complexity Summary

OperationAverageWorst Case
Insert (all keys collide)
Lookup
Delete
Space
Resize (amortized per op)

Refinements: "average" here means expected over the hash function's randomness (for universal or keyed hashing) or over random inputs (for fixed hashes). Insert is amortised because of resizing, and worst-case per operation with incremental rehashing (Redis). Cuckoo hashing gives worst-case lookup; Java's treeified bins give worst-case for comparable keys. Space is but the constant varies widely: about 1.1–2× the raw entry size for Swiss tables and compact dicts, and several pointers per entry plus allocator overhead for node-based maps like std::unordered_map and Java HashMap (a HashMap.Node alone is 32 bytes with compressed oops, before the key and value objects).

Real-world uses

  • Language runtimes. Python objects store attributes in dicts (with key-sharing dicts so instances of one class share the key table); module namespaces, globals() and keyword arguments are dicts. String interning uses a hash set so equal identifiers share one object. JavaScript engines use hash tables for Map, Set and dictionary-mode objects.
  • Compilers and interpreters. Symbol tables, the set of reserved keywords (often a perfect hash generated by gperf), constant pools and memoisation caches.
  • Databases. Hash indexes for equality lookups (PostgreSQL USING hash, MySQL MEMORY tables), hash joins (build a hash table on the smaller relation, probe with the larger — the default join for large unsorted inputs; Query Planning & Optimization), hash aggregation for GROUP BY, and buffer-pool page tables mapping page IDs to frames (How Databases Work, Indexing Deep Dive on hash vs B-tree indexes).
  • Key-value stores and caches. Redis's keyspace is one big incrementally rehashed dict (Redis Internals); memcached is a hash table plus an LRU list; the hands-on version is Build a Key-Value Store. Cache sizing math is in Cache Sizing.
  • Operating systems and networking. The Linux page cache, dentry cache and inode cache are hash tables keyed by (file, offset) or (parent, name); connection tracking and socket lookup hash the 4-tuple; NICs use receive-side scaling, a Toeplitz hash of the 4-tuple, to spread packets across CPU queues (Linux Networking Stack).
  • Distributed systems. Sharding by key hash, consistent and rendezvous hashing for placement (Consistent Hashing), load balancers that hash client IPs for stickiness (Load Balancing Algorithms), and Bloom filters to skip disk reads in LSM trees (Bloom Filters, Probabilistic Data Structures).
  • Content addressing and deduplication. Git names objects by their hash; backup systems and object stores deduplicate chunks by hash. These use cryptographic hashes (Hashing Algorithms), where collision resistance matters, unlike hash tables.
  • Concurrency. ConcurrentHashMap, Intel TBB's concurrent_hash_map and lock-free split-ordered lists (Shalev and Shavit, 2006) let many threads share one table (Lock-Free Programming).

Pitfalls

  1. Mutable keys. A key's hash is computed when it is inserted; if the key object changes afterwards, it now hashes elsewhere and the entry becomes unreachable (it is still in the table, using memory, but lookups for the key — old or new value — miss). Python forbids list and dict as keys for this reason; Java and C++ do not stop you from mutating a key object.
  2. Breaking the equals/hashCode contract (Java). Equal objects must have equal hash codes. Overriding equals without hashCode (or vice versa) makes HashMap and HashSet silently misbehave: two "equal" keys land in different buckets. Records and Objects.hash help; IDEs and static analysers flag the mismatch.
  3. __eq__ without __hash__ (Python). Defining __eq__ in a class sets __hash__ to None, making instances unhashable — a TypeError at least, not silent corruption. Defining both but hashing on a mutable field brings back pitfall 1. Dataclasses with frozen=True (or eq=True, unsafe_hash=True if you know what you are doing) get this right.
  4. Float keys and NaN. NaN != NaN, so in Python each float('nan') object is its own key (since 3.10 its hash depends on object identity), and d[float('nan')] never finds an earlier NaN. Java's Double.equals does treat NaN as equal to NaN but treats 0.0 and -0.0 as different, although 0.0 == -0.0 is true. JavaScript Map uses SameValueZero (NaN equals NaN, +0 equals −0). And 0.1 + 0.2 is not 0.3; round or use integers/decimals as keys.
  5. Assuming iteration order. Python dicts and JavaScript Map are insertion-ordered; Python set, Java HashMap, C++ unordered_map and Go maps are not, and Go deliberately randomises map iteration order to stop programs relying on it. Tests that pass by accident on one platform fail on another.
  6. Modifying while iterating. Python raises RuntimeError: dictionary changed size during iteration; Java throws ConcurrentModificationException (fail-fast iterators, best effort); C++ unordered_map invalidates iterators on rehash — inserting during iteration is undefined behaviour if it triggers one. Collect changes and apply them after the loop, or iterate over a snapshot (list(d.items())).
  7. Relying on unordered_map in adversarial settings. Identity hashing plus predictable bucket counts invites anti-hash inputs (above). Use a seeded mixing hash, or a sorted structure.
  8. Integer overflow in polynomial hashes. In Java/C++, signed overflow is wrapping in Java and undefined behaviour in C++. Use unsigned arithmetic (uint64_t) or reduce modulo a prime after every step, and make sure intermediate products fit (two values below multiply to below ; for a 61-bit modulus you need 128-bit multiplication). Negative remainders: (a - b) % M can be negative in Java/C++/JS; add M before reducing.
  9. Hash seeds make output non-deterministic across runs. Python's set of strings iterates in a different order in each process; programs that print sets, or build caches keyed on hash() values persisted to disk, become irreproducible. Set PYTHONHASHSEED for reproducible tests, and never persist hash() values — use a stable hash (FNV, xxHash, SHA-256) for anything that outlives the process.
  10. Negative modulo for indices. hashCode() % capacity is negative for negative hash codes in Java and C++. Use Math.floorMod, mask with & (capacity - 1) for powers of two, or cast to unsigned.
  11. Forgetting that "expected O(1)" includes hashing the key. Hashing a 1 MB string is . Java caches String.hashCode, Python caches str hashes, but composite keys (tuples of large objects) rehash every time.
  12. Using a hash map where an array works. Keys that are small dense integers (0..n−1, letters a..z) belong in an array: no hashing, no collisions, no worst case.

Variations

  • Perfect hashing. For a static key set, choose a hash with no collisions at all. FKS hashing (Fredman, Komlós and Szemerédi, 1984) uses two levels — a first-level table and, per bucket, a second-level table of size equal to the bucket count squared — for space and worst-case lookup.
  • Minimal perfect hashing. A bijection from the keys to : no empty slots. CHD ("Hash, displace, and compress", Belazzougui, Botelho and Dietzfelbinger, ESA 2009) needs about 2.07 bits per key; newer schemes (RecSplit, PTHash) approach the theoretical 1.44 bits per key. Used for read-only dictionaries, genome k-mer indexes and search-engine term tables.
  • Ordered maps vs hash maps. A balanced BST or B-tree (TreeMap, std::map, Python's sortedcontainers) gives operations but supports ordered iteration, range queries, floor/ceiling and min/max, and has no adversarial worst case. Choose a hash map for pure point lookups; choose an ordered map when you need order, ranges or guaranteed bounds. See Trees.
  • Concurrent hash maps. Striped locks, per-bin CAS (Java's ConcurrentHashMap), lock-free split-ordered lists, and read-copy-update tables in the Linux kernel. See Lock-Free Programming and Concurrency Patterns.
  • Consistent hashing and rendezvous hashing — hashing onto servers with minimal remapping when the set changes (above).
  • Linear hashing and extendible hashing — disk-oriented tables that grow one bucket (or one directory doubling) at a time; used in database hash indexes.
  • Robin Hood, cuckoo, hopscotch, Swiss/F14 — open-addressing designs that reduce variance, bound probes, or exploit SIMD (above).
  • Bloom filters, cuckoo filters, count-min sketch, HyperLogLog — hashing without storing keys, for approximate membership, frequency and cardinality (Probabilistic Data Structures).
  • Locality-sensitive hashing — the opposite goal: similar items should collide, for nearest-neighbour search (Search Engineering).

Practice Problems

ProblemPatternDifficulty
Two SumComplement lookupEasy
Valid AnagramFrequency countingEasy
Contains DuplicateHash set existenceEasy
Group AnagramsSorted key → bucketMedium
Longest Consecutive SequenceHash set + smart startMedium
Subarray Sum Equals KPrefix sum + hash mapMedium
Top K Frequent ElementsFrequency + heap/bucket sortMedium
LRU CacheHash map + doubly linked listMedium
Encode and Decode TinyURLHash map (design)Medium
Design HashMapFrom scratchEasy

Practice ladder

Fifteen problems, easiest first, described in our own words; links go to the official statements.

1. Two Sum (LeetCode 1) — Indices of two numbers summing to a target in an unsorted array. Teaches complement lookup and lookup-before-insert.

Hint

One dictionary from value to index; check target - x before storing x.

2. Contains Duplicate II (LeetCode 219) — Are there two equal values at most k positions apart? Teaches "last seen index" maps (or a sliding hash set of size k).

Hint

Store each value's most recent index; on a repeat, compare the distance with k.

3. Isomorphic Strings (LeetCode 205) — Can one string's characters be consistently renamed to get the other? Teaches bijections with two maps.

Hint

A single map s → t is not enough: "ab" → "aa" passes it. Keep the reverse map too, or compare first-occurrence index patterns.

4. Word Pattern (LeetCode 290) — Does a sentence follow a letter pattern one-to-one? Teaches the same bijection with words as values.

Hint

Split the sentence; lengths must match; then two maps as in problem 3.

5. Design HashSet (LeetCode 705) — Implement add/remove/contains without library hash tables. Teaches buckets and chaining at small scale.

Hint

A prime number of buckets (e.g. 1,009), each a short list; key % 1009 is fine for the given key range.

6. Design HashMap (LeetCode 706) — Same with values. Teaches update-vs-insert and deletion.

Hint

Reuse problem 5 with (key, value) pairs; updating an existing key must not append a second pair.

Solution
class MyHashMap:
    def __init__(self, buckets: int = 1009):
        self.m = buckets
        self.table: list[list[list[int]]] = [[] for _ in range(buckets)]

    def put(self, key: int, value: int) -> None:
        bucket = self.table[key % self.m]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])

    def get(self, key: int) -> int:
        for k, v in self.table[key % self.m]:
            if k == key:
                return v
        return -1

    def remove(self, key: int) -> None:
        bucket = self.table[key % self.m]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = bucket[-1]       # swap-remove: O(1) once found
                bucket.pop()
                return

h = MyHashMap()
h.put(1, 1); h.put(2, 2); h.put(1, 10)
assert h.get(1) == 10 and h.get(3) == -1
h.remove(2)
assert h.get(2) == -1
h.put(1009 + 1, 5)                            # same bucket as key 1
assert h.get(1010) == 5 and h.get(1) == 10
print("ok")

Expected per operation with for LeetCode's limit of calls; resize if you want the load bounded independently of the input size.

7. Valid Sudoku (LeetCode 36) — Check that no row, column or 3×3 box repeats a digit. Teaches composite keys.

Hint

One set of tuples such as ("r", row, d), ("c", col, d), ("b", row // 3, col // 3, d) — a repeat insert means invalid.

8. Group Anagrams (LeetCode 49) — Bucket words that are permutations of each other. Teaches canonical keys (sorted string or count tuple).

Hint

Lists are not hashable in Python; use tuple(counts) or the sorted string.

9. Top K Frequent Elements (LeetCode 347) — The k most common values. Teaches counting plus heap, or bucket sort for .

Hint

Frequencies are at most n, so an array of n + 1 buckets indexed by frequency avoids sorting.

10. Pairs of Songs With Total Durations Divisible by 60 (LeetCode 1010) — Count pairs whose sum is a multiple of 60. Teaches complement lookup on residues.

Hint

Count residues t % 60 seen so far; each new song pairs with count[(60 - r) % 60]. The % 60 on the complement handles r = 0.

11. Longest Consecutive Sequence (LeetCode 128) — Longest run of consecutive integers in . Teaches start-of-run detection and its proof.

Hint

Only start walking from x when x - 1 is absent; iterate over the set, not the original list.

Solution
def longest_consecutive(nums: list[int]) -> int:
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:
            y = x
            while y + 1 in s:
                y += 1
            best = max(best, y - x + 1)
    return best

assert longest_consecutive([100, 4, 200, 1, 3, 2]) == 4
assert longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]) == 9
assert longest_consecutive([]) == 0
print("ok")

expected: each element is walked over once, from its run's start.

12. Subarray Sum Equals K (LeetCode 560) — Count subarrays summing to k, negatives allowed. Teaches prefix sums + counts.

Hint

Seed {0: 1}; look up sum - k before inserting sum.

13. Continuous Subarray Sum (LeetCode 523) — Is there a subarray of length at least 2 whose sum is a multiple of k? Teaches prefix residues with first-occurrence indices.

Hint

Map residue → first index, seeded with {0: -1}; a repeated residue at distance ≥ 2 answers yes. Never overwrite the first index.

Solution
def check_subarray_sum(nums: list[int], k: int) -> bool:
    first = {0: -1}
    s = 0
    for i, x in enumerate(nums):
        s = (s + x) % k
        if s in first:
            if i - first[s] >= 2:
                return True
        else:
            first[s] = i                 # keep the earliest index only
    return False

assert check_subarray_sum([23, 2, 4, 6, 7], 6)
assert check_subarray_sum([23, 2, 6, 4, 7], 6)
assert not check_subarray_sum([23, 2, 6, 4, 7], 13)
assert not check_subarray_sum([0], 1)    # length-1 subarray does not count
assert check_subarray_sum([0, 0], 1)
print("ok")

time, space. Equal prefix residues mean the subarray between them has sum .

14. Contiguous Array (LeetCode 525) — Longest subarray with equally many 0s and 1s. Teaches the "map 0 to −1, then find equal prefix sums" reduction.

Hint

Running balance (+1 for 1, −1 for 0); the longest stretch between two equal balances is the answer. Store first occurrences.

15. Insert Delete GetRandom O(1) (LeetCode 380) — A set with average insert, delete and uniform random sample. Teaches map + array with swap-remove.

Hint

The array gives random access; the map gives positions; delete by swapping with the last element (see Pattern 8).

Beyond the ladder. LRU Cache (LeetCode 146) is the design problem behind the module capstone; on Codeforces, any problem with integer keys and open hacking is a chance to practise the splitmix64 custom hash — or to see why sorting and coordinate compression are the safe default.

Interview follow-ups

  • "What is the worst case, and how do real systems avoid it?" per operation when keys collide. Defences: keyed hashes with a random seed (SipHash), treeified bins (Java), worst-case-bounded schemes (cuckoo lookup), or an ordered map when guarantees matter.
  • "Chaining or open addressing?" Open addressing is more cache-friendly and compact and dominates modern implementations (Python, Rust, Go 1.24+, Abseil); chaining tolerates high load, keeps references stable (required by std::unordered_map) and makes deletion trivial.
  • "Why do open-addressing tables keep load near 0.5–0.875?" Because expected probes for linear probing grow like for misses: 2.5 at 0.5, 8.5 at 0.75, 50.5 at 0.9. SIMD group probing tolerates more.
  • "How do you delete from an open-addressing table?" Tombstones (and purge them on rebuild) or backward-shift deletion for linear probing / Robin Hood. Never just empty the slot.
  • "Resizing causes latency spikes — what do you do?" Pre-size (reserve, initial capacity), or rehash incrementally with two tables like Redis.
  • "Design a hash map that is thread-safe." One global lock (simple, contended); lock striping by bucket range; per-bin CAS and locks like ConcurrentHashMap; for read-heavy loads, RCU or copy-on-write snapshots.
  • "Your keys are 64-bit integers from an untrusted source — what hash?" splitmix64 (or another strong mixer) with a per-process random seed; or SipHash if the threat model is serious.
  • "Hash map or sorted array/tree?" Hash for point lookups; tree for order, ranges, predecessor/successor and guaranteed bounds; sorted array + binary search for static data with the best memory footprint.
  • "How would you shard this map across 100 machines?" Consistent or rendezvous hashing with virtual nodes; discuss rebalancing, replication and hot keys.
  • "How much memory does a million-entry HashMap<Integer, Integer> use?" Roughly: table of 2^21 references (about 8 MB with compressed oops, since a million entries exceed 0.75 × 2^20 and push the table to 2^21 slots) + a million 32-byte Nodes + two million 16-byte Integers (minus cached small values) ≈ 70 MB, versus 8 MB for two int[] arrays. Boxing and nodes dominate.

Further Reading

  • Consistent Hashing — hash tables in distributed systems
  • Arrays & Strings — prefix sum + hash map pattern
  • Linked Lists — LRU cache combines hash map with linked list
  • Database Indexing — hash indexes vs B-tree indexes
  • Bloom Filters — probabilistic hash-based data structure
  • Probabilistic Data Structures — Bloom filters, count-min sketch and HyperLogLog in the course
  • Redis Internals — incremental rehashing in production
  • Your Language's Data Structures — dict, HashMap, unordered_map and Map from the user's side
  • Complexity Analysis — the potential method used for resizing
  • String Algorithms — rolling hashes and Rabin–Karp in depth
  • Donald Knuth, The Art of Computer Programming, Vol. 3, 2nd ed., §6.4 "Hashing" (linear probing analysis, Algorithm R, multiplicative hashing)
  • CLRS, Introduction to Algorithms, 4th ed., Chapter 11 "Hash Tables" (chaining analysis, universal hashing, open addressing)
  • J. Lawrence Carter and Mark N. Wegman, "Universal Classes of Hash Functions", JCSS 18(2), 1979
  • Rasmus Pagh and Flemming Friche Rodler, "Cuckoo Hashing", Journal of Algorithms 51(2), 2004 (ESA 2001)
  • Pedro Celis, Robin Hood Hashing, PhD thesis, University of Waterloo, 1986
  • Jean-Philippe Aumasson and Daniel J. Bernstein, "SipHash: a fast short-input PRF", INDOCRYPT 2012; Aumasson, Bernstein and Boßlet, "Hash-flooding DoS reloaded: attacks and defenses", 29C3, 2012
  • Scott A. Crosby and Dan S. Wallach, "Denial of Service via Algorithmic Complexity Attacks", USENIX Security 2003
  • Matt Kulukundis, "Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step", CppCon 2017; Abseil "SwissTables Design Notes"
  • Facebook Engineering, "Open-sourcing F14 for faster, more memory-efficient hash tables", 2019
  • CPython Objects/dictobject.c (the long comment at the top explains the probing), OpenJDK java/util/HashMap.java (implementation notes), Redis src/dict.c
  • neal, "Blowing up unordered_map, and how to stop getting hacked on it", Codeforces, 2018
  • cp-algorithms: String Hashing

Try It Yourself

Problem 1: Given nums = [2, 7, 11, 15] and target = 9, find two numbers that add up to the target using a hash map. Return their indices.

Solution

Iterate through the array, storing each number's index in a hash map:

  • i=0, num=2: complement = 9-2 = 7. Not in map. map={2:0}
  • i=1, num=7: complement = 9-7 = 2. Found 2 at index 0. Answer: [0, 1] (nums[0] + nums[1] = 2 + 7 = 9). Time: , Space: .

Problem 2: Group the anagrams in ["eat", "tea", "tan", "ate", "nat", "bat"].

Solution

Use a sorted string as the hash key:

  • "eat" → sorted key "aet" → group: ["eat"]
  • "tea" → sorted key "aet" → group: ["eat", "tea"]
  • "tan" → sorted key "ant" → group: ["tan"]
  • "ate" → sorted key "aet" → group: ["eat", "tea", "ate"]
  • "nat" → sorted key "ant" → group: ["tan", "nat"]
  • "bat" → sorted key "abt" → group: ["bat"] Answer: [["eat","tea","ate"], ["tan","nat"], ["bat"]]

Problem 3: Find the longest consecutive sequence in [100, 4, 200, 1, 3, 2].

Solution

Put all numbers in a hash set. For each number, only start counting if num-1 is NOT in the set (this is the start of a sequence):

  • 100: 99 not in set → sequence: 100 → length 1
  • 4: 3 is in set → skip (not a start)
  • 200: 199 not in set → sequence: 200 → length 1
  • 1: 0 not in set → sequence: 1, 2, 3, 4 → length 4 Answer: 4 (sequence [1, 2, 3, 4]). Time: .

Problem 4: Design a hash table with separate chaining that handles the insertion of keys "alice", "bob", "carol" into a table of size 4, where h("alice")=2, h("bob")=1, h("carol")=2.

Solution
  • Insert "alice": bucket[2] = [("alice", val)]
  • Insert "bob": bucket[1] = [("bob", val)]
  • Insert "carol": collision at bucket[2]! Append to chain: bucket[2] = [("alice", val), ("carol", val)] Final table: bucket[0]=[], bucket[1]=[("bob", val)], bucket[2]=[("alice", val), ("carol", val)], bucket[3]=[]

Problem 5: If a hash table has 12 entries and a capacity of 16, what is its load factor? Should it resize?

Solution

Load factor .

  • For separate chaining: 0.75 is at the common resize threshold. Most implementations (Java HashMap) resize at 0.75.
  • For open addressing: 0.75 is too high; performance degrades significantly above 0.7. It should resize. Answer: Load factor is 0.75. Whether to resize depends on the collision strategy, but it is at or past the threshold for most implementations.

(Precisely for Java: HashMap resizes when the size exceeds the threshold of 12, i.e. on inserting the 13th entry; at exactly 12 it does not resize yet.)

Problem 6: Insert 10, 18, 26, 3 into an 8-slot linear-probing table with . Where does each land, and how many probes does a search for the missing key 34 take?

Solution

10 → home 2, slot 2. 18 → home 2, probes 2 → 3, slot 3. 26 → home 2, probes 2 → 3 → 4, slot 4. 3 → home 3, probes 3 → 4 → 5, slot 5. Searching 34 (home 2) probes 2, 3, 4, 5, 6 and stops at the empty slot 6: 5 probes, all caused by one cluster.

Problem 7: Why does {1: "a", True: "b", 1.0: "c"} in Python produce a dict with a single entry?

Solution

1 == True == 1.0 and hash(1) == hash(True) == hash(1.0) == 1, so all three are the same key. The dict keeps the first key object (1) and the last value ("c"): {1: "c"}. Equal objects must hash equally, and Python's numeric tower makes these equal.

Quick Quiz

1. What is the average time complexity of hash table lookup?

  • a)
  • b)
  • c)
  • d)
Answer

c) — With a good hash function and appropriate load factor, hash table operations (insert, lookup, delete) are on average. The worst case is when all keys collide.

2. What happens to hash table performance when the load factor approaches 1.0 with open addressing?

  • a) Performance improves
  • b) Performance is unchanged
  • c) The expected number of probes per lookup grows dramatically
  • d) The hash function becomes faster
Answer

c) The expected number of probes per lookup grows dramatically — With open addressing, the expected probes is . At , this is 10 probes; at , it is 100 probes.

Correction: is the idealised uniform-hashing bound for an unsuccessful search. With linear probing an unsuccessful search averages about — about 50 probes at and about 5,000 at — so the growth is even more dramatic than stated.

3. Why does Java's HashMap convert chains to red-black trees when a bucket exceeds 8 entries?

  • a) To save memory
  • b) To prevent worst-case lookup from hash-flooding DoS attacks
  • c) To make insertion faster
  • d) To maintain insertion order
Answer

b) To prevent worst-case lookup from hash-flooding DoS attacks — An attacker can craft inputs that all hash to the same bucket. Converting long chains to red-black trees bounds worst-case lookup to .

4. What is the primary advantage of open addressing over separate chaining?

  • a) Simpler deletion
  • b) Better cache performance due to contiguous memory
  • c) Higher load factor tolerance
  • d) No need for a hash function
Answer

b) Better cache performance due to contiguous memory — Open addressing stores all entries in the array itself, benefiting from CPU cache locality. Chaining uses linked lists that scatter entries across the heap, causing cache misses.

5. In the "Subarray Sum Equals K" pattern, what is stored in the hash map?

  • a) Element values and their indices
  • b) Prefix sum values and their occurrence counts
  • c) Subarray start and end indices
  • d) Element frequencies
Answer

b) Prefix sum values and their occurrence counts — The hash map stores how many times each prefix sum has occurred. When current_sum - k exists in the map, each occurrence represents a subarray that sums to .

6. In an open-addressing table, why can't delete simply mark the slot empty?

Answer

A key inserted later may have probed past that slot. If the slot becomes empty, a search for that key stops there and wrongly reports it missing. Use a tombstone (searches continue past it) or backward-shift deletion.

7. A Codeforces solution using unordered_map<long long, int> gets TLE only after a hack. What happened and what is the fix?

Answer

libstdc++ hashes integers with the identity and uses a predictable sequence of prime bucket counts, so the hacker chose keys that all fall into one bucket, making each operation . Fix: a custom hash that mixes the bits (splitmix64) and adds a seed chosen at runtime, so collisions cannot be precomputed.