Was ist eine Hash-Tabelle und wie erreicht sie O(1) Suche?

Question

Accepted Answer

Eine **Hash-Tabelle** (Hash-Map) speichert **key → value** Paare und bietet durchschnittliches Einfügen, Suchen und Löschen in **O(1)**. Sie funktioniert, indem jeder Schlüssel eine **Hash-Funktion** durchläuft, die ihn auf einen Index in einem zugrunde liegenden Array (einem "Bucket") abbildet.

## Wie es funktioniert

```text
key "cat" --hash()--> 3   buckets:
key "dog" --hash()--> 0     [0] -> ("dog", 5)
                            [1]
                            [2]
                            [3] -> ("cat", 9)
```

## Beispiel

```python
phone = {}
phone['alice'] = 555_1234   # insert -> hash 'alice' to a bucket
num = phone['alice']        # lookup -> hash again, jump to bucket
del phone['alice']          # delete
'bob' in phone              # membership -> O(1) average
```

## Komplexität

| Operation | Durchschnitt | Schlimmster Fall |
|---|---|---|
| einfügen | O(1) | O(n) |
| suchen | O(1) | O(n) |
| löschen | O(1) | O(n) |

Der **schlimmste Fall** O(n) tritt auf, wenn viele Schlüssel in den gleichen Bucket kollidieren.

## Warum es wichtig ist

- **Stärken:** extrem schneller schlüsselbasierter Zugriff; flexible Schlüssel.
- **Schwächen:** keine Sortierung von Schlüsseln; zusätzlicher Speicher; O(n) im schlimmsten Fall; benötigt eine gute Hash-Funktion.

Hash-Tabellen sind praktisch gesehen wohl die am meisten genutzte Datenstruktur — sie stecken hinter Wörterbüchern, Sets, Caches, Datenbankindizes und Deduplizierung.

Einen linearen Scan durch eine Hash-Suche zu ersetzen ist einer der häufigsten Wege, einen O(n²) Algorithmus in O(n) umzuwandeln.