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!