Hash Tables & Hash Maps: O(1) Lookups

Hash functions, collision resolution via chaining & open addressing, and load factor

« Stacks (LIFO) & Queues (FIFO)« Previous Binary Search & The Two-Pointer Pattern »Next »

Hash tables associate unique keys with values, utilizing a hash function to map keys to bucket indices for average O(1) insertion, deletion, and retrieval.

The Mechanics of Hash Tables

Hash Function: Transforms an arbitrary string key (e.g. "alice") into a deterministic integer index.

Collision: When two different keys produce the same hash index. Resolved via Separate Chaining (linked lists in each bucket) or Open Addressing (probing for the next open slot).

Load Factor: Ratio of items / buckets. When the load factor exceeds ~0.75, the table automatically rehashes into a doubled bucket array to prevent performance degradation.

Two Sum Problem with a Hash Map in O(n)

Try It Yourself »

function twoSum(nums, target) {
  const seen = new Map(); // Stores: num -> index

  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);
  }
  return [];
}

console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1] (2 + 7 = 9)

Using a hash map reduces the brute-force O(n²) search to lightning-fast O(n).

Google AdSense Slot (inContentBanner)

Set your Publisher ID in src/config/ads.ts to display live ads.

Test Yourself With Exercise

+15 XP

What is the average-case time complexity of retrieving a value by key from a well-balanced Hash Map?

« Previous: Stacks (LIFO) & Queues (FIFO)Next: Binary Search & The Two-Pointer Pattern »