Hash maps and sets

Instant lookups

A hash map turns a key into an array index with a hash function, so finding "Momo" among a million dishes takes about one step. JavaScript's Map and Set are hash tables. They're the single most useful tool for making slow code fast.

A tiny hash table, then Map

function hash(key, size) {
  let h = 0;
  for (const ch of String(key)) h = (h * 31 + ch.charCodeAt(0)) % size;
  return h;
}

class HashTable {
  constructor(size = 8) { this.buckets = Array.from({ length: size }, () => []); }
  set(key, value) {
    const bucket = this.buckets[hash(key, this.buckets.length)];
    const entry = bucket.find((e) => e[0] === key);
    if (entry) entry[1] = value; else bucket.push([key, value]);
  }
  get(key) {
    const bucket = this.buckets[hash(key, this.buckets.length)];
    return bucket.find((e) => e[0] === key)?.[1];
  }
}

const t = new HashTable();
t.set("Momo", 180); t.set("Thukpa", 220); t.set("Lassi", 90);
console.log(t.get("Thukpa"), t.buckets.map((b) => b.length));

const prices = new Map([["Momo", 180]]);
prices.set("Tea", 50);
console.log(prices.get("Tea"), prices.has("Pizza"), prices.size);

Counting: counts.set(x, (counts.get(x) ?? 0) + 1).
Seen-before checks: Set.
Lookup by id instead of searching arrays.

Instant lookups

A tiny hash table, then Map

The rest of this lesson