Wie optimieren Hash Maps Algorithmen?

Question

Accepted Answer

Eine **Hash Map** (Wörterbuch) bietet **O(1) durchschnittlich** für Lookup, Einfügen und Löschen. Durch das Ersetzen wiederholter Durchsuchungen mit sofortigen Lookups werden viele O(n²) Algorithmen in O(n) umgewandelt, auf Kosten von O(n) Speicher.

## Die Idee

Anstatt jedes Mal eine Liste zu durchsuchen, speichern Sie gesehene Werte in einer Hash Map und überprüfen die Zugehörigkeit in konstanter Zeit.

## Beispiel: 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)
```

Ohne die Map ist dies O(n²); damit nur ein Pass.

## Häufige Anwendungen

- **Deduplizierung / Zugehörigkeit** mit einem Set.
- **Häufigkeitszählung** (`Counter`).
- **Gruppierung / Indexierung** nach Schlüssel.
- **Caching / Memoization** von Ergebnissen.

## Komplexität

- **Durchschnitt:** O(1) pro Operation. **Schlimmster Fall:** O(n) bei schweren Kollisionen. **Speicher:** O(n).

## Fallstricke

Schlüssel müssen **hashbar** und unveränderlich sein. Schlimmste-Fall-Kollisionen verschlechtern die Leistung. Hash Maps sind ungeordnet (verwenden Sie sortierte Varianten, wenn die Reihenfolge wichtig ist).

## Warum es wichtig ist

Hashing ist die mit Abstand häufigste Optimierung in Coding-Interviews und echten Systemen — es wandelt "immer wieder suchen" in "einmal nachschlagen" um.

Der Raum-für-Zeit-Austausch ist ein wiederkehrendes Ingenieur-Konzept.

Häufigkeitszählung, Caching und Indexierung basieren alle auf dieser einen Idee.