Hashing & Hash Tables: How O(1) Lookup Really Works (Collisions, Load Factor, Resizing)

In plain words: the coat-check analogy

Imagine a coat-check room at a theater. When you arrive, the attendant takes your coat and hands you a ticket with a number — say, 47. Your coat goes on hook 47. When you return, you hand over ticket 47, the attendant walks directly to hook 47, and returns your coat in O(1) time — no scanning every hook in order. That's a hash table. The ticket number is the hash, the hooks are the bucket array, and the formula that converts your name to a hook number is the hash function.

If this course allowed only one structure beyond the array, it would be the hash table. Dictionaries, maps, sets, objects, caches, database indexes, deduplication, frequency counting — all hash tables. It's the structure that answers 'find me the value for this key' in O(1) average time, for *any* kind of key, at any scale.

The core idea

Keys and their bucket assignment:
  hash("alice") mod 7 = 3  →  bucket 3
  hash("bob")   mod 7 = 1  →  bucket 1
  hash("carol") mod 7 = 5  →  bucket 5
  hash("dave")  mod 7 = 3  →  bucket 3  ← COLLISION with "alice"

Bucket array (capacity = 7):
  Index │  Contents
  ──────┼──────────────────────────────
    0   │  (empty)
    1   │  ("bob",   value_b)
    2   │  (empty)
    3   │  ("alice", value_a)  →  ("dave", value_d)  [chained list]
    4   │  (empty)
    5   │  ("carol", value_c)
    6   │  (empty)

Arrays give O(1) access — but only by integer position. Hash tables extend that to arbitrary keys with one trick: a hash function converts any key into an integer, and `index = hash(key) mod capacity` maps that integer into an array of buckets. Store the (key, value) pair at that index; to look it up, recompute the same formula and jump straight there. No scanning needed — just arithmetic.

A good hash function must be deterministic (same key → same hash, always), fast (it runs on every operation), and uniform (keys spread evenly across buckets — clustering destroys performance). Real implementations mix the key's bytes through multiplication and bit-mixing so that similar keys ('user1', 'user2') land far apart.

Collisions: the inevitable problem

With more possible keys than buckets, two keys will eventually share an index — a collision. By the birthday paradox, this happens fast: 23 random keys in 365 buckets give a >50% collision chance. Every hash table is really a collision-handling strategy. Two families dominate:

Separate chaining

Each bucket holds a small collection — classically a linked list — of every pair that hashed there. Insert: hash, walk the bucket's chain to check for a duplicate key, else append. Lookup: hash, walk the chain comparing keys. With a good hash function and n items in b buckets, chains average n/b items — the load factor α — so operations cost O(1 + α). Keep α bounded (say ≤ 1) and that's O(1). Some implementations convert long chains to balanced trees (like Java's HashMap), capping even pathological buckets at O(log n).

Open addressing

All pairs live directly in the bucket array — no auxiliary linked lists. On collision, probe for another slot by a fixed rule: linear probing tries index+1, index+2, …; quadratic probing and double hashing spread probes to reduce clustering. Lookup follows the identical probe sequence until it finds the key or an empty slot. Deletion needs a tombstone marker — actually emptying a slot would break other keys' probe chains. Open addressing is more cache-friendly (one contiguous array) but degrades sharply as the table fills; load factors are kept lower, typically under ~0.7.

Capacity = 7. hash(k) = k % 7.
Insert keys: 10, 17, 24

hash(10) = 10%7 = 3  →  slot 3 is empty, insert
hash(17) = 17%7 = 3  →  slot 3 is taken (10 is there)!
                        probe slot 4 → empty, insert 17
hash(24) = 24%7 = 3  →  slot 3 taken, probe 4 (taken), probe 5 → empty, insert 24

Bucket array:
  [ _ | _ | _ | 10 | 17 | 24 | _ ]
    0   1   2    3    4    5   6

Lookup(17): hash = 3, slot 3 has 10≠17, try 4, 4 has 17 ✓
Lookup(31): hash = 3, try 3(10),4(17),5(24),6(empty) → NOT FOUND

Load factor and resizing

As α = n/b climbs, chains lengthen or probe sequences stretch, and O(1) quietly erodes. So hash tables watch α and, past a threshold, resize: allocate a bucket array roughly twice as large and re-insert every element (every index changes, because the modulus changed — this is a full rehash, not a copy). One resize costs O(n), but doubling makes them geometrically rare, so inserts stay amortized O(1) — exactly the same argument as the dynamic array in Lesson 3.

Table state:  capacity=8, n=6, α=6/8=0.75  → RESIZE triggered (threshold 0.75)

Resize:
  1. Allocate new array, capacity = 16
  2. For every (key, value) pair in the old table:
       new_index = hash(key) % 16   ← different modulus!
       insert into new table
  3. Replace old table with new one

Cost: O(n) this operation, but happens so rarely that
      amortized cost per insert stays O(1).

Complexity summary

Space is O(n + b) — the pairs plus the bucket array's slack. The worst-case O(n) column is real: if every key hashes to the same bucket (terrible hash function, or an adversary crafting colliding keys — a genuine DoS vector), the table becomes one long chain. Runtimes counter this by seeding string hashes randomly per process. The fine print on 'O(1)': *average case, assuming a good hash function and bounded load factor*.

Hash sets: membership in O(1)

A hash set is a hash table storing only keys — membership without values. Same complexities. It answers 'have I seen this before?' in O(1), which converts an enormous family of O(n²) 'for each element, scan for…' problems into O(n) ones. If you learn one reflex from this lesson: nested loop doing lookups → replace the inner loop with a hash set/map.

Worked example: two-sum (the canonical hash-map pattern)

Given an array and a target, find two numbers summing to the target. Brute force checks every pair: O(n²). The hash-map version does one pass.

function twoSum(arr, target):
    seen = {}          # hash map: value → index

    for i in 0 .. len(arr)-1:
        need = target - arr[i]
        if need in seen:
            return (seen[need], i)   # found the pair
        seen[arr[i]] = i             # store current value

    return null    # no pair found

i=0  arr[0]=3  need=10-3=7   seen={}          7 not in seen  store: seen={3:0}
i=1  arr[1]=8  need=10-8=2   seen={3:0}       2 not in seen  store: seen={3:0, 8:1}
i=2  arr[2]=5  need=10-5=5   seen={3:0,8:1}   5 not in seen  store: seen={3:0,8:1,5:2}
i=3  arr[3]=2  need=10-2=8   seen={3:0,8:1,5:2}  8 IS in seen!
               → return (seen[8], 3) = (1, 3)

Answer: indices 1 and 3  (values 8 + 2 = 10)  ✓

The same one-pass shape solves counting duplicates, grouping anagrams, first unique element, longest consecutive sequence, and dozens more interview problems. The key insight is always: replace the inner scan with a hash map lookup.

Common pitfalls

• Mutable keys. Mutating a key after insertion changes its hash; the entry is filed under the old index and becomes unfindable. Use immutable keys (strings, numbers, tuples), or never mutate.
• Breaking the hash/equality contract. Equal keys must produce equal hashes. In languages where you define both, override one without the other and lookups silently fail.
• Expecting order. Iteration order is arbitrary (or insertion-order in some languages, but never *sorted*). Needing sorted keys or range queries means a balanced BST, not a hash table.
• Ignoring worst-case where it matters. Untrusted keys + predictable hash = collision-flooding DoS. Runtimes mitigate with random seeds, but it's worth knowing why.
• Using a map where a set says it better. If you only care about membership, a set states the intent more clearly and saves value storage.

When to use vs avoid

• Use: lookup by key, deduplication, counting frequencies, caching/memoization (Lesson 8), detecting seen-before, joining two datasets by key. It should be your reflexive answer to 'find X quickly by name'.
• Avoid: sorted iteration, range queries ('all keys between A and M'), nearest-key queries — order-destroying hashing can't help; balanced trees and sorted arrays can. Also reconsider when memory is extremely tight: the bucket array's slack and per-entry overhead are real.

Practice problems

1. Group anagrams: given a list of words, group words that are anagrams of each other. Solve in O(n·k log k) using a hash map keyed on sorted characters.
2. Longest consecutive sequence: given an unsorted array of integers, find the length of the longest consecutive run (e.g., [100,4,200,1,3,2] → 4 for 1,2,3,4). Solve in O(n) using a hash set.
3. Subarray sum equals k: given an integer array and target k, count the number of contiguous subarrays summing to k. Hint: prefix sums + hash map of prefix-sum frequencies.

Key takeaways

• hash(key) mod capacity turns any key into an array index — O(1) average insert, lookup, delete.
• Collisions are guaranteed; chaining (lists per bucket) and open addressing (probe sequences) are the two ways to live with them.
• Load factor measures fullness; resizing + rehashing keeps it bounded and keeps inserts amortized O(1).
• 'O(1)' is average-case with a good hash and bounded load — the worst case is O(n), and adversarial keys can force it.
• The hash map/set is the single most effective tool for turning O(n²) scans into O(n) passes. Reach for it whenever an inner loop is a lookup.

Next, the course goes hierarchical: trees and binary trees, where recursion from Lesson 8 becomes the natural language. Drill hash-table mechanics and patterns in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play