Skip to content

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.

View glossary

Build real projects

Apply what you learned by building guided projects with starter code and solutions.

View projects

Decode error messages

Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.

View errors