Chapter 04 — Hashing: Maps & Sets
Chapter 04 — Hashing: Maps & Sets
Hey everyone! Welcome back to Namaste DSA!
If there's ONE technique that turns "impossible" interview problems into easy ones, it's hashing. The magic of a hash map is the O(1) lookup — instant "do I have this key?" checks. Once you internalize the "have I seen this before?" pattern, you'll spot it everywhere.
What we will cover:
- What a hash function does (key → bucket)
- Why lookups are O(1) average
- Collisions and how they're handled
- JS Map vs Object vs Set
- The "seen before?" pattern — Two Sum
- Frequency maps
- Grouping (group anagrams)
- Interview Questions
1. What is a Hash Function?
A hash function takes a key and turns it into an array index (a "bucket"). That's how it knows exactly where to store and find a value — without scanning.
┌─────────────────────────────────────────────────────────────┐
│ HOW A HASH MAP WORKS │
├─────────────────────────────────────────────────────────────┤
│ │
│ key "apple" ──► hash() ──► 3 ──► store at bucket[3] │
│ │
│ Buckets (internal array): │
│ ┌────┬────┬────┬──────────┬────┐ │
│ │ 0 │ 1 │ 2 │ 3:apple │ 4 │ │
│ └────┴────┴────┴──────────┴────┘ │
│ │
│ Later: get("apple") → hash → 3 → look in bucket[3] → O(1) │
│ │
└─────────────────────────────────────────────────────────────┘
2. Why Lookups are O(1) Average
Because the hash function jumps straight to the bucket — no scanning. Insert, search, and delete are all O(1) on average. This is the whole reason hashing is so powerful: you trade a bit of memory for blazing-fast lookups.
3. Collisions — When Two Keys Land in the Same Bucket
Different keys can hash to the same bucket. That's a collision. The common fix is chaining: each bucket holds a small list.
hash("apple") = 3
hash("grape") = 3 ← collision!
bucket[3] → [ apple ] → [ grape ] (a tiny linked list)
With a good hash function collisions are rare, so lookups stay O(1) on average. But the worst case is O(n) — if everything collides into one bucket, you're back to scanning a list. That's why we always say "O(1) average".
4. Map vs Object vs Set
| Type | Stores | Use when |
|---|---|---|
| Map | key → value pairs | Keys can be ANY type; you need ordered, frequent add/remove |
| Object | string/symbol keys → value | Simple records; keys are strings |
| Set | unique values only | "Have I seen this?" / dedupe |
// Map
const m = new Map();
m.set("a", 1); m.get("a"); m.has("a"); m.delete("a");
// Set
const s = new Set();
s.add(5); s.has(5); s.delete(5);
const unique = [...new Set([1,1,2,3,3])]; // [1,2,3]
Interview tip: prefer Map over plain objects for algorithm problems — any key type, true size via .size, and no prototype-key surprises.
5. The "Seen Before?" Pattern — Two Sum
The most famous hashing problem. Given an array and a target, find two indices that add to the target.
BRUTE FORCE: check every pair → O(n²) HASHING: remember what we've seen → O(n)
Idea: for each number, the partner I need is target - num. Have I already seen that partner?
function twoSum(nums, target) {
const seen = new Map(); // value → index
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) {
return [seen.get(need), i];
}
seen.set(nums[i], i);
}
return [];
}
HAND TRACE: twoSum([2, 7, 11, 15], 9)
i=0 num=2 need=7 seen has 7? no → store {2:0}
i=1 num=7 need=2 seen has 2? YES → return [0, 1] ✔
Solved in one pass → O(n) time, O(n) space.
6. Frequency Maps
Count how often each item appears — the backbone of dozens of problems.
function frequency(arr) {
const freq = new Map();
for (const x of arr) {
freq.set(x, (freq.get(x) || 0) + 1);
}
return freq;
}
// frequency(["a","b","a"]) → Map { "a" → 2, "b" → 1 }
7. Grouping — Group Anagrams
Group words that are anagrams of each other. The trick: anagrams share the same sorted letters, so use that as the map key.
function groupAnagrams(words) {
const groups = new Map();
for (const w of words) {
const key = w.split("").sort().join(""); // "eat"→"aet"
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(w);
}
return [...groups.values()];
}
// ["eat","tea","tan","ate"] → [["eat","tea","ate"], ["tan"]]
Interview Questions — Quick Fire!
Q: Why is a hash map lookup O(1) on average but O(n) worst case?
"The hash function maps a key directly to a bucket, so normally you find it in constant time. But collisions can put many keys in the same bucket, and in the worst case all keys collide into one bucket, turning lookups into a linear scan — O(n). With a good hash function this is rare, so we say O(1) average."
Q: How does hashing solve Two Sum in O(n)?
"As you iterate, for each number you compute the partner you'd need (target minus the number) and check a hash map of values you've already seen. If the partner is there, you've found the pair in one pass — O(n) instead of the brute-force O(n²) of checking every pair."
Q: When would you use a Set over a Map?
"A Set when you only care about presence or uniqueness — 'have I seen this?' or removing duplicates. A Map when you need to associate each key with a value, like counting frequencies or mapping a value to its index."
Q: What's a collision and how is it handled?
"A collision is when two different keys hash to the same bucket. The common solution is chaining — each bucket holds a small list of entries. Another is open addressing, where you probe for the next free slot. Good hashing keeps collisions rare."
Q: Map vs plain Object in JavaScript for algorithms?
"Map is usually better: it accepts any key type, preserves insertion order, gives the count via .size, and has no prototype key collisions like '__proto__'. Objects are fine for simple string-keyed records."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| Hash function | key → bucket index, direct jump. |
| Lookup | O(1) average, O(n) worst (collisions). |
| Collision | Two keys, one bucket → chaining. |
| Map / Set | Map = key→value; Set = unique values. |
| "Seen before?" | The core pattern — Two Sum in O(n). |
| Frequency map | Count occurrences in O(n). |
| Grouping | Use a canonical key (e.g. sorted string). |
What's Next?
Chapter 05 covers Recursion & the Call Stack — the foundation for trees, graphs, backtracking, and dynamic programming. We'll draw the call stack and recursion tree step by step so it finally clicks.
Keep coding, keep grinding! See you in the next one!
Post a Comment