A hash table trades memory for near-constant-time lookups¶

Governing idea: A hash function turns a key into an array index, so lookup, insert, and delete cost O(1) on average — as long as collisions stay rare.

Intro 15 min read algorithms

What you'll be able to do

Explain why a hash table reaches O(1) average lookup while a list needs O(n).
Describe how collisions happen and compare chaining vs. open addressing.
Predict when hashing degrades to O(n) and which keys are unsafe to hash.
Apply a hash set/map to turn a nested-loop search into a single pass.

Prerequisites: arrays, big-O notation, basic functions.

A hash table is an array you index by content, not position¶

To find a value in an unsorted array you scan every element: O(n). A hash table removes the scan. It keeps an underlying array of buckets and a hash function h(key) -> int. To store a key you compute i = h(key) % capacity and put it in bucket i; to look it up you compute the same i and go straight there. No scan — you compute the location from the key itself.

That is the whole trick: spend extra memory (empty buckets) to buy direct access.

A good hash spreads keys uniformly, giving O(1) average¶

The array has capacity buckets and holds n items. The ratio α = n / capacity is the load factor. If the hash function scatters keys uniformly, each bucket holds about α items, so a lookup touches ~1 + α entries — constant when α is kept small (real implementations resize once α passes ~0.7).

flowchart LR
    K1["key: alice"] -->|h % 5 = 1| B1
    K2["key: bob"]   -->|h % 5 = 3| B3
    K3["key: carol"] -->|h % 5 = 1| B1
    subgraph Buckets
        B0[0: ·]
        B1[1: alice → carol]
        B2[2: ·]
        B3[3: bob]
        B4[4: ·]
    end

Above, alice and carol hashed to the same bucket — a collision. The table is still correct; bucket 1 just holds a small list. Lookups stay fast because collisions are rare under a good hash and a low load factor.

Collisions are resolved by chaining or by open addressing¶

Two keys will eventually map to the same bucket (pigeonhole principle). Two standard fixes:

Separate chaining — each bucket is a small list (or tree). On collision, append. Simple, degrades gracefully. Used by Java HashMap, Python dict's conceptual model.
Open addressing — keep one item per bucket; on collision, probe for the next free slot (linear/quadratic probing, double hashing). Cache-friendly, no per-entry pointers. Used by Go's map and C++ flat hash maps.

Here is the everyday payoff — collapsing an O(n²) nested search into one pass by remembering what we've seen:

PythonGoC++

def two_sum(nums, target):
    seen = {}                       # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:      # O(1) average lookup
            return [seen[target - x], i]
        seen[x] = i
    return []

func twoSum(nums []int, target int) []int {
    seen := make(map[int]int, len(nums)) // value -> index
    for i, x := range nums {
        if j, ok := seen[target-x]; ok {  // O(1) average lookup
            return []int{j, i}
        }
        seen[x] = i
    }
    return nil
}

std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;        // value -> index
    for (int i = 0; i < (int)nums.size(); ++i) {
        auto it = seen.find(target - nums[i]); // O(1) average lookup
        if (it != seen.end()) return {it->second, i};
        seen[nums[i]] = i;
    }
    return {};
}

Hashing betrays you under bad hashes, mutable keys, and order needs¶

O(1) is an average, not a guarantee. Three ways it breaks:

Adversarial / poor hashes — if many keys collide into one bucket, lookups walk a long chain: worst case O(n). Hash-flooding attacks exploit exactly this.
Mutable keys — if a key's hash changes after insertion (you mutate it), you can never find it again. Keys must be immutable and hashable (Python tuples yes, lists no; in C++/Go the key type needs a stable hash/equality).
No ordering — a hash table has no meaningful key order. Need sorted iteration or range queries? Use a balanced tree (O(log n)), not a hash table.

Equality and hashing must agree

If two keys are equal, they must hash the same — otherwise the table stores duplicates it can never reconcile. When you define a custom key type, override hashing and equality together (__hash__/__eq__, std::hash + operator==, Go: use a comparable struct).

Check yourself¶

Q1 — Is a hash-table lookup always O(1)?

Single best answer:

A. Yes — hashing is constant time by definition.
B. Yes, but only for integer keys.
C. No — it's O(1) on average; a bad hash or high load factor makes it O(n). ← correct
D. No — it's always O(log n).

Why: ✅ C — average-case O(1) assumes uniform hashing and a bounded load factor; pile everything into one bucket and you scan a chain → O(n). ✗ A confuses the average with a guarantee. ✗ B — key type doesn't change the asymptotics. ✗ D conflates hash tables with balanced trees.

Q2 — What does this print?

seen = {}
for x in [3, 3, 3]:
    seen[x] = seen.get(x, 0) + 1
print(len(seen), seen[3])

A. 3 1
B. 1 3 ← correct
C. 3 3
D. 1 1

Why: ✅ B — all three 3s are the same key, so there is one entry (len == 1) whose count was incremented three times (seen[3] == 3). ✗ A and ✗ C assume duplicate keys create separate slots — they don't; a hash map keys by value/equality. ✗ D forgets the running increment.

Practice¶

Two Sum — the canonical "remember what you've seen" pass.
Contains Duplicate — a hash set as a membership test.
Group Anagrams — hashing a derived key (sorted letters / counts).
Top K Frequent Elements — frequency map + selection.

Summary¶

A hash table indexes by content: i = h(key) % capacity → direct access.
Average O(1) holds while the load factor is low and the hash is uniform; implementations resize to keep it that way.
Collisions are unavoidable; resolve them with chaining or open addressing.
It degrades to O(n) under bad hashes, breaks with mutable keys, and keeps no order — reach for a tree when you need ordering.
Governing idea: trade memory for near-constant-time lookups, as long as collisions stay rare.