Hashing and Hash Tables

1What a Hash Function Does

A hash function takes an input of arbitrary size (a string, an object, anything) and deterministically produces a fixed-size output — usually an integer — called a hash code. The same input always produces the same hash code.

function simpleHash(str) {
  let hash = 0;
  for (let i = 0; i < str.length; i++) {
    hash = (hash * 31 + str.charCodeAt(i)) | 0; // |0 keeps it a 32-bit integer
  }
  return hash;
}
simpleHash("hello"); // always the same number for "hello"
simpleHash("world"); // a different number (almost always)

A good hash function is fast, deterministic, and spreads outputs evenly across the possible output range, minimizing how often two different inputs produce the same output.

2What a Hash Table Is

A hash table is a data structure that uses a hash function to map keys to array indices (called "buckets"), giving average O(1) lookup, insertion, and deletion — dramatically faster than scanning a list (O(n)) for large datasets.

key "name" -> hash("name") -> 47 -> bucket[47 % tableSize] -> stores { key: "name", value: "Ana" }

JavaScript's Object, Map, and Set are all implemented internally using hash tables — this is why property/key lookup on them is fast regardless of how many entries exist.

3Hash Collisions

Two different inputs can produce the same hash code (or map to the same bucket after modulo) — this is called a collision, and it's mathematically unavoidable once you have more possible inputs than output slots (the pigeonhole principle).

hash("Alice") % 10 = 3
hash("Bob")   % 10 = 3   <- collision, both land in bucket 3

4Collision Resolution Strategies

Separate chaining, bucket 3: [ {key:"Alice",...}, {key:"Bob",...} ]
  — lookup for "Bob" hashes to bucket 3, then linearly scans that
    small list to find the matching key

Real-world hash table implementations (including JS engines' internal Map/Object implementations) use variations of these strategies, often switching approach based on how full the table is.

5Load Factor and Resizing

Load factor = number of entries ÷ number of buckets. As load factor rises, collisions become more frequent and performance degrades toward O(n). Hash tables automatically resize (allocate a bigger underlying array and rehash every entry) once load factor crosses a threshold (commonly ~0.75), to keep operations close to O(1) on average.

1A Minimal Hash Table with Separate Chaining

class HashTable {
  constructor(size = 16) {
    this.buckets = new Array(size).fill(null).map(() => []);
    this.size = size;
    this.count = 0;
  }

  _hash(key) {
    let hash = 0;
    const str = String(key);
    for (let i = 0; i < str.length; i++) {
      hash = (hash * 31 + str.charCodeAt(i)) % this.size;
    }
    return hash;
  }

  set(key, value) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    const existing = bucket.find(entry => entry[0] === key);
    if (existing) {
      existing[1] = value; // update
    } else {
      bucket.push([key, value]);
      this.count++;
    }
  }

  get(key) {
    const bucket = this.buckets[this._hash(key)];
    const entry = bucket.find(entry => entry[0] === key);
    return entry ? entry[1] : undefined;
  }

  has(key) {
    return this.buckets[this._hash(key)].some(entry => entry[0] === key);
  }

  delete(key) {
    const bucket = this.buckets[this._hash(key)];
    const index = bucket.findIndex(entry => entry[0] === key);
    if (index === -1) return false;
    bucket.splice(index, 1);
    this.count--;
    return true;
  }
}

2Why the Modulo Matters

hash % this.size compresses a potentially huge hash number down into a valid array index (0 to size - 1). This is the step that actually creates collisions in practice — even a perfect, evenly-distributed hash function will produce colliding bucket indices once you have more keys than buckets.

3Why This Beats a Plain Array of [key, value] Pairs

// Naive linear search — O(n) every lookup
function linearGet(pairs, key) {
  for (const [k, v] of pairs) if (k === key) return v;
  return undefined;
}

// Hash table — O(1) average: jump straight to the right bucket,
// then scan only the (typically very short) list of collisions within it

With 1,000,000 entries, a linear search checks up to 1,000,000 pairs in the worst case. A well-sized hash table checks roughly 1,000,000 / bucketCount entries — a handful, not a million.

4Worst-Case vs Average-Case

The worst case happens with a poor hash function (everything collides) or a deliberately crafted "hash flooding" attack against a predictable hash function — one reason production hash table implementations use randomized hash seeds.

5Resizing (Rehashing) Sketch

_resize(newSize) {
  const oldEntries = this.buckets.flat();
  this.size = newSize;
  this.buckets = new Array(newSize).fill(null).map(() => []);
  this.count = 0;
  for (const [key, value] of oldEntries) this.set(key, value); // re-hash every entry into the new size
}

Every entry must be rehashed because hash % size depends on size — changing the table size invalidates every existing bucket assignment.

⚠️ Common Pitfalls

1. Using a hash function that only depends on length or a single character — produces massive collision rates; always fold in every character's contribution (as _hash above does).
2. Forgetting to update, not duplicate, an existing key — set must check for an existing entry in the bucket first, or you'll get duplicate [key, value] pairs for the same key.
3. Never resizing — a fixed-size table degrades to O(n) performance as more entries are added and load factor climbs.
4. Assuming hash tables preserve insertion order — a raw hash table (unlike JS's actual Map) generally does not; Map's insertion-order guarantee is an additional design choice on top of hashing, not an inherent property of hash tables.

📋 Quick Reference

hash(key) -> number -> index = hash % bucketCount
collision  -> chaining (list per bucket) or open addressing (probe next slot)
load factor = entries / buckets   -> resize when too high
average case O(1), worst case O(n)

🎤 Interview Q&A

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

Source: js_hashing_and_hash_tables_theory_1.md, js_hashing_and_hash_tables_theory_2.md · generated by tools/build_lessons.py