Hash Tables with Maps

Suppose you have a list of ten thousand products and you need the price of one, identified by its id. A linear search walks the list item by item; done ten thousand times, that is a hundred million comparisons. There is a better way: store each product in a place chosen by its id, so that given the id you can jump straight to the right slot without scanning anything at all. That is what a hash table does, and it is the structure behind almost every fast lookup in computing.

JavaScript's Map is a hash table you can use directly. It stores key-value pairs and, on average, finds a value by its key in constant time — O(1) — whether the Map holds ten entries or ten million.

flowchart LR
  K["key: username"] --> H["hash function"]
  H --> B["bucket index"]
  B --> V["value: user record"]
  style H fill:#e0900b,color:#fff

A hash function turns the key into a bucket index, and the value lives in that bucket.

How a hash table works

Three pieces collaborate. A hash function takes a key and returns a number; that number is folded into the range of an internal array to pick a bucket; and each bucket holds the key-value pair, or a small list of them. When you set a key, the table hashes it, finds its bucket, and stores the pair there. When you get it later, the same key hashes to the same number, lands in the same bucket, and the value comes straight back — no scanning required.

The miracle word is average. A good hash function spreads keys evenly, so each bucket holds one pair and lookup stays O(1). But two different keys can legally land in the same bucket — a collision — and the table must have a plan for that, which is the detail that separates a toy map from a production one.

A Map stores key-value pairs; get, size, and has are all O(1) on average. Press Run.

const prices = new Map();
prices.set('apple', 0.5);
prices.set('bread', 2.25);
console.log(prices.get('apple'));
console.log(prices.size);
console.log(prices.has('bread'));

Why Map, not a plain object?

A plain object can hold key-value pairs too, so why reach for a Map? Because objects carry hidden assumptions. An object's keys are always coerced to strings, so the number 1 and the string '1' become the same key. A Map keeps its keys exactly as you gave them: a number key stays a number, and you can even use an object or a function as a key, which an ordinary object cannot do reliably.

A Map also remembers the order in which you added its entries and exposes its size directly through the size property. A for...of loop walks those entries in that same insertion order, handing you each pair as a two-element array — something a plain object cannot promise for non-string keys. For a collection whose whole job is to map arbitrary keys to values, Map is the honest tool.

flowchart TD
  O["plain object<br/>keys become strings"] --> O1["number 1 and string 1 collide"]
  M["Map<br/>keys keep their type"] --> M1["number 1 and string 1 stay distinct"]
  style M fill:#1e7f3d,color:#fff
  style O fill:#b91c1c,color:#fff

Objects stringify their keys, so 1 and '1' collide. A Map treats them as distinct keys.

A frequency counter built on a Map: read with get, write with set.

function frequency(items) {
  const counts = new Map();
  for (const item of items) {
    counts.set(item, (counts.get(item) || 0) + 1);
  }
  return counts;
}

const f = frequency(['a', 'b', 'a', 'c', 'a', 'b']);
console.log(f.get('a'));
console.log(f.get('b'));
console.log(f.get('c'));

Collisions and the load factor

Collisions are not a bug; they are inevitable. A hash function maps an infinite set of possible keys into a finite set of buckets, so eventually two keys must share one. The standard fix is chaining: each bucket holds a short list of every pair that hashed there, and a lookup walks that list to find the matching key.

As long as the keys spread evenly and the table stays large enough, each list stays tiny and lookup remains effectively O(1). The ratio of entries to buckets is called the load factor, and real hash tables resize themselves — re-hashing every entry into a bigger array — once that ratio crosses a threshold. You never manage any of this yourself with a Map; the engine does it. Understanding it, though, is what stops you treating hash tables as magic, and it explains the rare worst case where a hostile set of keys degrades a Map toward O(n).

flowchart LR
  B["bucket 3"] --> N1["cat: 1"] --> N2["dog: 2"]
  style B fill:#3776ab,color:#fff
  style N1 fill:#e0900b,color:#fff
  style N2 fill:#e0900b,color:#fff

Chaining: a bucket holds a small list of all the pairs that hashed to the same index.

A toy hash table: keys of length 3 all land in bucket 3, so chaining stores both.

function makeHashTable(buckets) {
  const table = [];
  for (let i = 0; i < buckets; i++) table.push([]);
  return {
    set(key, value) {
      const i = key.length % buckets;
      const bucket = table[i];
      const entry = bucket.find(e => e.key === key);
      if (entry) entry.value = value;
      else bucket.push({ key, value });
    },
    get(key) {
      const i = key.length % buckets;
      const entry = table[i].find(e => e.key === key);
      return entry ? entry.value : undefined;
    }
  };
}

const ht = makeHashTable(4);
ht.set('cat', 1);
ht.set('dog', 2);
console.log(ht.get('cat'));
console.log(ht.get('dog'));

Exercise

What does this print? A Map keeps a number key and a string key distinct. get on a missing key returns a specific value — what is it?

const m = new Map();
m.set(1, 'number one');
m.set('1', 'string one');
console.log(m.get(1));
console.log(m.get('1'));
console.log(m.get(2));

Your prediction — what does this print?

Exercise

Write makeMap(pairs) that takes an array of [key, value] pairs and returns a Map containing each one.

function makeMap(pairs) {
  // build and return a Map
}

function makeMap(pairs) {
  const m = new Map();
  for (const [key, value] of pairs) {
    m.set(key, value);
  }
  return m;
}

Exercise

This tally uses square-bracket access on a Map, the way you would on an object. A Map is not indexed that way, so every count comes back wrong. Rewrite the two bracket lines using the proper Map methods so the counts are correct.

function tally(items) {
  const counts = new Map();
  for (const item of items) {
    counts[item] = (counts[item] || 0) + 1;
  }
  return counts;
}

function tally(items) {
  const counts = new Map();
  for (const item of items) {
    counts.set(item, (counts.get(item) || 0) + 1);
  }
  return counts;
}

Exercise

On average, what is the time complexity of looking up a value in a Map by its key?

Exercise

Write groupBy(arr, keyFn) that groups the items of arr into a Map. Each key is keyFn(item), and each value is an array of every item that produced that key, in their original order. If arr is empty, return an empty Map.

function groupBy(arr, keyFn) {
  // return a Map of key -> array of items
}

function groupBy(arr, keyFn) {
  const groups = new Map();
  for (const item of arr) {
    const key = keyFn(item);
    if (!groups.has(key)) {
      groups.set(key, []);
    }
    groups.get(key).push(item);
  }
  return groups;
}

Recap

A hash table places each key in a bucket chosen by a hash function, giving average O(1) lookup.
A Map is JavaScript's hash table: set, get, has, and size do the work.
Map keys keep their real type and insertion order; object keys are always strings.
Collisions are handled by chaining, and the table quietly resizes as its load factor grows.
Reach for a Map whenever the keys are not a fixed set of known strings.

Next you will model relationships that are not linear at all — trees and graphs — and traverse them with recursion and queues.

How a hash table works

Why Map, not a plain object?

Collisions and the load factor

Recap

Checkpoint quiz

Go deeper — technical resources