Hvordan optimaliserer hash maps algoritmer?

Question

Accepted Answer

Et **hash map** (ordbok) gir **O(1) gjennomsnittlige** oppslag, innsettinger og slettinger. Ved å handle O(n) minne for hastighet omgjøres mange O(n²) algoritmer til O(n) ved å erstatte gjentatte skanninger med øyeblikkelige oppslag.

## Ideen

Istedenfor å søke i en liste hver gang, lagrer du verdier du har sett i et hash map og sjekker medlemskap på 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)
```

Uten kartet er dette O(n²); med det, ett pass.

## Vanlig bruk

- **Deduplicering / medlemskap** med et sett.
- **Tellingsfrekvenser** (`Counter`).
- **Gruppering / indeksering** etter nøkkel.
- **Caching / memoization** av resultater.

## Kompleksitet

- **Gjennomsnitt:** O(1) per operasjon. **Verst:** O(n) ved mange kollisjoner. **Plass:** O(n).

## Fallgruver

Nøkler må være **hashable** og uforanderlige. Verste-tilfelle kollisjoner forverrer ytelsen. Hash maps er uordnede (bruk ordnede varianter hvis rekkefølge betyr noe).

## Hvorfor det betyr noe

Hashing er den eneste mest vanlige optimaliseringen i kodingsintervjuer og ekte systemer — det gjør "søk igjen og igjen" til "slå det opp én gang".

Rommet-for-tid-avveiingen er en tilbakevendende teknisk innflytelsesarm.

Frekvenstelling, caching og indeksering hviler alle på denne ene ideen.