Hash Maps Explained

Hash maps (hash tables, dictionaries, objects) are the most versatile data structure in coding interviews. They provide O(1) average-case lookup, insertion, and deletion. If you reach for a hash map in 30-40% of your solutions, you are on the right track.

graph TD
    Key["key"]
    Hash["hash(key) % capacity"]
    Index["bucket[index]"]
    Check{"key exists?"}
    Return["return value"]
    Miss["return undefined"]

    Key --> Hash --> Index --> Check
    Check -->|"Yes"| Return
    Check -->|"No"| Miss

    style Key fill:#D97A2B,stroke:#B86418,color:#fff
    style Hash fill:#FAF6EE,stroke:#E8DFC8
    style Check fill:#D97A2B,stroke:#B86418,color:#fff
    style Return fill:#D4EDDA,stroke:#28A745
    style Miss fill:#F8D7DA,stroke:#DC3545
    style Index fill:#FAF6EE,stroke:#E8DFC8

How Hash Maps Work

A hash map uses a hash function to convert a key into an array index. The hash function maps the key to a number in the range [0, capacity-1]. The value is stored at that index.

// Simplified hash map
class HashMap {
  private buckets: Array<[string, any][]> = Array(16).fill(null).map(() => []);

  set(key: string, value: any) {
    const index = this.hash(key) % this.buckets.length;
    const bucket = this.buckets[index];
    const existing = bucket.find(([k]) => k === key);
    if (existing) existing[1] = value;
    else bucket.push([key, value]);
  }

  get(key: string): any {
    const index = this.hash(key) % this.buckets.length;
    const bucket = this.buckets[index];
    const pair = bucket.find(([k]) => k === key);
    return pair ? pair[1] : undefined;
  }

  private hash(key: string): number {
    let hash = 0;
    for (const char of key) hash = (hash * 31 + char.charCodeAt(0)) % 2147483647;
    return Math.abs(hash);
  }
}

Collision Handling

When two keys hash to the same index, a collision occurs. Two main strategies:

• Chaining: Each bucket stores a linked list (or balanced tree). Collisions are resolved by traversing the list. This is what most implementations use.
• Open addressing: If a slot is taken, probe the next slot (linear probing), or use a quadratic sequence. Used in some high-performance implementations.

Time Complexity

Worst case O(n) occurs when all keys hash to the same bucket (poor hash function). With a good hash function and load factor below 0.75, average case is effectively O(1).

Common Patterns

Frequency Counting

// Count character frequencies
function charFrequency(s: string): Map<string, number> {
  const freq = new Map<string, number>();
  for (const ch of s) {
    freq.set(ch, (freq.get(ch) || 0) + 1);
  }
  return freq;
}

Two Sum Pattern

// Find pair that sums to target
function twoSum(nums: number[], target: number): [number, number] {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) return [seen.get(complement)!, i];
    seen.set(nums[i], i);
  }
  throw new Error("No pair found");
}

Grouping

// Group anagrams together
function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  for (const s of strs) {
    const key = s.split('').sort().join('');
    if (!map.has(key)) map.set(key, []);
    map.get(key)!.push(s);
  }
  return Array.from(map.values());
}

Common Mistakes

• Using hash map when order matters : hash maps don't preserve insertion order (use arrays or ordered maps).
• Ignoring space complexity : a hash map with n entries uses O(n) space. If the input is sorted, consider two pointers instead.
• Using the wrong key type : objects in JS can only use string keys. Use Map for non-string keys.
• Not handling null/undefined : check if get() returns undefined before using the value.
• Overcomplicating : if a brute force nested loop solution exists, try a hash map first before reaching for complex algorithms.