Hash Tables

Think of it like this

Imagine a library with a perfect librarian. You give them any book title; they instantly tell you exactly which shelf and slot it's in — without searching. They do this using a formula (the hash function) that converts the title to a shelf number.

"The Great Gatsby"  →  hash()  →  shelf 7, slot 3
"1984"              →  hash()  →  shelf 2, slot 0
"Dune"              →  hash()  →  shelf 9, slot 5

That "librarian formula" is a hash function. The shelves are an array of buckets. This is a hash table.

How It Works

Step 1: You call map.set("name", "Alice")
 
Step 2: Hash function converts "name" to an integer
        hash("name") → 104  (some deterministic integer)
 
Step 3: Map that to a bucket index
        104 % 11 = 5         (11 = number of buckets)
 
Step 4: Store "Alice" in bucket[5]
 
Step 5: map.get("name")
        → hash("name") = 104 → 104 % 11 = 5 → return bucket[5] → "Alice"
 
        Direct lookup! O(1) average.

Buckets (size 11):
 [0]  →  null
 [1]  →  null
 [2]  →  null
 [3]  →  { key:"city", val:"NYC" }
 [4]  →  null
 [5]  →  { key:"name", val:"Alice" }
 [6]  →  null
 [7]  →  { key:"age",  val:30 }
 [8]  →  null
 [9]  →  null
[10]  →  null

What Makes a Good Hash Function?

Property	What it means	Why it matters
Deterministic	Same key → always same hash	You must be able to find what you stored
Uniform distribution	Keys spread evenly across buckets	Minimizes collisions
Fast to compute	O(1) to hash	Don't waste the lookup speedup
Avalanche effect	Small input change → completely different hash	Security, prevents clustering

Collisions — When Two Keys Hash to the Same Bucket

No hash function is perfect. Collisions happen. Two strategies to handle them:

Strategy 1 — Chaining: Each bucket holds a linked list of all entries that hash to it.

hash("name") % 7 = 3
hash("game") % 7 = 3  ← collision!
 
Bucket[3]: → { key:"name", val:"Alice" } → { key:"game", val:"Chess" } → null

class HashMap {
  constructor(capacity = 16) {
    this.buckets = new Array(capacity).fill(null).map(() => []);
    this.capacity = capacity;
    this.size = 0;
  }
 
  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash * 31 + key.charCodeAt(i)) % this.capacity;
    }
    return hash;
  }
 
  set(key, val) {
    const idx = this._hash(key);
    const bucket = this.buckets[idx];
    const entry = bucket.find(e => e[0] === key);
    if (entry) { entry[1] = val; return; } // update existing
    bucket.push([key, val]);
    this.size++;
    if (this.size / this.capacity > 0.75) this._resize(); // load factor check
  }
 
  get(key) {
    const idx = this._hash(key);
    const entry = this.buckets[idx].find(e => e[0] === key);
    return entry ? entry[1] : undefined;
  }
 
  delete(key) {
    const idx = this._hash(key);
    const bucket = this.buckets[idx];
    const i = bucket.findIndex(e => e[0] === key);
    if (i === -1) return false;
    bucket.splice(i, 1);
    this.size--;
    return true;
  }
 
  _resize() {
    const old = this.buckets;
    this.capacity *= 2;
    this.buckets = new Array(this.capacity).fill(null).map(() => []);
    this.size = 0;
    for (const bucket of old)
      for (const [k, v] of bucket) this.set(k, v);
  }
}

Strategy 2 — Open Addressing (Linear Probing): If bucket i is taken, try i+1, i+2, ... until you find an empty slot.

hash("name") → slot 5 (taken by "age") → probe slot 6 (empty) ✓
 
Set: probe until empty slot, place there.
Get: probe until you find the key OR an empty slot (= key not present).

Load Factor — The Critical Metric

load factor (α) = number of stored keys / number of buckets
 
Low α (< 0.5):  Lots of empty buckets → fast lookups, wasted memory
High α (> 0.75): Many collisions → lookups degrade toward O(n)
 
Rehash threshold:
  Chaining:        rehash when α > 0.75
  Open addressing: rehash when α > 0.5  (collisions compound faster)
 
Rehashing: double bucket count, re-insert all keys → O(n) amortized

Time Complexity

Operation	Average	Worst (high α / bad hash)
Insert	O(1)	O(n)
Lookup	O(1)	O(n)
Delete	O(1)	O(n)
Iterate all keys	O(n)	O(n)

Space Complexity: O(n) for keys + values

Collision Resolution Comparison

Method	Pros	Cons
Chaining	Simple; handles high α gracefully	Extra pointer memory; poor cache locality
Linear probing	Cache-friendly; no extra allocation	Clustering; must handle tombstones on delete
Quadratic probing	Reduces primary clustering	Can miss empty slots if α > 0.5
Double hashing	Best distribution	Two hash computations

Hash Table (Collision via Chaining)

1 / 2

[0]

[1]

Bob

[2]

↑ hash('Bob') = 2

[3]

[4]

Insert 'Bob'. Hash function maps 'Bob' to index 2.

The Most Important Interview Pattern

Frequency counting — convert O(n²) to O(n) using a hash map to track counts:

// Group Anagrams: ["eat","tea","tan","ate","nat","bat"]
// Sort each word as key → group words with same sorted chars
 
function groupAnagrams(strs) {
  const map = new Map();
  for (const s of strs) {
    const key = [...s].sort().join(''); // sorted chars = canonical anagram key
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(s);
  }
  return [...map.values()];
}
 
// "eat" → "aet", "tea" → "aet", "ate" → "aet"  → all grouped together
// "tan" → "ant", "nat" → "ant"                   → grouped together
// "bat" → "abt"                                   → alone

Real-World Frontend Application

Every JavaScript Object and Map is a hash table under the hood:

// Redux normalized state — O(1) entity lookup
const state = {
  entities: {
    users: {
      byId: {
        'u1': { id: 'u1', name: 'Alice' },
        'u2': { id: 'u2', name: 'Bob'   },
      },
      allIds: ['u1', 'u2']
    }
  }
};
// O(1) lookup: state.entities.users.byId['u1'] ← direct hash table access
 
// Memoization with Map
function memoize(fn) {
  const cache = new Map(); // hash map for cache
  return (...args) => {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key); // O(1) lookup
    const result = fn(...args);
    cache.set(key, result);
    return result;
  };
}

`Map` vs `Object` in JavaScript

Feature	`Object`	`Map`
Key types	Strings and Symbols only	Any value (including objects)
Insertion order	Not guaranteed (pre-ES2015)	Guaranteed
Size	Manual `Object.keys().length`	`.size` property
Iteration	Verbose	`for...of map`
Prototype pollution	`{ toString: ... }` collides	No prototype
Performance for frequent add/delete	Good	Optimized

Use Map when: keys aren't strings, you need iteration order guaranteed, or you're doing many additions/deletions.

Common Mistakes

Mistake	Consequence	Fix
Using object keys that are objects	`{} === {}` is false; key becomes `"[object Object]"`	Use `Map` for non-string keys
Forgetting `has()` check	`get()` returns `undefined` which may be a valid value	Use `map.has(key)` to distinguish "missing" from `undefined`
Assuming iteration order in `Object`	Integer-like keys sort before string keys	Use `Map` when insertion order matters
Not accounting for worst-case	O(1) average can degrade with hash collisions	For adversarial input (crypto), use a cryptographic hash

Key Problems to Solve

#	Problem	Pattern	Difficulty
1	Two Sum	Hash map: value → index	Easy
2	Valid Anagram	Frequency count	Easy
3	Contains Duplicate	Hash set	Easy
4	Group Anagrams	Sorted key as canonical hash key	Medium
5	Longest Consecutive Sequence	Set membership in O(1)	Medium
6	Subarray Sum Equals K	Prefix sum + hash map	Medium
7	LRU Cache	HashMap + doubly linked list	Medium
8	Top K Frequent Elements	Frequency map + heap	Medium
9	Minimum Window Substring	Sliding window + frequency maps	Hard
10	Longest Substring Without Repeating Chars	Sliding window + character index map	Medium

Step 1: You call map.set("name", "Alice") Step 2: Hash function converts "name" to an integer hash("name") → 104 (some deterministic integer) Step 3: Map that to a bucket index 104 % 11 = 5 (11 = number of buckets) Step 4: Store "Alice" in bucket[5] Step 5: map.get("name") → hash("name") = 104 → 104 % 11 = 5 → return bucket[5] → "Alice" Direct lookup! O(1) average.

Buckets (size 11): [0] → null [1] → null [2] → null [3] → { key:"city", val:"NYC" } [4] → null [5] → { key:"name", val:"Alice" } [6] → null [7] → { key:"age", val:30 } [8] → null [9] → null [10] → null

Property

What it means

Why it matters

Deterministic

Same key → always same hash

You must be able to find what you stored

Uniform distribution

Keys spread evenly across buckets

Minimizes collisions

Fast to compute

O(1) to hash

Don't waste the lookup speedup

Avalanche effect

Small input change → completely different hash

Security, prevents clustering

class HashMap { constructor(capacity = 16) { this.buckets = new Array(capacity).fill(null).map(() => []); this.capacity = capacity; this.size = 0; } _hash(key) { let hash = 0; for (let i = 0; i < key.length; i++) { hash = (hash * 31 + key.charCodeAt(i)) % this.capacity; } return hash; } set(key, val) { const idx = this._hash(key); const bucket = this.buckets[idx]; const entry = bucket.find(e => e[0] === key); if (entry) { entry[1] = val; return; } // update existing bucket.push([key, val]); this.size++; if (this.size / this.capacity > 0.75) this._resize(); // load factor check } get(key) { const idx = this._hash(key); const entry = this.buckets[idx].find(e => e[0] === key); return entry ? entry[1] : undefined; } delete(key) { const idx = this._hash(key); const bucket = this.buckets[idx]; const i = bucket.findIndex(e => e[0] === key); if (i === -1) return false; bucket.splice(i, 1); this.size--; return true; } _resize() { const old = this.buckets; this.capacity *= 2; this.buckets = new Array(this.capacity).fill(null).map(() => []); this.size = 0; for (const bucket of old) for (const [k, v] of bucket) this.set(k, v); } }

load factor (α) = number of stored keys / number of buckets Low α (< 0.5): Lots of empty buckets → fast lookups, wasted memory High α (> 0.75): Many collisions → lookups degrade toward O(n) Rehash threshold: Chaining: rehash when α > 0.75 Open addressing: rehash when α > 0.5 (collisions compound faster) Rehashing: double bucket count, re-insert all keys → O(n) amortized

Operation

Average

Worst (high α / bad hash)

Insert

O(1)

O(n)

Lookup

O(1)

O(n)

Delete

O(1)

O(n)

Iterate all keys

O(n)

Method

Pros

Cons

Chaining

Simple; handles high α gracefully

Extra pointer memory; poor cache locality

Linear probing

Cache-friendly; no extra allocation

Clustering; must handle tombstones on delete

Quadratic probing

Reduces primary clustering

Can miss empty slots if α > 0.5

Double hashing

Best distribution

Two hash computations

// Group Anagrams: ["eat","tea","tan","ate","nat","bat"] // Sort each word as key → group words with same sorted chars function groupAnagrams(strs) { const map = new Map(); for (const s of strs) { const key = [...s].sort().join(''); // sorted chars = canonical anagram key if (!map.has(key)) map.set(key, []); map.get(key).push(s); } return [...map.values()]; } // "eat" → "aet", "tea" → "aet", "ate" → "aet" → all grouped together // "tan" → "ant", "nat" → "ant" → grouped together // "bat" → "abt" → alone

// Redux normalized state — O(1) entity lookup const state = { entities: { users: { byId: { 'u1': { id: 'u1', name: 'Alice' }, 'u2': { id: 'u2', name: 'Bob' }, }, allIds: ['u1', 'u2'] } } }; // O(1) lookup: state.entities.users.byId['u1'] ← direct hash table access // Memoization with Map function memoize(fn) { const cache = new Map(); // hash map for cache return (...args) => { const key = JSON.stringify(args); if (cache.has(key)) return cache.get(key); // O(1) lookup const result = fn(...args); cache.set(key, result); return result; }; }

Feature

Object

Map

Key types

Strings and Symbols only

Any value (including objects)

Insertion order

Not guaranteed (pre-ES2015)

Guaranteed

Size

Manual Object.keys().length

.size property

Iteration

Verbose

for...of map

Prototype pollution

{ toString: ... } collides

No prototype

Performance for frequent add/delete

Good

Optimized

Mistake

Consequence

Fix

Using object keys that are objects

{} === {} is false; key becomes "[object Object]"

Use Map for non-string keys

Forgetting has() check

get() returns undefined which may be a valid value

Use map.has(key) to distinguish "missing" from undefined

Assuming iteration order in Object

Integer-like keys sort before string keys

Use Map when insertion order matters

Not accounting for worst-case

O(1) average can degrade with hash collisions

For adversarial input (crypto), use a cryptographic hash

Problem

Pattern

Difficulty

Two Sum

Hash map: value → index

Easy

Valid Anagram

Frequency count

Easy

Contains Duplicate

Hash set

Easy

Group Anagrams

Sorted key as canonical hash key

Medium

Longest Consecutive Sequence

Set membership in O(1)

Medium

Subarray Sum Equals K

Prefix sum + hash map

Medium

LRU Cache

HashMap + doubly linked list

Medium

Top K Frequent Elements

Frequency map + heap

Medium

Minimum Window Substring

Sliding window + frequency maps

Hard

Longest Substring Without Repeating Chars

Sliding window + character index map

Medium

Hash Tables

Hash Tables#

Think of it like this

How It Works

What Makes a Good Hash Function?

Collisions — When Two Keys Hash to the Same Bucket

Load Factor — The Critical Metric

Time Complexity

Space Complexity: O(n) for keys + values

Collision Resolution Comparison

Hash Table (Collision via Chaining)

The Most Important Interview Pattern

Real-World Frontend Application

Map vs Object in JavaScript

Common Mistakes

Key Problems to Solve

Hash Tables

Hash Tables#

Think of it like this

How It Works

What Makes a Good Hash Function?

Collisions — When Two Keys Hash to the Same Bucket

Load Factor — The Critical Metric

Time Complexity

Space Complexity: O(n) for keys + values

Collision Resolution Comparison

Hash Table (Collision via Chaining)

The Most Important Interview Pattern

Real-World Frontend Application

Map vs Object in JavaScript

Common Mistakes

Key Problems to Solve

Hash Tables

`Map` vs `Object` in JavaScript

Hash Tables

`Map` vs `Object` in JavaScript