Hvad er en hashtabel, og hvordan opnår den O(1) opslag?

Question

Accepted Answer

En **hashtabel** (hash map) gemmer **key → value** par og tilbyder gennemsnitligt **O(1)** indsættelse, opslag og sletning. Det fungerer ved at køre hver nøgle gennem en **hashfunktion**, som kortlægger den til et indeks i et 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

| Handling | Gennemsnit | Værste tilfælde |
|---|---|---|
| indsættelse | O(1) | O(n) |
| opslag | O(1) | O(n) |
| sletning | O(1) | O(n) |

**Værste tilfælde** O(n) sker, når mange nøgler kolliderer i samme bucket.

## Afvejninger

- **Styrker:** ekstremt hurtigt nøglebaseret adgang; fleksible nøgler.
- **Svagheder:** ingen sortering af nøgler; ekstra hukommelse; O(n) i værste tilfælde; kræver en god hashfunktion.

## Hvorfor det betyder noget

Hashtabeller er uden tvivl den mest brugte struktur i praksis — bag ordbøger, sæt, cache, databaseindekser og deduplicering.

At erstatte en lineær scanning med et hashopslag er en af de mest almindelige måder at gøre en O(n²) algoritme til O(n).