Hash Tables Explained: How They Work, Collision Resolution, and Real-World Use Cases

// Hash table: array indexed by hash(key)
class HashMap {
  constructor(size = 16) {
    this.buckets = new Array(size).fill(null).map(() => []);
    this.size = size;
    this.count = 0;
  }

  #hash(key) {
    // Convert key to array index
    let hash = 0;
    for (const char of String(key)) {
      hash = (hash * 31 + char.charCodeAt(0)) % this.size;
    }
    return hash; // O(key length) — treated as O(1) for fixed-length keys
  }

  set(key, value) {
    const idx = this.#hash(key);
    const bucket = this.buckets[idx];
    const existing = bucket.find(([k]) => k === key);
    if (existing) { existing[1] = value; return; }
    bucket.push([key, value]); // Chaining: multiple entries per bucket
    this.count++;
    if (this.count / this.size > 0.75) this.#resize(); // Load factor threshold
  }

  get(key) {
    const bucket = this.buckets[this.#hash(key)];
    return bucket.find(([k]) => k === key)?.[1];
  }

  #resize() {
    const old = this.buckets;
    this.size *= 2;
    this.buckets = new Array(this.size).fill(null).map(() => []);
    this.count = 0;
    old.forEach(bucket => bucket.forEach(([k, v]) => this.set(k, v)));
  }
}

// Chaining: each bucket is a linked list / array
// Multiple keys can map to same index — stored in the list
// Pro: simple, handles high load factors well
// Con: linked list pointer overhead, cache unfriendly
// Used by: Java HashMap, most language default hash tables

// Open addressing: find next empty slot in array
// Linear probing: idx, idx+1, idx+2, ...
// Quadratic probing: idx, idx+1, idx+4, idx+9, ...
// Double hashing: idx, idx+hash2(key), ...
// Pro: cache friendly (all data in one array), no pointer overhead
// Con: clustering (many collisions near same index), needs low load factor
// Used by: Python dict, Java's newer hash tables, Redis

// Load factor = count / capacity
// Chaining: resize at load factor > 0.75 (Python uses 0.6667)
// Open addressing: resize at load factor > 0.5 (more collisions at high load)

// Real performance:
// O(1) average: when load factor is low, hash is good
// O(n) worst case: when everything hashes to same bucket (terrible hash fn)

// Good hash function properties:
// 1. Deterministic: same key always → same hash
// 2. Uniform distribution: spreads keys evenly across buckets
// 3. Fast: O(1) or O(key length)
// 4. Avalanche effect: small key change → completely different hash

// FNV-1a (fast, good distribution):
function fnv1a(key) {
  let hash = 2166136261; // FNV offset basis
  for (const byte of Buffer.from(String(key))) {
    hash ^= byte;
    hash = (hash * 16777619) >>> 0; // FNV prime, keep 32-bit
  }
  return hash;
}

// MurmurHash3: non-cryptographic, excellent distribution, used in Redis
// MD5/SHA256: cryptographic — use only when security matters, slow for hash tables

// Bad hash function (causes clustering):
function badHash(key) { return key.length % capacity; } // Only uses length!
// All 3-letter words → same bucket!