Hash Tables

Hash maps and hash sets are the most frequently used data structures in interview solutions — and also the most frequently misunderstood. The misunderstanding is almost always the same: treating O(1) amortized as O(1) guaranteed, and not knowing what breaks it. This file explains the full mechanism: how hashing works, how collisions are resolved, when performance degrades, and the patterns that make hash tables indispensable.

---

1. What Hashing Is

A hash table maps arbitrary keys to array indices using a hash function. The goal is to store and retrieve key-value pairs in O(1) average time.

key ──▶ hash_function(key) ──▶ index ──▶ arr[index]

"hello"  ──▶  hash("hello")  ──▶  3  ──▶  arr[3]
"world"  ──▶  hash("world")  ──▶  7  ──▶  arr[7]
42       ──▶  hash(42)       ──▶  2  ──▶  arr[2]

The underlying storage is a plain array. The hash function converts the key to an index in O(1).

Properties a Good Hash Function Must Have

1. Deterministic: Same key → same hash, always. If hash("hello") returns different values on different calls, your table is broken.

2. Uniform distribution: Keys should map roughly evenly across all indices. Clustering destroys performance.

3. Fast to compute: O(1) or O(len(key)) at worst. If hashing is O(n), your “O(1) lookup” is a lie.

4. Avalanche effect (desirable): Small changes to the key should produce very different hashes. This helps with distribution.

---

2. Collision Resolution

A collision occurs when two different keys hash to the same index. This is unavoidable — with n possible keys and m buckets, the birthday paradox guarantees collisions appear far earlier than you’d expect (after about √m insertions).

Strategy 1: Separate Chaining

Each array slot holds a linked list of all key-value pairs that hashed to that slot.

arr[3]: [("hello", 1)] → [("world", 4)] → null   // both hashed to slot 3
arr[7]: [("foo", 9)]   → null

Lookup: hash(key) → slot index → scan the linked list for key. O(1) average if the list is short; O(n) worst case if all keys hash to the same slot.

Insertion: hash(key) → slot index → prepend to linked list. O(1) if we prepend.

Java’s HashMap uses separate chaining. Since Java 8, the linked list converts to a red-black tree when a bucket’s chain length exceeds 8, making worst-case lookup O(log n) per bucket instead of O(n).

Strategy 2: Open Addressing

All entries live in the array itself. No linked lists. On collision, probe for the next available slot.

Linear Probing: On collision at index i, try i+1, i+2, i+3, …

insert("hello") → hashes to 3 → arr[3] is empty → store at 3
insert("world") → hashes to 3 → arr[3] is full  → try 4 → empty → store at 4

Problem with linear probing: Primary clustering. Collisions at i push entries to i+1, making i+1 more likely to be occupied, pushing more entries to i+2, etc. A “cluster” forms, making future lookups scan a growing contiguous block.

Quadratic Probing: Try i + 1², i + 2², i + 3²… Reduces primary clustering but can cause secondary clustering.

Double Hashing: Use a second hash function: (hash1(key) + j * hash2(key)) % m. Best distribution among open addressing strategies; no clustering patterns.

Deletion is tricky with open addressing: You can’t just set a slot to empty — that would break lookup chains for keys that were pushed past that slot during insertion. Use a “tombstone” marker: mark the slot as deleted (not empty), so lookups skip it but insertions can reuse it.

---

3. Load Factor and Rehashing

The load factor α = n/m where n = number of stored entries, m = number of buckets.

As α increases, the average chain length (for chaining) or probe distance (for open addressing) increases, degrading performance.

Threshold: Most implementations resize when α > 0.75 (Java’s HashMap). Python’s dict uses ~0.67.

Rehashing: Allocate a new array of ~2× capacity. Reinsert all existing entries (their indices change since hash(key) % new_capacity differs from hash(key) % old_capacity). This is O(n) work, but it happens at most O(log n) times over n insertions, giving amortized O(1) per insertion — same geometric series argument as dynamic array doubling.

Initial capacity: m=8
After 7 insertions (α=0.875 > 0.75): resize to m=16
After 13 insertions (α=0.8125 > 0.75): resize to m=32
...

Total rehashing work over n insertions: n/2 + n/4 + … ≤ n (geometric series). Amortized cost per insertion: O(1).

---

4. When Does Hash Table Performance Degrade?

Worst case is O(n) per operation. This happens when all keys hash to the same bucket. Under separate chaining, lookup scans a chain of length n.

In competitive programming on Codeforces, adversarial test cases are deliberately crafted to exploit unordered_map’s default hash in C++. The solution: use a custom hash that randomizes, or use a std::map (O(log n) guaranteed, no adversarial vulnerability) for Codeforces problems.

// C++: custom hash to defeat adversarial inputs on Codeforces
struct custom_hash {
    size_t operator()(uint64_t x) const {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
};
unordered_map<int, int, custom_hash> safe_map;

For LeetCode (no adversarial input): HashMap / dict / unordered_map is fine.

---

5. When NOT to Use a Hash Map

• When you need sorted order: Hash maps don’t preserve insertion order (though Python dicts do since 3.7) and can’t efficiently give you “minimum key” or “range queries.” Use a balanced BST (TreeMap in Java, std::map in C++) or a sorted array.

• When keys are integers in a small range: A direct-address table (plain array indexed by key) is faster and uses less memory.

• When memory is tight: Each hash map entry has significant overhead — in Java, a HashMap entry object costs ~32 bytes beyond the key and value. For large datasets with simple keys, arrays are far more memory-efficient.

• When worst-case guarantees matter: If you cannot tolerate O(n) behavior under any input, use a balanced BST — O(log n) guaranteed, no adversarial vulnerability.

---

6. Common Patterns

Frequency Counting

Count occurrences of each element.

freq = {}
for x in arr:
    freq[x] = freq.get(x, 0) + 1

Applications: anagram detection, majority element, most frequent k elements.

Two-Sum Pattern

Find two elements that sum to a target.

seen = {}
for x in arr:
    complement = target - x
    if complement in seen:
        return [seen[complement], current_index]
    seen[x] = current_index

O(n) time, O(n) space. The hash set converts “find complement” from O(n) search to O(1) lookup.

Grouping / Bucketing

Group items that share a property.

// Group anagrams: "eat", "tea", "tan", "ate", "nat", "bat"
// → [["eat","tea","ate"], ["tan","nat"], ["bat"]]

groups = defaultdict(list)
for word in words:
    key = tuple(sorted(word))   // canonical form
    groups[key].append(word)

The hash map key is the “canonical form” — sorted characters. Any anagrams share the same canonical form and thus the same bucket.

Detecting Duplicates / Visited

seen = set()
for x in arr:
    if x in seen:
        return True   // duplicate found
    seen.add(x)

O(n) time, O(n) space. Beats sorting (O(n log n)) when you care about time only.

---

7. Practice Problems

Easy

1. LeetCode #1 — Two Sum (classic two-sum pattern)

2. LeetCode #217 — Contains Duplicate (hash set, O(n))

3. LeetCode #242 — Valid Anagram (frequency count comparison)

Medium

4. LeetCode #49 — Group Anagrams (sorted-string key grouping)

5. LeetCode #128 — Longest Consecutive Sequence (hash set; O(n) solution requires insight about starting points)

6. LeetCode #347 — Top K Frequent Elements (frequency map + bucket sort or heap)

7. LeetCode #560 — Subarray Sum Equals K (prefix sum stored in hash map; classic O(n) trick)

Hard

8. LeetCode #41 — First Missing Positive (use the array itself as a hash map — cyclic sort; O(n) time O(1) extra space)

---

What Most Engineers Get Wrong

Assuming hash map operations are always O(1). They are O(1) amortized for insert/delete, and O(1) average for lookup — assuming the hash function distributes keys uniformly. Adversarial inputs can degrade both to O(n). In production code and in competitive programming, know when to worry about this.

Secondary mistake: Not handling the “complement equals element” edge case in two-sum. If target = 8 and the array contains 4, 4, the naive implementation might match an element with itself. The fix: check seen[complement] != current_index or only add to seen after checking.

Third mistake: Using mutable objects (lists, dicts) as hash map keys in Python. Mutable objects are not hashable. Convert to tuples or frozensets first.

---

Return to README.md · Next: 05_heaps_and_priority_queues.md