Skip to main content

🗂️ 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​

OperationAverageWorst
InsertO(1)O(n)
LookupO(1)O(n)
DeleteO(1)O(n)
SpaceO(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​

ProblemDifficultySolution

| LC 1 — Two Sum | Easy | View Solution | | LC 217 — Contains Duplicate | Easy | View Solution | | LC 242 — Valid Anagram | Easy | View Solution | | LC 929 — Unique Email Addresses | Easy | View Solution | | LC 575 — Distribute Candies | Easy | View Solution | | LC 349 — Intersection of Two Arrays | Easy | View Solution | | LC 219 — Contains Duplicate II | Easy | View Solution | | LC 383 — Ransom Note | Easy | | | LC 387 — First Unique Character in a String | Easy | | | LC 389 — Find the Difference | Easy | | | LC 448 — Find All Numbers Disappeared in an Array | Easy | | | LC 771 — Jewels and Stones | Easy | | | LC 1002 — Find Common Characters | Easy | | | LC 1207 — Unique Number of Occurrences | Easy | | | CC — Frequency of Characters (FREQ) | Easy | | | CC — Count Distinct Elements (DISTELEM) | Easy | | | LC 49 — Group Anagrams | Medium | View Solution | | LC 347 — Top K Frequent Elements | Medium | View Solution | | LC 128 — Longest Consecutive Sequence | Medium | View Solution | | LC 167 — Two Sum II | Medium | View Solution | | LC 3 — Longest Substring Without Repeating Characters | Medium | | | LC 36 — Valid Sudoku | Medium | | | LC 187 — Repeated DNA Sequences | Medium | | | LC 454 — 4Sum II | Medium | | | LC 560 — Subarray Sum Equals K | Medium | | | LC 692 — Top K Frequent Words | Medium | | | LC 974 — Subarray Sums Divisible by K | Medium | | | LC 1010 — Pairs of Songs With Total Durations Divisible by 60 | Medium | | | CC — Subarray with Given Sum (SUBSUM) | Medium | | | CC — Hash Table Operations (HASHTBL) | Medium | | | LC 30 — Substring with Concatenation of All Words | Hard | | | LC 41 — First Missing Positive | Hard | | | LC 149 — Max Points on a Line | Hard | | | LC 269 — Alien Dictionary | Hard | | | LC 336 — Palindrome Pairs | Hard | | | CC — Advanced Hashing (ADVHASH) | Hard | |

Last updated on