🗂️ Hashing (Map / Set)

One-line summary: Use a hash table to achieve O(1) average-time lookup, insertion, and deletion — turning O(n²) brute-force into O(n).

What is Hashing?

Key Hash Table Components

Hash Function: Converts keys into array indices

JavaScript Hash Structures

Map (new Map()) — Key-value pairs; preserves insertion order; any type as key
Set (new Set()) — Unique values only; no duplicates allowed
Object ({}) — String/Symbol keys; prototype chain considerations
WeakMap/WeakSet — Garbage collection friendly; object keys only

Performance Characteristics

Average case: O(1) insert, lookup, delete
Worst case: O(n) due to hash collisions (rare with good hash function)
Space complexity: O(n) where n is number of elements

When to Use Hashing?

✅ Perfect for:

Fast lookups (checking if element exists)
Counting frequencies (character/word counting)
Removing duplicates (using Set)
Caching/Memoization (storing computed results)
Database indexing (quick record retrieval)
Two-sum type problems (complement lookup)

❌ Not suitable for:

Ordered data (use TreeMap/sorted structures)
Range queries (use segment trees/arrays)
Memory-constrained environments (overhead of hash table)
Small datasets (array iteration might be faster)

📊 Visual Learning

Hash Table Structure

Hash Table Visualization Understanding how hash functions map keys to array indices and handle collisions

Hash Function Flow Step-by-step visualization of key hashing, collision detection, and resolution strategies

Array vs Hash Table Comparing array-based storage vs hash table organization for efficient data access

Time & Space Complexity

Operation	Average	Worst
Insert	O(1)	O(n)
Lookup	O(1)	O(n)
Delete	O(1)	O(n)
Space	O(n)	O(n)

Common Patterns

Pattern 1 — Frequency Count

const freq = new Map();
for (const ch of s) freq.set(ch, (freq.get(ch) || 0) + 1);

Pattern 2 — Complement Lookup (Two Sum)

const seen = new Map();
for (let i = 0; i < nums.length; i++) {
  const comp = target - nums[i];
  if (seen.has(comp)) return [seen.get(comp), i];
  seen.set(nums[i], i);
}

Pattern 3 — Canonical Key (Group Anagrams)

const groups = new Map();
for (const w of words) {
  const key = w.split('').sort().join('');
  if (!groups.has(key)) groups.set(key, []);
  groups.get(key).push(w);
}

Pattern 4 — Set Membership (Contains Duplicate)

const seen = new Set();
for (const n of nums) {
  if (seen.has(n)) return true;
  seen.add(n);
}
return false;

Pitfalls

Using object {} as map — breaks with keys like "__proto__" — prefer new Map()
Comparing object keys by reference, not value
Forgetting that Map.size ≠ Object.keys(obj).length

Practice Problems

Problem	Difficulty	Solution

Prefix Sum — hash maps power "subarray sum = K"
Sliding Window — freq maps track window contents
Two Pointers

What is Hashing?​

Key Hash Table Components​

JavaScript Hash Structures​

Performance Characteristics​

When to Use Hashing?​

📊 Visual Learning​

Hash Table Structure​

Time & Space Complexity​

Common Patterns​

Pattern 1 — Frequency Count​

Pattern 2 — Complement Lookup (Two Sum)​

Pattern 3 — Canonical Key (Group Anagrams)​

Pattern 4 — Set Membership (Contains Duplicate)​

Pitfalls​

Practice Problems​

Related Topics​