Hash Table

A hash table stores key-value pairs and supports put(k, v), get(k), and delete(k) in O(1) expected time. It works by mapping each key to an array index via a hash function, then handling the inevitable collisions (different keys mapping to the same index) using either separate chaining (each slot holds a list) or open addressing (collisions probe nearby slots). Hash tables are the substrate for Python’s dict, Java’s HashMap, and the unordered_map in C++ — and they’re the silent answer to roughly 40% of LeetCode mediums.

1. Intuition — The Coat-Check Analogy

You go to a coat check at a theater. The clerk asks for your name, runs it through her brain to spit out a number (“Smith” → coat hook 7), and hangs your coat on hook 7. When you return, she runs the same process: “Smith” → 7, fetches the coat from hook 7, hands it to you.

That’s the entire hash table:

• Names are the keys.
• Coats are the values.
• The clerk’s brain → number is the hash function.
• The hook is an array slot.

The “magic” is that we don’t search through every coat — we go directly to the right hook. That’s how O(1) lookup is possible.

The catch: what if “Smith” and “Jones” both hash to hook 7? That’s a collision, and how you handle it is what separates hash table implementations.

2. Tiny Worked Example (Separate Chaining, n=10 buckets)

Insert keys 25, 13, 7, 47, 33 (values are just the keys for simplicity). Hash function: h(k) = k mod 10.

Bucket  0:  []
Bucket  1:  []
Bucket  2:  []
Bucket  3:  [13, 33]      ← collision: both 13 % 10 == 3 and 33 % 10 == 3
Bucket  4:  []
Bucket  5:  [25]
Bucket  6:  []
Bucket  7:  [7, 47]       ← collision
Bucket  8:  []
Bucket  9:  []

To get(33): hash → 3, walk the chain at bucket 3 → find 33 → return. To get(99): hash → 9, chain is empty → not found.

In a well-tuned hash table the chains stay very short (typically ≤ 1.5 elements on average), so the “walk the chain” step is essentially constant time.

3. Hash Functions — What Makes One “Good”

A hash function h: keys → integers in [0, m) should:

1. Be deterministic — h(k) always returns the same value for the same k.
2. Be fast to compute — typically O(1) per call. (Otherwise the whole O(1) story collapses.)
3. Distribute keys uniformly across the m buckets — no clustering.
4. Be sensitive to all bits of the key — changing any input bit should change ~50% of output bits, on average.

Common hash functions

• Modular hashing: h(k) = k mod m. Trivial to compute, but choosing m matters: if m shares factors with key patterns (e.g., m = 100 and many keys end in 00), you cluster badly. Pick m to be a prime not too close to a power of 2.

• Multiplicative hashing: h(k) = floor(m · ((k · A) mod 1)) for some real A between 0 and 1. Knuth recommends A = (√5 - 1) / 2 ≈ 0.618 (the golden ratio’s reciprocal). Less sensitive to m’s exact value.

• Universal hashing: randomly select a hash function from a family at runtime. Defends against adversarial keys (an attacker who chooses keys to cause collisions). Used in security-conscious implementations.

• Cryptographic hashes (MD5, SHA-256): far stronger than needed — slow. Use only when you need security, not for general-purpose hash tables.

• Production non-crypto hashes: MurmurHash3, xxHash, CityHash, SipHash. Fast (a few cycles per byte), well-distributed. SipHash is technically a cryptographic pseudo-random function, but it is fast enough to use as a general-purpose keyed hash. It is the default for str/bytes keys in CPython (adopted in Python 3.4 via PEP 456, which replaced the earlier randomized-FNV scheme introduced for hash-DoS mitigation in 3.3) and in Rust’s standard HashMap (SipHash-1-3, Rust 1.36 blog), precisely because its small keyed-randomness layer mitigates hash-collision DoS attacks (see §10.3).

4. Collision Resolution — Two Schools

4.1 Separate Chaining

Each bucket holds a list (or, in modern Java, a list that converts to a balanced tree above a threshold to bound worst-case lookup).

table[h(k)].append((k, v))           # insert
for (kk, vv) in table[h(k)]:         # lookup
    if kk == k: return vv

Pros: simple; load factor can exceed 1; deletions are easy. Cons: extra pointer-chasing on collisions; cache-unfriendly because chains live in scattered allocations.

4.2 Open Addressing (Probing)

The table itself stores entries directly — no separate chains. On collision, probe other slots according to a probe sequence.

Linear probing: try h(k), h(k)+1, h(k)+2, ... (mod m). Quadratic probing: try h(k), h(k)+1, h(k)+4, h(k)+9, .... Double hashing: try h(k), h(k) + h₂(k), h(k) + 2·h₂(k), ..., where h₂ is a second, independent hash.

def get(k):
    i = h(k)
    while table[i] is not EMPTY:
        if table[i].key == k: return table[i].value
        i = (i + 1) % m         # linear probing
    return None

Pros: all data in one contiguous array — cache-friendly; no per-entry pointer overhead. Cons: load factor must stay below ~0.7 (otherwise probes get long); deletions are tricky (you must use a “tombstone” marker, not just clear the slot).

Linear probing's clustering problem

Linear probing suffers from primary clustering (CLRS §11.4): once a run of contiguous filled slots forms, any key that hashes anywhere into that run must probe to its end, extending the run and making it even more likely to absorb the next collision. Long runs thus grow super-linearly, and probe lengths blow up well before the table is full. Quadratic probing eliminates primary clustering but introduces milder secondary clustering — two keys with the same initial hash follow the same probe sequence, so they collide repeatedly. Double hashing has neither problem (the step size depends on a second hash, so colliding keys diverge) and is the strongest in theory, yet in practice linear probing often wins on wall-clock time because its sequential memory access pattern is far friendlier to CPU caches than the scattered jumps of double hashing.

CPython’s dict uses open addressing with a perturbation scheme — instead of pure linear probing, the next probe index is i = (5*i + 1 + perturb) % m, where perturb is shifted right by 5 each step. This mixes the probe sequence based on bits the original hash didn’t use, dramatically reducing clustering.

5. Load Factor and Resizing

The load factor α = n / m is the ratio of occupied slots to total slots.

• Separate chaining: can tolerate α > 1. Average chain length is α. If α grows large, lookups slow down linearly.
• Open addressing: α < 1 is mandatory (you can’t have more entries than slots). Performance degrades sharply as α → 1. Most implementations resize when α > 0.75 or so.

Resizing algorithm:

1. Allocate a new array, typically 2m slots.
2. Re-hash every existing entry into the new array. (Hash function output depends on m, so you can’t just copy.)
3. Free the old array.

This is O(n) per resize. But if you double the capacity on each resize, the amortized cost per insert is still O(1) — see Amortized Analysis for the standard argument. The intuition: to reach n entries you resize at sizes roughly 1, 2, 4, ..., n, and the total rehash work is 1 + 2 + 4 + ... + n < 2n, a geometric series that sums to O(n) over all n inserts. Spreading that O(n) total across n inserts gives O(1) amortized each. (The key is multiplicative growth — resizing by a fixed additive increment, e.g. always +100 slots, would make total rehash work O(n²) and destroy the amortized bound.)

def insert(k, v):
    if (n + 1) / m > 0.75:
        resize()                # double m, re-hash everything
    # ... actual insert ...

6. Complexity

Operation	Average	Worst
get(k)	O(1)	O(n)
put(k, v)	O(1) amortized	O(n) (during resize / many collisions)
delete(k)	O(1)	O(n)
Iterate all	O(n + m)	O(n + m)

Why “amortized” for put: individual puts might trigger a resize that takes O(n). But over a sequence of n inserts, the total resize cost is bounded — see §5.

Why O(n) worst case for get: an adversary or unlucky hash distribution could put all n keys in one bucket, degenerating to a linear scan.

Why interviews say “O(1)”: with a decent hash function and reasonable load factor, the worst case effectively never happens. But always acknowledge the worst case if asked — saying “O(1)” without the qualifier is a small ding for senior interviews.

7. Common Interview Patterns Built on Hash Tables

Problem	Pattern
Two-Sum (find indices of pair summing to target)	Map of value → index; for each x, check if target - x is in the map
Group anagrams	Map sorted-letters → list of words
Longest substring without repeating chars	Map char → last index; sliding window
Subarray sum equals k	Map prefix-sum → count of occurrences
Detect cycle in Linked List (alt to Floyd’s)	Set of seen-nodes
First non-repeating char	Map char → count, then scan
Top K frequent elements	Map for counting + heap or bucket-sort
Valid Sudoku	Sets per row/col/box
Word pattern / Isomorphic strings	Two maps for bijection

If a problem mentions “in O(n)” and involves looking up “have I seen this before?”, a hash table is almost certainly the answer.

8. Special Hash Tables / Variants

• Hash set — same structure but stores keys only (no values). Used for membership tests and dedup.
• Multimap — each key can map to multiple values. Implement as map<K, list<V>>.
• Concurrent hash map — sharded internally so multiple threads can write to different shards without locking the whole table. Java’s ConcurrentHashMap is the canonical example.
• Robin Hood hashing — open addressing where, on a collision, the entry that has travelled farther from its ideal slot (“greater probe distance”) is allowed to keep the slot and the incumbent is pushed onward; this equalizes how far entries are displaced and so reduces the variance of probe lengths (the rich-poor metaphor: steal from the entry that is close to home to give to the one that is far). Rust’s standard HashMap used Robin Hood hashing until it was replaced by the SwissTable-based hashbrown implementation in Rust 1.36.0 (July 2019) (Rust 1.36 release notes).
• Swiss table / SwissMap — open addressing with a separate array of one-byte control metadata per slot (7 bits of the hash plus empty/deleted state), scanned 16 lanes at a time with SIMD so a whole group of slots is probed in a couple of instructions. Used in Google’s absl::flat_hash_map, Rust’s current HashMap (hashbrown), and — since Go 1.24 (Feb 2025) — the Go built-in map. Fast in practice; see Swiss Table Maps for the control-byte mechanism in depth.
• Cuckoo hashing — two hash functions, two tables; on collision, “kick out” the existing entry to its alternate slot. Worst-case O(1) lookup (always at most two probes); insertion can be amortized O(1).
• Perfect hashing — for static key sets, construct a hash function with zero collisions. O(1) worst case. Useful for compiler keyword tables.

9. Hash Table vs Other Data Structures

Need	Use
Key-value lookup, no ordering	Hash Table
Key-value lookup with sorted iteration / range queries	Binary Search Tree (red-black, AVL)
Membership test only, fixed false-positive rate OK, very memory-tight	Bloom Filter
Cardinality estimation only	HyperLogLog
Counting heavy-hitters with bounded memory	Count-Min Sketch
Cache with eviction	LRU Cache (hash map + doubly linked list)
Prefix queries on strings	Trie

The single biggest reason to not use a hash table is needing ordered iteration — hash tables give you keys in arbitrary (often unstable across versions) order. If you need sorted, use a tree-based map.

10. Pitfalls

10.1 Mutating Keys

If you put a mutable object (e.g., a Python list) in a dict and then mutate it, the hash changes — the entry becomes “lost” (still in the table but unreachable via lookup, because the new hash points to a different bucket). Hash table keys must be immutable (or treated as such). Python enforces this by raising TypeError: unhashable type for lists.

10.2 Equality Without Hash Consistency

The contract: if a == b, then hash(a) == hash(b). Violating this breaks the table (two equal objects map to different buckets, both seem “present” simultaneously). Always implement __hash__ and __eq__ together.

10.3 Hash Collision DoS

If your hash function is publicly known and an attacker controls the keys (e.g., HTTP query parameters parsed into a dict), they can craft inputs that all collide, degrading your O(1) lookups to O(n) and DoSing your server. Real attack from 2011-2012 against PHP, Java, Python, etc. Modern languages mitigate with:

• Random seeding (Python 3.3+‘s PYTHONHASHSEED)
• Keyed hash functions (SipHash)

10.4 Iteration Order Surprises

Java’s HashMap iteration order changes between insertion sequences. Python’s dict preserves insertion order since 3.7 (became a language guarantee, not just an implementation detail), but set does not. Don’t rely on a hash table’s order unless your language guarantees it.

10.5 Resizing Pauses

A dict insert that triggers a resize can be O(n). For latency-sensitive code (real-time, games), this is sometimes unacceptable; use a concurrent / incremental hash table or pre-size the table to avoid resizes.

10.6 Forgetting Tombstones in Open Addressing

If you delete an entry by clearing the slot, future lookups for keys whose probe path passed through that slot will halt early (“empty slot → not found”). Mark deleted slots as tombstones (a special value distinct from “empty”) so probes continue.

10.7 Confusing Hash with Encryption

hash("password") is not encryption. Hashes are one-way; encryption is reversible with a key. Also: don’t use a regular hash table’s hash function for password storage — use a password hash like Argon2 or bcrypt, which is intentionally slow.

11. Diagram — Separate Chaining vs Open Addressing

flowchart LR
    subgraph "Separate Chaining"
        SC0["[0]"] --> N1[apple]
        SC1["[1]"]
        SC2["[2]"] --> N2[banana] --> N3[mango]
        SC3["[3]"]
    end
    subgraph "Open Addressing (linear probing)"
        OA0["[0] apple"]
        OA1["[1] empty"]
        OA2["[2] banana"]
        OA3["[3] mango (probed from 2)"]
    end

What this diagram shows. Both diagrams represent the same insertions: apple → bucket 0, banana → bucket 2, mango → bucket 2 (collision). With chaining, mango appends to the chain at slot 2; with open addressing (linear probing), mango is placed at slot 3 (next free slot). Open addressing keeps everything in one array (cache-friendly); chaining isolates collisions but allocates per-bucket nodes.

12. Real-World Implementations (Worth Knowing)

These details are point-in-time; standard-library hash tables evolve, so each claim below names a version or release where possible.

• CPython dict (see CPython Dict Internals for the full mechanism): open addressing — never chaining. The probe recurrence is j = (5*j + 1 + perturb) % 2^i, with perturb initialized to the full hash and right-shifted by PERTURB_SHIFT = 5 each step, so the early probes are scrambled by the high bits of the hash that the initial slot index ignored (verified in Objects/dictobject.c). The table is grown when it is more than ~2/3 full — USABLE_FRACTION(n) = (2*n)/3 — so the load factor cap is about 0.66. Key insertion order is preserved as a language guarantee since Python 3.7 (the “compact dict” layout, separating a dense insertion-ordered entries array from a sparse index array). str/bytes keys are hashed with SipHash since 3.4.
• Java HashMap: separate chaining, but a single bucket is converted (“treeified”) from a linked list to a red-black tree once it holds more than TREEIFY_THRESHOLD = 8 entries — and only if the table has at least MIN_TREEIFY_CAPACITY = 64 buckets; below that, a hot bucket triggers a resize instead of treeification. A treeified bucket reverts to a list when it shrinks below UNTREEIFY_THRESHOLD = 6 during a resize. Treeification bounds a single bucket’s worst case at O(log n) instead of O(n), blunting hash-collision DoS. Default initial capacity 16; resizes when α > 0.75 (the default loadFactor).
• Java LinkedHashMap: HashMap + doubly-linked list of entries to preserve insertion (or access) order. Used to implement LRU Cache.
• C++ std::unordered_map: effectively mandated to be separate chaining because the standard exposes a bucket interface and guarantees reference/pointer stability of elements across rehash — open addressing cannot satisfy this. Most “fast” C++ hash maps (absl::flat_hash_map, Boost’s unordered_flat_map since 1.81) use open addressing instead and are correspondingly faster.
• Rust HashMap (std): SwissTable-style open addressing via the hashbrown crate, adopted as the std implementation in Rust 1.36.0 (July 2019). SipHash-1-3 by default with a per-table random seed for DoS resistance; the hasher is swappable for a faster non-DoS-resistant one (e.g. ahash, FxHash) when adversarial keys are not a concern.
• Go map: separate chaining where each “bucket” holds up to 8 key/value pairs in flat arrays (keys grouped together, then values, for cache efficiency and to avoid per-key padding); on overflow a bucket chains to an overflow bucket, and table growth is performed incrementally (evacuating a few buckets per write) to avoid a single long stop-the-world rehash pause.

Uncertain

Verify: Go’s map internals above describe the long-standing runtime/map.go (bmap/8-slot) design. Reason: Go 1.24 (Feb 2025) replaced the built-in map with a Swiss Tables-based implementation, which changes the bucket/group layout. To resolve: confirm against the current runtime source for the targeted Go version — the “8-slot chained bucket” description is accurate for pre-1.24 and the conceptual model still holds, but the exact group structure differs in 1.24+. uncertain

13. Open Questions

• When does cuckoo hashing’s worst-case-O(1) lookup actually matter in practice? Mostly in real-time systems and network packet processing.
• Is Robin Hood hashing’s reduced variance worth the extra complexity? Rust dropped it for SwissMap; suggests “no, not for general-purpose.”

14. See Also

• Hash Function Design — what makes a good hash function (deeper than this note)
• CPython Dict Internals — the compact-dict layout and perturbation probing in depth
• Swiss Table Maps — SIMD control-byte open addressing (Abseil / hashbrown / Go 1.24)
• Bloom Filter — probabilistic membership; complementary tool
• Count-Min Sketch — probabilistic frequency
• HyperLogLog — probabilistic cardinality
• LRU Cache — hash map + doubly linked list
• Consistent Hashing — distributed hashing across machines (System Design)
• Big-O Notation
• Amortized Analysis — why amortized O(1) for inserts
• SWE Interview Preparation MOC