Hash Tables — Complete DSA Hash Table Theory

Learning Progress. Work top to bottom: theory → collision handling → the interactive bucket visualizer → patterns → cheat sheet → interview prep. Pin the visualizer (button top-right of the panel) to keep it on screen while you read.

Theory & Fundamentals

What is a Hash Table?

A Hash Table maps keys to values using a hash function that turns a key into an array index (a bucket). Done well, insert, delete, and lookup are O(1) average.

The catch is collisions: two keys hashing to the same bucket. How you resolve them (chaining vs open addressing) and your load factor decide real-world performance.

The hash function

// map key → bucket index
index = hash(key) % capacity

// good hash: fast, uniform, deterministic
// load factor α = n / capacity
// resize (rehash) when α > ~0.75

Why Hash Tables? They turn O(n) lookups into O(1): the single most common way to speed up an algorithm. Two Sum, frequency counts, dedup, caches, sets, symbol tables — all hash tables underneath.

Collision Resolution

🔗

Separate Chaining

Each bucket holds a linked list (or vector) of entries that hash there.

Use: simple, handles high load factor. std::unordered_map.

➡️

Linear Probing

On collision, step to the next slot (i+1, i+2…) until an empty one.

Use: cache-friendly, but clustering.

🔢

Quadratic / Double Hash

Probe by i², or use a second hash for the step, reducing clustering.

Use: open addressing with better spread.

Terminology

Hash Function

Maps a key to an integer index, ideally uniformly.

Bucket / Slot

An array cell where entries hashing to that index live.

Collision

Two distinct keys mapping to the same bucket.

Load Factor (α)

n / capacity. High α → more collisions → slower ops.

Rehashing

Growing the table and re-inserting all keys when α gets high.

Clustering

Consecutive filled slots in probing, hurting performance.

Complexity Summary

Insert

O(1)*

Average; O(n) worst with bad hashing.

O(1)*

Average; O(n) if all keys collide.

Delete

O(1)*

Average constant time.

Rehash

O(n)

Occasional, amortized into O(1) inserts.

Space

O(n)

Plus empty-slot overhead (α < 1).

Ordered iterate

✗

No sorted order (use a BST/map for that).

Advantages & Disadvantages

Advantages

O(1) average insert, search, delete.
Turns nested-loop O(n²) into single-pass O(n).
Flexible keys (strings, tuples with custom hashers).
Foundation of sets, maps, caches, dedup.

Disadvantages

No ordering — can't do range queries or sorted iteration.
Worst case O(n) with adversarial keys / bad hash.
Extra memory for empty slots (load factor < 1).
Rehash pauses; poor cache locality with chaining.

C++ STL Implementation

hash_stl.cpp · unordered_map & unordered_set

#include <bits/stdc++.h>
using namespace std;

int main() {
    unordered_map<string,int> freq;   // key→value, O(1) avg
    freq["apple"]++;
    freq["apple"]++;
    if (freq.count("apple")) cout << freq["apple"]; // 2

    unordered_set<int> seen;          // membership, O(1) avg
    seen.insert(5);
    bool has = seen.count(5);       // true

    freq.reserve(1000);              // pre-size to avoid rehash
    cout << freq.load_factor();       // current α
    return 0;
}

patterns.cpp · Two Sum & frequency

// Two Sum — O(n) with a hash map
vector<int> twoSum(vector<int>& a, int target){
    unordered_map<int,int> seen;   // value → index
    for (int i = 0; i < a.size(); i++) {
        int need = target - a[i];
        if (seen.count(need)) return {seen[need], i};
        seen[a[i]] = i;
    }
    return {};
}

// Chaining hash set (illustrative)
struct HashSet {
    static const int B = 769;   // prime capacity
    vector<int> bucket[B];
    int idx(int k){ return (k % B + B) % B; }
    void add(int k){ auto& c = bucket[idx(k)];
        if (find(c.begin(),c.end(),k)==c.end()) c.push_back(k); }
    bool has(int k){ auto& c = bucket[idx(k)];
        return find(c.begin(),c.end(),k)!=c.end(); }
};

Interactive Hash Table Visualization

Bucket Target bucket Entry Collision Found

Idle

Current operation details

Operation

—

hash(key) % ${'cap'}

—

Load factor α

0.00

Steps

taken

Entries

stored

Collisions

so far

Buckets

capacity

Step — of —

Select a scenario above, or use the manual controls, then press Play. hash(k) = k mod capacity.

Manual controls — integer keys, capacity is a small prime

Keys: Capacity: Key:

✓ Done

Speed

Step-by-step operation log

Step	Key	Bucket	Action	Collisions
Run a scenario to populate the log.

Key Patterns

Hash map = O(1) lookup. The universal speedup: replace "search the array again" (O(n) inner loop) with a hash map lookup (O(1)). Two Sum, subarray-sum-equals-k, longest consecutive sequence, group anagrams all use this.

Frequency counting. map[x]++ in one pass gives you counts for anagrams, majority element, top-K, and first-unique problems. For a small fixed alphabet, an int[26]/int[128] array is even faster.

Cheat Sheet

Structure	Search	Ordered?	Notes
unordered_map / set	O(1) avg	No	Hash table; fastest lookup
map / set	O(log n)	Yes	Balanced BST; sorted iteration
Frequency array	O(1)	By index	int[26]/int[128] for small alphabets
Chaining	O(1+α)	No	Lists per bucket, handles high α
Open addressing	O(1) avg	No	Probing; cache-friendly, clusters

Learning Roadmap

Hashing Basics

Hash functions, buckets, index = hash % capacity, load factor, why O(1) average.

~2 hours

Collision Resolution

Separate chaining, linear/quadratic probing, double hashing, rehashing.

~3 hours

STL Maps & Sets

unordered_map/set vs map/set tradeoffs, custom hashers, reserve/rehash.

~2 hours

Hashing Patterns

Two Sum, frequency count, dedup, subarray sum = k, group anagrams, LRU cache.

~4 hours

Interview Preparation

Two Sum

One pass; for each element check if (target − x) is already in the map. O(n)/O(n).

Hash Map

Group Anagrams

Key each word by its sorted form or char-count signature into a map of lists. O(n·k log k).

Hashing

Subarray Sum Equals K

Prefix sum + map of prefix→count; add count of (sum − k) seen so far. O(n).

Prefix + Hash

LRU Cache

Hash map for O(1) lookup + doubly linked list for O(1) recency updates.

Hash + List

Practice Problems

EasyTwo SumHash Map

EasyContains DuplicateHash Set

EasyValid AnagramFrequency

MediumGroup AnagramsHashing

MediumTop K Frequent ElementsBucket

MediumSubarray Sum Equals KPrefix + Hash

MediumLongest Consecutive SequenceHash Set

HardLRU CacheHash + List

Key Takeaways

⚡O(1) average: hash(key) % capacity picks a bucket. Insert, search, delete are constant time when the hash spreads keys well.

💥Collisions are inevitable: resolve with chaining (lists per bucket) or open addressing (probing). Keep load factor below ~0.75 and rehash.

🚀The universal speedup: a hash map turns O(n²) nested loops into O(n) — Two Sum, frequency counts, dedup, prefix-sum tricks.

📐No ordering: need sorted iteration or range queries? Reach for a balanced BST (std::map) instead — O(log n) but ordered.