Hoe optimaliseren hash maps algoritmen?

Question

Accepted Answer

Een **hash map** (woordenboek) geeft **O(1) gemiddelde** opzoekingen, invoegingen en verwijderingen. Door O(n) geheugen voor snelheid in te ruilen, worden veel O(n²) algoritmen in O(n) omgezet door herhaalde scans te vervangen door directe opzoekingen.

## Het idee

In plaats van elke keer een lijst te doorzoeken, sla je geziene waarden op in een hash map en controleer je lidmaatschap in constante tijd.

## Voorbeeld: two-sum in 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)
```

Zonder de map is dit O(n²); ermee één keer langs.

## Veelvoorkomende toepassingen

- **Deduplicatie / lidmaatschap** met een set.
- **Frequenties tellen** (`Counter`).
- **Groeperen / indexeren** op sleutel.
- **Caching / memoization** van resultaten.

## Complexiteit

- **Gemiddeld:** O(1) per bewerking. **Slechtste:** O(n) bij veel botsingen. **Ruimte:** O(n).

## Valkuilen

Sleutels moeten **hashable** en onveranderbaar zijn. Slechte-geval botsingen verslechteren prestaties. Hash maps zijn ongeordend (gebruik geordende varianten als volgorde belangrijk is).

## Waarom het belangrijk is

Hashing is de meest voorkomende optimalisatie in codeerinterviews en echte systemen — het zet "telkens opnieuw zoeken" om in "één keer opzoeken".

De ruimte-voor-snelheid afweging is een terugkerende technische hefboom.

Frequentietelling, caching en indexering rusten allemaal op dit ene idee.