Hash Map

Hash then bucket

A hash function turns a key into an array index. Different keys can collide into the same bucket; a short list (or tree) inside the bucket resolves it. With a good spread, get/put/delete average O(1), worst O(n).

Library by first letter

Shelving books by first letter of the title lets you skip to the right shelf instantly. If too many titles start with 'S', that shelf gets slow — that's a collision.

Two Sum in one pass

Store each number's index as you go; check for the complement before inserting.

def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return [seen[target - n], i]
        seen[n] = i
    return []

Output:

two_sum([2, 7, 11, 15], 9) -> [0, 1]

Quick check: You need fast lookup by key and don't care about order. Reach for...

• Hash map
• Sorted array + binary search
• Linked list
• Stack