Algorithms from zero
Hashing: code reading
Crux Read real hash-table and hash-map snippets, predict their behaviour, and pick the highest-leverage fix: chaining lookup, doubling resize, complement and frequency bugs.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skyHashing bugs hide in code that looks correct. Read each snippet, predict what it actually does under load or on edge cases, then pick the fix a careful engineer would make first.
Goal
Practise the loop you run on every hash-map task: read the code, trace it on the awkward input, and reach for the precise fix — not a vague ‘use a hash map’ wave of the hand.
Snippet 1 — chained insert and lookup
class HashTable {
constructor(size = 8) {
this.buckets = Array.from({ length: size }, () => []);
}
hash(key) {
let h = 0;
for (const ch of key) h = (h * 31 + ch.charCodeAt(0)) % this.buckets.length;
return h;
}
set(key, value) {
const b = this.buckets[this.hash(key)];
b.push([key, value]); // always push
}
get(key) {
const b = this.buckets[this.hash(key)];
for (const [k, v] of b) if (k === key) return v;
return undefined;
}
} Quiz
Completed
You call set('a', 1) then set('a', 2), then get('a'). What is returned, and what is the bug?
Heads-up get returns the FIRST matching key it scans, which is the stale ['a',1] pair. The newer pair sits behind it in the chain and is never reached.
Heads-up Nothing cancels — both pairs are stored in the chain. get finds the first one and returns 1; the duplicate-key bug is silent.
Heads-up This implementation never checks for duplicate keys, so it cannot throw. It silently stores both and returns the stale value — which is exactly the bug.
Snippet 2 — resize on load factor
set(key, value) {
if ((this.count + 1) / this.buckets.length > 0.75) this.resize();
const b = this.buckets[this.hash(key)];
b.push([key, value]);
this.count++;
}
resize() {
const old = this.buckets;
this.buckets = Array.from({ length: old.length * 2 }, () => []);
for (const bucket of old)
for (const [k, v] of bucket) {
const i = this.hash(k); // re-hash with the NEW length
this.buckets[i].push([k, v]);
}
} Quiz
Completed
Why must resize re-hash every key with the new array length instead of copying buckets straight across?
Heads-up It is correctness, not optimisation. After the length changes, hash(key) yields different indices; a key copied to its old slot would be unreachable by get, which uses the new length.
Heads-up The hash function is unchanged — only the modulus (array length) changes. That modulus change alone moves keys, which is why every key must be re-placed.
Heads-up Resize lowers the load factor and shortens chains, but collisions still occur. Re-hashing is about putting keys in the bucket the new modulus maps them to, not eliminating collisions.
Snippet 3 — two-sum with the complement pattern
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); // record AFTER the check
}
return null;
} Quiz
Completed
Why does the check for need happen BEFORE seen.set(nums[i], i), and what breaks if you swap the two lines?
Heads-up The map's final contents are the same, but the per-step lookup is not. Setting before checking lets an element find ITSELF as its own complement, producing an invalid [i, i] answer for cases like 3 + 3 = 6 with a single 3.
Heads-up It is not about speed but correctness: setting first allows self-pairing. The has-call is still needed; reordering changes the answer, not the work.
Heads-up That extra guard would patch it, but the clean, idiomatic fix is simply to record after the check. The snippet is already correct; swapping introduces the bug the guard would then have to undo.
Snippet 4 — anagram grouping by frequency key
function groupAnagrams(words) {
const groups = new Map();
for (const w of words) {
const key = w.split('').sort().join(''); // canonical key
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(w);
}
return [...groups.values()];
} Quiz
Completed
This groups anagrams correctly. For long strings, what is the cost of the key, and what is the cheaper canonical key with the same grouping result?
Heads-up Sorting is O(L log L), not O(L). A linear character-count signature is asymptotically cheaper and groups anagrams identically because anagrams have equal letter frequencies.
Heads-up The raw word groups identical strings, not anagrams — 'eat' and 'tea' would land in different groups. The key must be invariant across anagrams, which the sorted form (or count signature) provides.
Heads-up Relying on hash collisions to group anagrams is wrong and unsafe — non-anagrams would also collide. You need a deterministic canonical key (sorted or counted), not collision behaviour.
Recap
Every hash-map task is read in code: a chained set must update an existing key in place, not blindly push; resize must re-hash with the new modulus or lookups go to the wrong bucket; the complement pattern records after it checks so an element never pairs with itself; and grouping needs a canonical key that is invariant across the group — a character count beats a sort on the hot path. Read the awkward input first, then pick the precise fix.