Hash Tables Deep Dive
Understand hash functions, collision resolution, load factor, and rehashing strategies.
What you'll learn
- Hash function properties: uniform distribution, speed
- Collision resolution: chaining vs open addressing
- Load factor and when to rehash
- Cryptographic vs non-cryptographic hashes
Concept
Hash Tables Deep Dive
A hash table maps keys to values using a hash function, giving O(1) average lookup, insert, and delete. It is the workhorse of modern programming - JavaScript objects, Python dicts, Java HashMaps are all hash tables under the hood.
Hash Functions
A good hash function has two properties: uniform distribution (keys spread evenly across buckets) and speed (fast to compute). For strings, a common approach is the polynomial rolling hash: hash(s) = (s[0]*p^0 + s[1]*p^1 + ...) mod m.
Collision Resolution
When two keys hash to the same bucket, you have a collision. Chaining: each bucket holds a linked list of entries. Simple, handles high load factors, but cache-unfriendly. Open addressing: on collision, probe the next bucket (linear probing, quadratic probing, or double hashing). Cache-friendly but sensitive to clustering.
Load Factor
The load factor alpha = n/m (entries / buckets). As alpha grows, collisions increase. Most implementations rehash (double the bucket count and reinsert all entries) when alpha exceeds a threshold (typically 0.75). Rehashing is O(n) but happens rarely, so amortized cost is O(1).
Cryptographic vs Non-Cryptographic
Non-cryptographic hashes (FNV, MurmurHash, xxHash) are fast but not collision-resistant. Cryptographic hashes (SHA-256) resist this but are slower. Use non-crypto for hash tables; crypto for integrity and security.
Example
class HashTable {
constructor(size = 16) { this.size = size; this.buckets = Array.from({length: size}, () => []); this.count = 0; }
_hash(key) { let h = 0; const s = String(key); for (let i = 0; i < s.length; i++) h = (h * 31 + s.charCodeAt(i)) >>> 0; return h % this.size; }
set(key, value) {
const idx = this._hash(key); const bucket = this.buckets[idx];
for (const e of bucket) { if (e[0] === key) { e[1] = value; return; } }
bucket.push([key, value]); this.count++;
if (this.count / this.size > 0.75) this._rehash();
}
get(key) { const idx = this._hash(key); for (const e of this.buckets[idx]) { if (e[0] === key) return e[1]; } return undefined; }
_rehash() { const old = this.buckets; this.size *= 2; this.buckets = Array.from({length: this.size}, () => []); this.count = 0; for (const b of old) for (const [k, v] of b) this.set(k, v); }
}
const ht = new HashTable();
ht.set('name', 'Ada'); ht.set('age', 36); ht.set('role', 'admin');
console.log(ht.get('name'), ht.get('age'), ht.get('role'));
The hash function uses polynomial rolling with base 31. Chaining stores collisions in bucket arrays. When load factor exceeds 0.75, _rehash doubles the bucket count.
Try it
- Hash Generator
See how hash functions distribute input - the foundation of hash table performance.
Common mistakes
The mistake
Using a non-uniform hash function, causing all keys to cluster in one bucket.
The fix
A bad hash function destroys O(1) performance. Test distribution: hash many keys and check that bucket occupancy is roughly uniform.
The mistake
Not rehashing when load factor grows.
The fix
Without rehashing, collision chains grow long and performance degrades to O(n). Set a load factor threshold and resize when exceeded.
Look up unfamiliar terms
A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.
Build real projects
Apply what you learned by building guided projects with starter code and solutions.
Decode error messages
Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.