Wat is een hash table en hoe bereikt het O(1) lookup?

Question

Accepted Answer

Een **hash table** (hash map) slaat **key → value** paren op en biedt gemiddeld **O(1)** insert, lookup en delete. Het werkt door elke sleutel door een **hash function** te halen die deze toewijst aan een index in een onderliggende array (een "bucket").

## Hoe het werkt

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

## Voorbeeld

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

## Complexiteit

| Bewerking | Gemiddeld | Worst case |
|---|---|---|
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |

Het **worst case** O(n) gebeurt wanneer veel sleutels botsen in dezelfde bucket.

## Afwegingen

- **Sterke punten:** extreem snelle op sleutel gebaseerde toegang; flexibele sleutels.
- **Zwakke punten:** geen ordenering van sleutels; extra geheugen; O(n) worst case; heeft een goede hash function nodig.

## Waarom het belangrijk is

Hash tables zijn waarschijnlijk de meest gebruikte structuur in de praktijk — achter woordenboeken, sets, caches, database-indexen en deduplicatie.

Een lineaire scan vervangen door een hash lookup is een van de meest voorkomende manieren om een O(n²) algoritme in O(n) om te zetten.