How do hash maps optimize algorithms?

Question

Accepted Answer

A **hash map** (dictionary) gives **O(1) average** lookups, inserts, and deletes. Trading O(n) memory for speed turns many O(n²) algorithms into O(n) by replacing repeated scans with instant lookups.

## The idea

Instead of searching a list each time, store seen values in a hash map and check membership in constant time.

## Example: two-sum in O(n)

```python
def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:               # O(1) lookup
            return (seen[need], i)
        seen[x] = i
    return None

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

Without the map this is O(n²); with it, one pass.

## Common uses

- **Deduplication / membership** with a set.
- **Counting frequencies** (`Counter`).
- **Grouping / indexing** by key.
- **Caching / memoization** of results.

## Complexity

- **Average:** O(1) per operation. **Worst:** O(n) on heavy collisions. **Space:** O(n).

## Pitfalls

Keys must be **hashable** and immutable. Worst-case collisions degrade performance. Hash maps are unordered (use ordered variants if order matters).

## Why it matters

Hashing is the single most common optimization in coding interviews and real systems — it converts "search again and again" into "look it up once."

The space-for-time trade-off is a recurring engineering lever.

Frequency counting, caching, and indexing all rest on this one idea.