# Hash Map — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/hash-map

> Key → value in average O(1) via a hash function and buckets.

## 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.

```python
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]
```

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

- [ ] Sorted array + binary search
- [x] Hash map
- [ ] Linked list

*Answer:* Hash map. Hash map is average O(1) per lookup; binary search is O(log n) and needs sorting.