Hash Tables & Maps

A Hash Table (or Hash Map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a mathematical function (a Hash Function) to compute an index into an array of buckets or slots, from which the desired value can be found.

Hash tables are incredibly powerful because they offer $O(1)$ average time complexity for insertions, deletions, and lookups!

How it Works

1. Key: You provide a Key (e.g., "apple").
2. Hash Function: The hash function scrambles the key mathematically and outputs a massive integer (the Hash Code). Example: hash("apple") = 5829103.
3. Index Calculation: The hash code is reduced to fit within the bounds of the underlying array using the modulo operator. Example: 5829103 % 10 (array size) = 3.
4. Storage: The Value is stored in the array at index 3.

Hash Collisions

A collision occurs when the Hash Function generates the same exact index for two different keys. Because the underlying array is much smaller than the infinite number of possible string keys, collisions are mathematically inevitable (The Pigeonhole Principle).

If we try to insert "banana" and hash("banana") % 10 = 3, we have a collision at index 3!

Collision Resolution Strategies

1. Separate Chaining: Instead of storing the value directly in the array slot, every array slot contains a Linked List. When a collision occurs, the new key-value pair is simply appended to the linked list at that index. During a lookup, the hash table finds the correct index, then linearly traverses the linked list to find the exact key.

2. Open Addressing (Linear Probing): If index 3 is full, the hash table simply checks index 4. If 4 is full, it checks 5. It linearly probes forward until it finds an empty slot, and stores the value there.

Time Complexity

Why is the worst case $O(N)$? If your Hash Function is terrible and maps every single key to index 0, your Hash Table degrades into a single massive Linked List. Searching through a Linked List is $O(N)$. Modern languages (Java, Python, JS/TS) have highly optimized internal hash functions to ensure $O(1)$ performance.

Using Sets (HashSets)

A Set is just a Hash Table that only stores Keys, without any attached Values. It is used exclusively to guarantee uniqueness and to allow $O(1)$ lookups to check if an item exists.

// Finding duplicates in O(N) time instead of O(N^2)
function hasDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();
  
  for (const num of nums) {
    if (seen.has(num)) {
      return true; // O(1) lookup!
    }
    seen.add(num);
  }
  return false;
}

Resizing (Load Factor)

As you add more items to a Hash Table, the chances of collisions skyrocket. The Load Factor is the ratio of items to array size. When the Load Factor hits a certain threshold (usually 0.75), the Hash Table performs an automatic resize. It creates a new array double the size and re-hashes every single element into the new array. This operation is expensive ($O(N)$), but since it happens rarely, the amortized insertion time remains $O(1)$.