Hash Maps and Sets for O(1) Lookup

Nearly every "how do I make this fast" question in frontend code resolves to the same answer: replace a linear scan with a hash-based lookup. This lesson is about understanding why that works, not just reaching for Map on faith.

The problem, restated from the first lesson

Back in the very first lesson of this course, excludedTags.includes(...) called inside a loop turned an O(n) filter into an O(n²) one — because .includes() on an array has to check every element, one at a time, until it finds a match or reaches the end. That's a linear operation, and calling a linear operation inside another loop is where quadratic behavior sneaks in.

// O(n * m): .includes() is O(m) per call, called n times
function filterExcluded(items, excludedIds) {
  return items.filter((item) => !excludedIds.includes(item.id));
}

The fix: trade the array for a Set

// O(n): Set.has() is O(1) average per call, called n times
function filterExcludedFast(items, excludedIds) {
  const excludedSet = new Set(excludedIds); // O(m) to build, once
  return items.filter((item) => !excludedSet.has(item.id));
}

Same logic, same result — but building the Set once up front (an O(m) cost, paid a single time) means every subsequent .has() call is O(1) average instead of O(m). The total work drops from O(n * m) to O(n + m), which simplifies to O(n) when the two collections are similar sizes — a real, measurable difference the moment either collection grows past a trivial size.

Why hashing gets you there: the mechanism, briefly

A hash map doesn't search for your key. It computes where the key should be. A hash function takes a key and produces a number — deterministically, so the same key always produces the same number — which is then used to pick a "bucket" (a slot) in an internal array. set computes the bucket and writes there; get computes the same bucket for the same key and reads directly from it. No scanning required, in the typical case — which is why it's O(1): the cost doesn't grow with how many other entries are in the map, only with the (fixed) cost of hashing the key itself.

The "in the typical case" qualifier is doing real work. If many different keys happen to hash to the same bucket (a collision), that bucket has to store multiple entries and check them one by one — degrading toward a linear scan in the worst case. Well-designed hash functions and enough buckets make collisions rare in practice, which is exactly what "O(1) average, not worst-case-guaranteed" means, and it's the same average-versus-worst-case distinction from the amortized-cost lesson two parts ago.

Map versus plain object, briefly

{} can act like a hash map, but Map is the better default for this kind of work: Map preserves insertion order reliably, accepts any value as a key (not just strings and symbols), has a real .size, and doesn't carry the risk of colliding with inherited properties like toString or __proto__ that a plain object does. Set is the same idea specialized to "do I have this value," without a paired value to store.

The gotcha: reference equality for object keys

const map = new Map();
map.set({ id: 1 }, "first user");
 
map.get({ id: 1 }); // undefined — NOT "first user"

Map compares keys the same way === compares objects: by reference, not by content. Two separately-created objects that look identical are still two different keys, exactly as covered in the JavaScript foundations track's lesson on arrays and objects and their reference semantics. If you need to look values up "by shape" (say, by a record's id field), key the map by a primitive extracted from the object — map.set(user.id, user) — not by the object itself, unless you specifically intend reference-based identity.

One genuine exception worth knowing: NaN. NaN === NaN is famously false, but Map and Set use a slightly different equality internally (SameValueZero) that specifically treats NaN as equal to itself. So map.set(NaN, "value"); map.get(NaN) correctly returns "value" — one of the few places Map's equality and === genuinely diverge.

What to remember

• Array.prototype.includes() is O(m) per call. Set.prototype.has() is O(1) average per call. Calling the array version inside a loop is the most common accidental-quadratic pattern in real frontend code.
• Hashing computes where a key belongs rather than searching for it, which is what makes O(1) possible — but collisions can degrade it toward O(n) in the worst case, so it's properly described as O(1) average.
• Map/Set key objects by reference identity, not by shape — two separately-created lookalike objects are different keys. Key by a stable primitive (like an id) when you want shape-based lookup.
• Map/Set use SameValueZero equality, which specifically (and usefully) treats NaN as equal to itself, unlike ===.