What is a hash table and how does it achieve O(1) lookup?

Question

Accepted Answer

A **hash table** (hash map) stores **key → value** pairs and offers **average O(1)** insert, lookup, and delete. It works by running each key through a **hash function** that maps it to an index in an underlying array (a "bucket").

## How it works

```text
key "cat" --hash()--> 3   buckets:
key "dog" --hash()--> 0     [0] -> ("dog", 5)
                            [1]
                            [2]
                            [3] -> ("cat", 9)
```

## Example

```python
phone = {}
phone['alice'] = 555_1234   # insert -> hash 'alice' to a bucket
num = phone['alice']        # lookup -> hash again, jump to bucket
del phone['alice']          # delete
'bob' in phone              # membership -> O(1) average
```

## Complexity

| Operation | Average | Worst |
|---|---|---|
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |

The **worst case** O(n) happens when many keys collide into the same bucket.

## Trade-offs

- **Strengths:** extremely fast key-based access; flexible keys.
- **Weaknesses:** no ordering of keys; extra memory; O(n) worst case; needs a good hash function.

## Why it matters

Hash tables are arguably the most-used structure in practice — behind dictionaries, sets, caches, database indexes, and deduplication.

Replacing a linear scan with a hash lookup is one of the most common ways to turn an O(n²) algorithm into O(n).