Hash Tables: Sets & Maps

"Have I seen this before?" and "how many times?" are the most common questions in real code. A hash table answers both in O(1) on average, which is why every language ships one.

beginner⏱ 14 min read

←Builds on

1Arrays & Dynamic ArraysA hash table is an array of buckets indexed by the hash of the key.0Big-O & Growth RatesAverage O(1) versus worst case O(n) is exactly the distinction Big-O taught you to make.

Leads to→

1Prefix Sums, Two Pointers & Sliding WindowCounting subarrays with a given sum stores the prefix sums seen so far in a hash map.5Balanced Trees & set / mapstd::set and std::map are the ordered counterparts of unordered_set and unordered_map.5Trie & AutocompleteThe children of a trie node are often kept in a map from letter to child.11Rolling Hash & Rabin–KarpA rolling hash is a hash function that updates in O(1) as the window slides.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Sets and maps

Two everyday tools are built on hash tables:

A set stores unique keys and answers "is x in it?". C++ unordered_set, Python set, Java HashSet.
A map (dictionary) stores key → value pairs: word → count, user id → profile. C++ unordered_map, Python dict, Java HashMap.

The idea: a hash function h(k) turns any key, a number or a string, into an index of an array of buckets. To insert, compute h(k) and put the key there. To look up, compute h(k) again and look in that one bucket. No scanning, no sorting: the key itself tells you where it lives.

02Collisions and chaining

There are far more possible keys than buckets, so two keys will sometimes land in the same bucket. That is a collision, and it is normal, not an error.

The simplest fix is separate chaining: each bucket holds a small list. With h(k) = k mod 7, the keys 15, 8 and 22 all give 1, so bucket 1 holds a chain of three. A lookup hashes to the bucket and then compares keys along that chain only.

The other classic approach is open addressing: if a bucket is taken, probe the next one (and the next) until you find a free slot. Either way, the work per operation is about the length of one chain, so we want chains to stay short.

03Load factor and rehashing

The load factor α = (number of keys) / (number of buckets) is the average chain length. With a good hash function that spreads keys evenly, each operation costs about O(1 + α).

So the table keeps α bounded. When it passes a limit (around 1 for unordered_map, 2/3 for Python's dict), it rehashes: allocates about twice as many buckets and reinserts every key, because h(k) depends on the bucket count.

A single rehash is O(n), but it happens after the table has doubled, exactly like a growing vector. The result is expected O(1) insert, find and erase, amortized over all operations.

04When to reach for it, and the traps

Use a hash set or map when you need membership, counting or grouping: detect duplicates, count word frequencies, find a pair with a given sum (store what you have seen), group anagrams by a sorted key.

Know the limits:

Worst case is O(n): if many keys collide, a chain becomes a list. Adversarial inputs on contest sites can do this on purpose to unordered_map; a randomized hash defends against it.
No order: iteration order is arbitrary. If you need sorted keys, min/max or "next larger key", use an ordered map/set (a balanced tree, O(log n)).
Keys must be hashable and not change while stored. Mutating a key inside a set loses it.

Cost at a glance

Insert / find / erase (expected)O(1)

Worst case (all keys collide)O(n)

RehashO(n), rare

Ordered map / set insteadO(log n)

Remember

A hash function sends each key straight to a bucket, so lookups skip scanning entirely.
Collisions are normal; chaining keeps them correct and a bounded load factor keeps them short.
Hash tables give expected O(1) but no ordering; use a tree map when order matters.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch bucket 1 grow a chain, then compare a lookup that walks the chain with one that hits an empty bucket. Try 2 buckets to force long chains.

Interactive visualizerfocus here, then space ← →

Hash table: h(k) = k mod 7

[0]∅

[1]∅

[2]∅

[3]∅

[4]∅

[5]∅

[6]∅

A hash table maps keys to 7 buckets via h(k) = k mod 7. Ideally each lookup touches just one bucket.

Pseudocode

 1 table of B buckets; h(k) = k mod B 2 insert k: append to bucket h(k) (chaining on collision) 3 find k: hash to bucket h(k), then scan its chain 4   compare each key until found or chain ends 5 // expected O(1) while the load factor stays bounded

1 / 1

Check

Three questions. Pick an answer to see why.

With 7 buckets and h(k) = k mod 7, which bucket does key 30 go to?

You must check whether any two of n numbers sum to a target. What is the fastest typical approach?

You need the smallest key larger than x, many times. Which structure fits?

Practice

Real problems to lock it in, easiest first.

CSESDistinct Numbers beginner↗LeetCodeTwo Sum beginner↗LeetCodeValid Anagram beginner↗LeetCodeGroup Anagrams intermediate↗LeetCodeLongest Consecutive Sequence intermediate↗