Hva er en hash table og hvordan oppnår den O(1) oppslag?

Question

Accepted Answer

En **hash table** (hash map) lagrer **key → value** par og tilbyr gjennomsnittlig **O(1)** insert, oppslag og sletting. Det fungerer ved å kjøre hver nøkkel gjennom en **hash function** som kartlegger den til en indeks i en underliggende array (en "bucket").

## Hvordan det fungerer

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

## Eksempel

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

## Kompleksitet

| Operasjon | Gjennomsnitt | Verste tilfelle |
|---|---|---|
| insert | O(1) | O(n) |
| oppslag | O(1) | O(n) |
| sletting | O(1) | O(n) |

Det **verste tilfellet** O(n) oppstår når mange nøkler kolliderer inn i samme bucket.

## Avveiinger

- **Styrker:** ekstremt rask nøkkelbasert tilgang; fleksible nøkler.
- **Svakheter:** ingen rekkefølge på nøkler; ekstra minne; O(n) verste tilfelle; trenger en god hash function.

## Hvorfor det betyr noe

Hash tables er trolig den mest brukte strukturen i praksis — bak ordbøker, sett, cacher, databaseindekser og deduplisering.

Å erstatte et lineært søk med et hash-oppslag er en av de vanligste måtene å gjøre en O(n²) algoritme til O(n).