Hash Map
A Hash Map is a data structure that stores key → value pairs and supports lookup, insert, and delete in O(1) on average. It is usually the first tool to reach for when a problem asks "have I seen this before", "count occurrences", or "find the complement of a value".
Its power comes from trading memory for speed: instead of rescanning the array every time (O(n)), you remember what you've already seen and look it up in one step. What matters is choosing the right key and handling the missing-key case cleanly.
Like gym lockers — if you know the locker number, you grab your stuff right away instead of opening each locker to check.
How to spot it
When you see these cues in the problem, reach for Hash Map
| Keyword in the problem | Why it points to this topic |
|---|---|
| O(1) lookup | Need fast existence checks or value reads |
| frequency counting | Count occurrences of characters or items |
| pair sum = X | Store complements seen so far, check in O(1) |
| detect duplicates | Use a Set or Map to remember what you have seen |
| group anagrams | Hash key = sorted characters |
When to use
4 typical situations where this topic applies
You need lookups / counts / existence checks in O(1) on average
You need to count the frequency of characters / elements
You need to map one key to another value (anagram, isomorphic strings)
You need to detect duplicates or complements
When NOT to use
3 situations where this topic doesn't fit — know them so you don't overuse them
The array is already sorted: Two Pointers uses less memory (O(1) instead of O(n))
The domain is tiny and fixed (e.g. 26 letters): an array index is faster, with less hashing overhead
You need to iterate in sorted order: TreeMap / Sorted Map fits better than HashMap
Illustration
A diagram of how this topic works.
hash() turns a key into an array index — direct lookup, no scan of the array.
Code template
Most problems in this topic share this scaffold — copy it, then fill in the problem-specific logic.
function pattern(input: T[]): R {
const map = new Map<K, V>() // or: const seen = new Set<K>()
for (const item of input) {
// 1. Probe the map first
if (map.has(someKey(item))) {
// reuse what was stored
}
// 2. Update the map
map.set(someKey(item), someValue(item))
}
return assembleResult(map)
}Recap
A quick summary — reread it before your interview
Key points
Map.set(key, value) and Map.get(key) are O(1) on average
In JS use a plain object or a Map.
Map preserves insertion order; an object does too for string keys, but numeric keys get reordered — use a Map when you need a stable order.
Use a Set when you only need "does it exist" (no value) — it saves memory.
Use a Map when you need to store both key and value.
A hash collision is two different keys hashing to the same slot.
- Two ways to resolve it: Chaining (each slot is a list of (key, value) pairs, searched linearly within the slot) or Open addressing (find the next empty slot using a probing formula).
- Both are O(n) in the worst case, but with a good hash function and a load factor < 0.75 it is extremely rare.
Load factor = n/m (number of elements / number of slots).
Once it passes a threshold (~0.75) → the table auto-rehashes to grow, costing O(n) amortized.
Common mistakes
Forgetting to check that the key exists before incrementing a count (NaN bug)
Using an object as a key in a plain object — it gets stringified and the key is lost
Treating load factor as unimportant — once it is high (> 0.75), collisions grow quickly and operations get much slower
Complexity
Time O(1) average / O(n) worst, Space O(n)Practice problems for this topic
Grouped by difficulty — work through them in order to build confidence