How a lookup worksCore idea
A hash map turns a key into an array index using a hash function: a function that maps any key to a number in the range 0 to capacity − 1. The value is stored at that index, so finding it later is one calculation and one jump.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","actorBkg":"#e7f5ff","actorBorder":"#1e1e1e","noteBkgColor":"#fff9db","noteBorderColor":"#1e1e1e"}}}%%
graph LR
K["key: 'cat'"] --> H["hash('cat') % 16"]
H --> B["bucket[5]"]
B --> C{"key there?"}
C -->|yes| V["return value"]
C -->|no| M["return undefined"]
class K orange
class H yellow
class B blue
class V green
class M red
classDef orange fill:#ffd8a8,stroke:#1e1e1e,color:#1e1e1e
classDef blue fill:#a5d8ff,stroke:#1e1e1e,color:#1e1e1e
classDef green fill:#b2f2bb,stroke:#1e1e1e,color:#1e1e1e
classDef red fill:#ffc9c9,stroke:#1e1e1e,color:#1e1e1e
classDef violet fill:#d0bfff,stroke:#1e1e1e,color:#1e1e1e
classDef yellow fill:#ffec99,stroke:#1e1e1e,color:#1e1e1e
classDef grey fill:#e9ecef,stroke:#1e1e1e,color:#1e1e1eclass HashMap {
private buckets: Array<[string, any][]> = Array(16).fill(null).map(() => []);
set(key: string, value: any) {
const index = this.hash(key) % this.buckets.length;
const bucket = this.buckets[index];
const existing = bucket.find(([k]) => k === key);
if (existing) existing[1] = value;
else bucket.push([key, value]);
}
get(key: string): any {
const index = this.hash(key) % this.buckets.length;
const bucket = this.buckets[index];
const pair = bucket.find(([k]) => k === key);
return pair ? pair[1] : undefined;
}
private hash(key: string): number {
let hash = 0;
for (const char of key) hash = (hash * 31 + char.charCodeAt(0)) % 2147483647;
return Math.abs(hash);
}
}Collision handlingHow it works
Two different keys can land on the same index. That is called a collision, and there are two main ways to deal with it:
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","actorBkg":"#e7f5ff","actorBorder":"#1e1e1e","noteBkgColor":"#fff9db","noteBorderColor":"#1e1e1e"}}}%%
graph LR
B0["bucket 4"] --> E0["empty"]
B1["bucket 5"] --> N1["'cat' → 3"] --> N2["'act' → 7"]
B2["bucket 6"] --> N3["'dog' → 1"]
class B0,B1,B2 blue
class N1,N2 orange
class N3 green
class E0 grey
classDef orange fill:#ffd8a8,stroke:#1e1e1e,color:#1e1e1e
classDef blue fill:#a5d8ff,stroke:#1e1e1e,color:#1e1e1e
classDef green fill:#b2f2bb,stroke:#1e1e1e,color:#1e1e1e
classDef red fill:#ffc9c9,stroke:#1e1e1e,color:#1e1e1e
classDef violet fill:#d0bfff,stroke:#1e1e1e,color:#1e1e1e
classDef yellow fill:#ffec99,stroke:#1e1e1e,color:#1e1e1e
classDef grey fill:#e9ecef,stroke:#1e1e1e,color:#1e1e1eChainingmost common
Each bucket stores a linked list (or a balanced tree). A collision just adds to the list. Most real implementations do this.
Open addressingprobing
If a slot is taken, try the next one (linear probing) or jump by a growing step (quadratic). Used in some high-performance maps.
Time complexityCompare
| Operation | Average | Worst |
|---|---|---|
| Get | O(1) | O(n) |
| Set | O(1) | O(n) |
| Delete | O(1) | O(n) |
| Contains | O(1) | O(n) |
Pattern 1: Frequency countingPattern
Count how often each thing appears. It is the base of anagram, duplicate and “most frequent” problems.
function charFrequency(s: string): Map<string, number> {
const freq = new Map<string, number>();
for (const ch of s) {
freq.set(ch, (freq.get(ch) || 0) + 1);
}
return freq;
}Pattern 2: Two Sum (remember what you have seen)Pattern
Store each value as you pass it. For every new value, check whether its partner is already stored.
function twoSum(nums: number[], target: number): [number, number] {
const seen = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) return [seen.get(complement)!, i];
seen.set(nums[i], i);
}
throw new Error("No pair found");
}Pattern 3: GroupingPattern
Build a key that is the same for everything in a group, then collect items under it. For anagrams, the sorted letters make a good key: “eat”, “tea” and “ate” all become “aet”.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","actorBkg":"#e7f5ff","actorBorder":"#1e1e1e","noteBkgColor":"#fff9db","noteBorderColor":"#1e1e1e"}}}%%
graph LR
W1["eat"] --> K1["aet"]
W2["tea"] --> K1
W3["ate"] --> K1
W4["tan"] --> K2["ant"]
W5["nat"] --> K2
W6["bat"] --> K3["abt"]
class W1,W2,W3,W4,W5,W6 blue
class K1 orange
class K2 green
class K3 violet
classDef orange fill:#ffd8a8,stroke:#1e1e1e,color:#1e1e1e
classDef blue fill:#a5d8ff,stroke:#1e1e1e,color:#1e1e1e
classDef green fill:#b2f2bb,stroke:#1e1e1e,color:#1e1e1e
classDef red fill:#ffc9c9,stroke:#1e1e1e,color:#1e1e1e
classDef violet fill:#d0bfff,stroke:#1e1e1e,color:#1e1e1e
classDef yellow fill:#ffec99,stroke:#1e1e1e,color:#1e1e1e
classDef grey fill:#e9ecef,stroke:#1e1e1e,color:#1e1e1efunction groupAnagrams(strs: string[]): string[][] {
const map = new Map<string, string[]>();
for (const s of strs) {
const key = s.split('').sort().join('');
if (!map.has(key)) map.set(key, []);
map.get(key)!.push(s);
}
return Array.from(map.values());
}Common mistakesPitfalls
In the interviewIn the interview
Trading memory for speed is the most common optimisation interviewers expect. Say the trade out loud.
Frequently asked questionsFAQ
What is the time complexity of a hash map lookup?
The average case is O(1) for insert, lookup, and delete because a hash function maps a key directly to a bucket. The worst case degrades to O(n) when many keys collide into one bucket, which is why load factors, resizing, and collision strategy keep the average constant.
When should you use a hash map instead of an array?
Use a hash map when keys are arbitrary values like strings, or when the key space is large and sparse. Use an array when keys are small dense integers, for example a character frequency table of size 26, which gives O(1) space and avoids hashing overhead.
How do hash maps handle collisions?
Two common strategies are chaining, storing colliding keys in a list at the same bucket, and open addressing, probing to the next free slot. Modern languages like Java and Go use chaining with a balanced-tree fallback for oversized buckets so worst-case lookup stays O(log n).
Now explain hash maps to me out loud
I'll give you interview problems and ask follow-ups, like a real interviewer.