Maps and Sets

How it works

A hash function converts a key into an integer, which is reduced to a bucket index. Storing and retrieving both compute that index directly, so neither searches.

Concept

Expected, not guaranteed

If several keys hash to the same bucket, they must be distinguished by scanning that bucket. With a good hash function and a reasonable load factor, buckets stay short and lookups are effectively constant. In the pathological case where everything collides, lookup degrades to O(n).

The trade is memory for time: O(n) space for O(1) access.
Operation	Time	Space
Insert	O(1) expected	O(1)
Lookup	O(1) expected	O(1)
Delete	O(1) expected	O(1)
Iterate all	O(n)	O(1)
Any of the above, worst case	O(n)	O(1)

The trade is memory for time: O(n) space for O(1) access.

Set or map?

Question	Structure
Have I seen this?	Set
How many times have I seen this?	Map to a count
Where did I see this?	Map to an index
What goes with this?	Map to any value

Pick the one that answers the question you actually have.

When a hash table is wrong

Order or adjacency matters — a hash table discards position.
You need range queries or the nearest key — that is a sorted structure.
The key space is tiny and dense, where an array of counters is faster and smaller.
Memory is the binding constraint.

Quick quiz

How it works

Expected, not guaranteed

Set or map?

When a hash table is wrong

Hash tables

You’ve reached the end

Search Tech Epitome

Search Tech Epitome

Maps and Sets

How it works

Expected, not guaranteed

Set or map?

When a hash table is wrong

You’ve reached the end