Hvordan optimerer hash maps algoritmer?

Question

Accepted Answer

En **hash map** (ordbog) giver **O(1) gennemsnitlig** opslag, indsættelse og sletning. Ved at erstatte gentagne søgninger med øjeblikkelig opslag konverteres mange O(n²) algoritmer til O(n) for O(n) hukommelse.

## Idéen

I stedet for at søge i en liste hver gang gemmer du sete værdier i en hash map og kontrollerer medlemskab i konstant tid.

## Eksempel: two-sum i O(n)

```python
def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:               # O(1) lookup
            return (seen[need], i)
        seen[x] = i
    return None

two_sum([2, 7, 11, 15], 9)             # -> (0, 1)
```

Uden kortet er dette O(n²); med det kun ét pass.

## Almindelige anvendelser

- **Deduplikering / medlemskab** med et sæt.
- **Tælling af frekvenser** (`Counter`).
- **Gruppering / indeksering** efter nøgle.
- **Cachelagring / memoization** af resultater.

## Kompleksitet

- **Gennemsnitlig:** O(1) pr. operation. **Værste:** O(n) ved tunge kollisioner. **Plads:** O(n).

## Faldgruber

Nøgler skal være **hashable** og uforanderlige. Værste tilfælde kollisioner forværrer ydeevne. Hash maps er uordnede (brug ordnede varianter hvis rækkefølge betyder noget).

## Hvorfor det betyder noget

Hashing er den absolut mest almindelige optimering i kodningsinterviews og rigtige systemer — det konverterer "søg igen og igen" til "kig det op engang".

Rumaustausch for hastighed er en tilbagevendende ingeniørvirk.

Tælling af frekvenser, cachelagring og indeksering hviler alle på denne ene ide.