Hash Maps and Sets
Hash Maps and Sets in JavaScript
If you learn one structure properly, make it the hash map. More interview problems collapse from O(n squared) to O(n) with a Map than with anything else in this tutorial.
What makes it fast
A hash map turns a key into a number, and that number is a position. It does not search - it calculates where the value should be and looks there. That is why lookup is O(1) whether the map holds ten entries or ten million.
The cost is memory, and the fact that the order is not something you should reason about beyond insertion order.
Map, Set, and plain objects
The three, and when each fits
javascript
// Map — any key type, remembers insertion order, has .size
const scores = new Map()
scores.set("ada", 90)
scores.set("grace", 95)
scores.get("ada") // 90
scores.has("ada") // true
scores.size // 2
// Set — membership only, no values
const seen = new Set([1, 2, 2, 3])
seen.has(2) // true
seen.size // 3, duplicates collapse
// Plain object — string keys only, and it inherits
const counts = {}
counts.ada = 90
console.log(scores.get("ada")) // 90
console.log(seen.has(2)) // true
console.log(counts.ada) // 90 — a plain object uses dot access
console.log("ada" in {}) // false
console.log("toString" in {}) // true — objects inherit, Maps do notReach for Map when keys are added and removed at runtime, when keys are not strings, or when you need .size. Reach for Set when you only care whether something is present.
A plain object is fine for a fixed, known set of keys. It is the wrong tool for counting arbitrary input, because every object already has inherited keys:
Why a plain object bites
javascript
const counts = {}
console.log(counts["constructor"]) // a function, not undefined
console.log("toString" in counts) // true
// A Map has none of this.
const safe = new Map()
console.log(safe.get("constructor")) // undefined
console.log(safe.has("toString")) // falseThe pattern that keeps recurring
Almost every use is the same shape: as you walk the input, remember something so you never have to look back.
Three variations on one idea
javascript
// 1. Have I seen this before?
function hasDuplicate(items) {
const seen = new Set()
for (const n of items) {
if (seen.has(n)) return true
seen.add(n)
}
return false
}
// 2. How many times have I seen it?
function frequency(items) {
const counts = new Map()
for (const n of items) counts.set(n, (counts.get(n) || 0) + 1)
return counts
}
// 3. Where did I see it?
function firstIndexOf(items) {
const at = new Map()
items.forEach((n, i) => {
if (!at.has(n)) at.set(n, i)
})
return at
}
console.log(hasDuplicate([1, 2, 1])) // true
console.log(frequency("aab").get("a")) // 2
console.log(firstIndexOf([5, 6, 7], 6)) // 1What O(1) does not mean
It does not mean free. Hashing a key takes work, and hashing a long string takes work proportional to its length. It also does not mean constant in the worst case - with unlucky keys a hash map degrades. For interview purposes O(1) is the right answer; for a hot loop over long string keys, measure.
Grouping, the other everyday use
Group anagrams
javascript
function groupAnagrams(words) {
const groups = new Map()
for (const word of words) {
// Same letters, same key.
const key = [...word].sort().join("")
if (!groups.has(key)) groups.set(key, [])
groups.get(key).push(word)
}
return [...groups.values()]
}
console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat"]))
// [["eat","tea","ate"], ["tan","nat"]]Sorting each word costs O(m log m), so the whole thing is O(n × m log m) - still far better than comparing every pair.