Part 2 · 2 chapters · ~12 min

Hashing

Hash functions and their properties, buckets and load factors, chaining versus open addressing, resizing and amortised cost, hash flooding and randomised seeds, hash sets and maps in each language, and the patterns hashing makes trivial (counting, grouping, two-sum, deduplication).

5

How hash tables work

Measured here: 100,000 lookups in a 10,000-item list took 200.6 ms with array.includes and 1.1 ms with Set.has. That 180× gap is the entire case for hashing.

INSIDE A HASH TABLE
hash, index, handle collisions, resize
key"acct_81723"hash function→ 2,654,435,761indexhash mod capacity (16) = 1bucket 0bucket 1acct_81723, acct_10bucket 2resizeload > 0.75 → double
swipe the figure sideways, or tap expand for full screen
1/5
hash
A hash function turns a key into a large integer, quickly and evenly. Equal keys must give equal hashes; different keys should rarely collide.
key → integer, fast and evenequal keys, equal hashes
6

Patterns hashing makes trivial

code
// two-sum: indices of two numbers adding to target, O(n)
function twoSum(a: number[], target: number): [number, number] | null {
  const seen = new Map<number, number>();
  for (let i = 0; i < a.length; i++) {
    const j = seen.get(target - a[i]); if (j !== undefined) return [j, i];
    seen.set(a[i], i);
  }
  return null;
}
// group transactions by merchant
const byMerchant = Map.groupBy(transactions, t => t.merchantId);      // ES2024
// count occurrences
const counts = new Map<string, number>(); for (const w of words) counts.set(w, (counts.get(w) ?? 0) + 1);
languagemap / setnotes
JavaScriptMap, Setinsertion-ordered; object keys by identity
Pythondict, setinsertion-ordered; keys must be hashable (immutable)
Gomap[K]Vrandom iteration order on purpose; not safe for concurrent writes
JavaHashMap, HashSetoverride equals and hashCode together
RustHashMap, HashSetSipHash by default; faster hashers available for trusted keys