Hash Maps & Sets

1. The physical picture

A hash map is an array of buckets plus a hash function. To store key → value, you hash the key to a bucket index and put the pair there. To look it up, you hash again and go straight to that bucket. No scanning — that’s where the O(1) comes from.

Two keys can hash to the same bucket (a collision), so each bucket holds a small list or probes to a nearby slot. If every key collided you’d be back to O(n); real hash functions make that vanishingly unlikely, which is why we say average-case O(1).

A set is the same structure with the values thrown away. It answers exactly one question: have I seen this?

2. The invariant

Every stored key sits in the bucket its hash points to — so a lookup only ever has to examine one bucket.

Corollary: there is no order. Iterating a hash map gives you an arbitrary sequence. If you need order, you need something else (a sorted array, or C++‘s tree-backed map).

3. Operations and complexity

The trade you are making: O(n) memory and a hash computation per access, in exchange for turning an O(n) search into O(1). Being able to state that trade out loud is what separates understanding it from reciting it.

4. C++ and JavaScript

unordered_map<int,int> m;
m[k]++;                          // CAREFUL: inserts 0 first if k is absent
if (m.count(k)) { ... }          // test WITHOUT inserting
auto it = m.find(k);
if (it != m.end()) it->second;

unordered_set<int> s;
s.insert(x);
if (s.count(x)) { ... }

map<int,int> ordered;            // tree-backed: O(log n) but keys stay sorted

const m = new Map();
m.set(k, (m.get(k) ?? 0) + 1);
if (m.has(k)) { ... }
m.size;
for (const [k, v] of m) { ... }  // insertion order

const s = new Set();
s.add(x);
if (s.has(x)) { ... }

The C++ trap that costs points: m[k] on an unordered_map default-constructs and inserts when k is absent. Writing if (m[k] > 0) silently grows the map and can turn a correct algorithm into a wrong one. Use .count() or .find() to test.

5. How you travel it

You mostly don’t — there’s no meaningful traversal, and that’s the point. The three shapes you’ll actually write:

1. Count:      for (x of arr) freq[x]++
2. Seen-set:   for (x of arr) { if (seen.has(need)) ...; seen.add(x) }
3. Group:      for (x of arr) buckets[key(x)].push(x)

Nearly every Arrays & Hashing problem is one of those three.

6. It’s the answer when…

The problem says, in any wording:

• “have I seen this before?” → set
• “how many times does each … appear?” → count map
• “find the pair/complement” → seen-map of value → index
• “group these together” → map from a canonical key to a bucket
• “is this a duplicate?” → set
• “in one pass” → almost always a map

And structurally: whenever your brute force re-scans data it has already visited.

7. The three classic mistakes

1. m[k] in C++ when you meant to test. It inserts. Use .count().
2. Using a plain {} in JavaScript with numeric keys. Keys get stringified, so 1 and "1" collide, and inherited prototype keys can surprise you. Use Map.
3. Reaching for a hash map when an array would do. For lowercase letters, int freq[26] is faster, simpler, and trivially comparable. Dense small integer keys → array.

8. What to drill

Two Sum, Contains Duplicate, Valid Anagram, Group Anagrams, Longest Consecutive Sequence. Do them back to back and notice you’re writing the same three lines each time with a different question attached — that repetition is the pattern forming.