Hvordan håndterer hash-tabeller kollisioner, belastningsfaktor og ændring af størrelse?

Question

Accepted Answer

To forskellige nøgler kan hash til den **samme bucket** — en **kollision**. Hash-tabeller forbliver O(1) i gennemsnit ved at løse kollisioner og **ændre størrelse** før buckets bliver fyldte, kontrolleret af **belastningsfaktoren**.

## Løsning af kollisioner

```text
Separate chaining: each bucket holds a list
  [3] -> ("cat",9) -> ("rat",2)   # both hashed to 3

Open addressing: probe to the next free slot
  hash=3 taken -> try 4 -> try 5 ... (linear probing)
```

## Belastningsfaktor og ændring af størrelse

```text
load factor α = number_of_entries / number_of_buckets
α rises -> more collisions -> slower lookups
When α exceeds a threshold (e.g. 0.75):
  -> allocate a bigger array (usually 2x)
  -> REHASH every existing key into new buckets
```

```python
# Conceptual resize
def _resize(self):
    old = self.buckets
    self.buckets = [None] * (len(old) * 2)
    for entry in all_entries(old):
        self._insert(entry.key, entry.value)   # rehash into new array
```

## Kompleksitet

| Handling | Gennemsnit | Værste |
|---|---|---|
| opslag / indsættelse / sletning | O(1) | O(n) |
| enkelt størrelseændring | — | O(n) |
| indsættelse (amortiseret, med størrelseændring) | O(1) | — |

En størrelseændring er O(n), men finder sted sjældent, så den **amortiseres til O(1)** pr. indsættelse.

## Afvejninger

- **Kædning:** enkel, forringes graciøst, men bruger ekstra pegepinde og har dårlig cache-lokalitet.
- **Åben adressering:** cache-venlig og kompakt, men følsom over for høj belastningsfaktor og kræver omhyggelig sletning (gravsten).

## Hvorfor det betyder noget

Disse interne detaljer forklarer *hvorfor* hash-kort er hurtige i gennemsnit, men kan stige til O(n) — afgørende for ydelses-sensitiv kode og forsvar mod modstanderdrevne input (hash-flooding).

Forståelse af belastningsfaktor forklarer også hukommelses-/hastigheds-tuning-knapper eksponeret af rigtige biblioteker.

Handling	Gennemsnit	Værste
opslag / indsættelse / sletning	O(1)	O(n)
enkelt størrelseændring	—	O(n)
indsættelse (amortiseret, med størrelseændring)	O(1)	—