All Roadmaps›🧠 Data Structures & Algorithms›Phase 2›Hash Tables & Hash Maps — Internal Working

Hash Tables & Hash Maps — Internal Working

0/14 in this phase0/57 across the roadmap

📖 Concept

A hash table (hash map) is the most important data structure for coding interviews. It provides O(1) average lookup, insert, and delete by mapping keys to array indices using a hash function.

How it works internally:

  1. Hash function: Converts key → integer index (e.g., "alice" → 42)
  2. Array of buckets: The index maps to a position in an array
  3. Collision handling: When two keys hash to the same index

Collision resolution strategies:

  1. Chaining (most common): Each bucket holds a linked list. Collisions add to the list.
  2. Open addressing: Find the next empty slot (linear probing, quadratic probing, double hashing)

Load factor = number of elements / number of buckets

  • When load factor exceeds threshold (~0.75), the table resizes (double buckets, rehash all)
  • This keeps chains short → O(1) average

Complexity:

Operation Average Worst Case
Insert O(1) O(n) (all keys collide)
Lookup O(1) O(n)
Delete O(1) O(n)

JavaScript's Map vs Object:

  • Map: Any key type, preserves insertion order, has .size, iterable
  • Object: String/Symbol keys only, prototype chain, not iterable by default
  • For DSA: always prefer Map or Set

🏠 Real-world analogy: A library catalog. The hash function is like organizing books by the first letter of the author's last name (A → shelf 1, B → shelf 2). If two books start with "S" (collision), they share a shelf (chaining).

💻 Code Example

codeTap to expand ⛶
1// BUILD HASH TABLE FROM SCRATCH
2class HashTable {
3  constructor(size = 53) {
4    this.buckets = new Array(size);
5    this.size = size;
6    this.count = 0;
7  }
8

9  // Simple hash function
10  _hash(key) {
11    let hash = 0;
12    const PRIME = 31; // Prime reduces collisions
13    for (let i = 0; i < Math.min(key.length, 100); i++) {
14      hash = (hash * PRIME + key.charCodeAt(i)) % this.size;
15    }
16    return hash;
17  }
18

19  set(key, value) {
20    const idx = this._hash(key);
21    if (!this.buckets[idx]) this.buckets[idx] = [];
22    // Check if key exists (update)
23    for (const pair of this.buckets[idx]) {
24      if (pair[0] === key) { pair[1] = value; return; }
25    }
26    this.buckets[idx].push([key, value]);
27    this.count++;
28  }
29

30  get(key) {
31    const idx = this._hash(key);
32    if (!this.buckets[idx]) return undefined;
33    for (const pair of this.buckets[idx]) {
34      if (pair[0] === key) return pair[1];
35    }
36    return undefined;
37  }
38

39  delete(key) {
40    const idx = this._hash(key);
41    if (!this.buckets[idx]) return false;
42    const bucket = this.buckets[idx];
43    for (let i = 0; i < bucket.length; i++) {
44      if (bucket[i][0] === key) {
45        bucket.splice(i, 1);
46        this.count--;
47        return true;
48      }
49    }
50    return false;
51  }
52}
53

54// COMMON INTERVIEW PATTERNS WITH HASH MAPS
55

56// Two Sum — O(n) with hash map
57function twoSum(nums: number[], target: number): [number, number] {
58  const map = new Map<number, number>();
59  for (let i = 0; i < nums.length; i++) {
60    const complement = target - nums[i];
61    if (map.has(complement)) return [map.get(complement)!, i];
62    map.set(nums[i], i);
63  }
64  throw new Error("No solution");
65}
66

67// Group Anagrams — O(n * k log k)
68function groupAnagrams(strs: string[]): string[][] {
69  const map = new Map<string, string[]>();
70  for (const s of strs) {
71    const key = s.split('').sort().join('');
72    if (!map.has(key)) map.set(key, []);
73    map.get(key)!.push(s);
74  }
75  return Array.from(map.values());
76}
77

78// Frequency Counter — Universal pattern
79function topKFrequent(nums: number[], k: number): number[] {
80  const freq = new Map<number, number>();
81  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
82  return [...freq.entries()]
83    .sort((a, b) => b[1] - a[1])
84    .slice(0, k)
85    .map(e => e[0]);
86}
87

88// Subarray Sum Equals K — Prefix sum + hash map
89function subarraySum(nums: number[], k: number): number {
90  const prefixCount = new Map<number, number>([[0, 1]]);
91  let sum = 0, count = 0;
92  for (const num of nums) {
93    sum += num;
94    if (prefixCount.has(sum - k)) count += prefixCount.get(sum - k)!;
95    prefixCount.set(sum, (prefixCount.get(sum) || 0) + 1);
96  }
97  return count;
98}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

  1. Build a hash table from scratch with set, get, delete
  2. Two Sum — find indices of two numbers that add to target
  3. Check if two strings are anagrams using a hash map
  4. Find the first non-repeating character in a string
  5. Group anagrams from an array of strings
  6. Find the longest consecutive sequence in an unsorted array
  7. Count subarrays with sum equal to k (prefix sum + hash map)
  8. Top K frequent elements
  9. Design a consistent hashing ring (conceptual)
  10. Implement an LRU Cache using hash map + doubly linked list

⚠️ Common Mistakes

  • Using Object as a hash map — use Map for non-string keys, better performance, and .size property

  • Not understanding that hash map O(1) is AVERAGE, not guaranteed — worst case with bad hash is O(n)

  • Forgetting that Map preserves insertion order in JavaScript — this is guaranteed by the spec

  • Using JSON.stringify as a hash key — it's slow and order-dependent for objects

  • Not considering hash collisions in custom implementations — always handle them

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Hash Tables & Hash Maps — Internal Working

← PreviousQueues, Deques & Circular QueuesNext →Sets & Maps — Built-in & Custom