Eine Hash-Tabelle (auch Hashtabelle, Hash-Map oder Dictionary) ist eine Datenstruktur, die Werte über einen Schlüssel speichert und abruft. Statt Elemente wie beim Array über einen Index von 0 bis n zu durchsuchen, berechnet eine Hash-Funktion aus dem Schlüssel direkt die Speicherposition. Im Idealfall findet die Hash-Tabelle jeden Eintrag in konstanter Zeit — unabhängig davon, wie viele Daten gespeichert sind.
So funktioniert eine Hash-Tabelle
Die Tabelle besteht aus einem Array von Speicherplätzen (Buckets). Wird ein Wert gespeichert, läuft das in drei Schritten ab:
- Die Hash-Funktion berechnet aus dem Schlüssel (z. B. einem String) eine Zahl.
- Diese Zahl wird auf die Größe des Bucket-Arrays abgebildet (meist per Modulo) — das Ergebnis ist der Index.
- Der Wert wird an diesem Platz abgelegt. Beim Suchen läuft derselbe Weg erneut: Schlüssel hinein, Index heraus, Wert abholen.
Weil die Hash-Funktion aus beliebigen Schlüsseln immer dieselbe Position liefert, sind Einfügen, Suchen und Löschen im Durchschnitt in O(1) erledigt — das Algorithmus-Verhalten ist deutlich besser als bei einem linearen Durchlauf.
Kollisionen: Wenn zwei Schlüssel denselben Platz wollen
Perfekt ist keine Hash-Funktion: Verschiedene Schlüssel können denselben Index ergeben. Diese Kollision wird klassisch auf zwei Arten aufgelöst:
- Verkettung (Separate Chaining): Jeder Bucket hält eine kleine Liste; kollidierende Werte werden dort angehängt. Die verkettete Liste ist dafür der typische Baustein.
- Offene Adressierung: Bei einer Kollision wird im Bucket-Array nach dem nächsten freien Platz gesucht (z. B. linear oder quadratisch).
Ein wichtiger Kennwert ist der Lastfaktor (Füllgrad der Tabelle). Wird er zu groß, wachsen Kollisionen und die Zugriffe werden langsamer. Dann wird die Tabelle vergrößert und alle Einträge werden neu verteilt (Rehash).
Wofür Hash-Tabellen eingesetzt werden
- Wörterbücher und Maps in Programmiersprachen: Python-Dict, Java-HashMap, Go-Map, JavaScript-Object.
- Caches: Häufig benötigte Werte werden nach Schlüssel abgelegt und in O(1) wiedergefunden.
- Sets: Mengen mit schneller Existenzprüfung (ist Element enthalten? ja/nein).
- Teilbereiche von Datenbanken: Hash-Indizes beschleunigen exakte Gleichheitssuchen.
- Tabellen für Passwort-Hashes zusammen mit Salt.
Vorteile und Grenzen
Der große Vorteil ist die konstante Zugriffszeit für exakte Schlüssel. Nachteile: Die Reihenfolge der Einträge ist nicht vorhersagbar (die Tabelle iteriert in Bucket-Reihenfolge), und der Speicherverbrauch ist wegen der Bucket-Arrays höher als bei einer dichten Liste. Für Bereichsabfragen („alle Werte zwischen X und Y“) sind Hash-Tabellen daher ungeeignet — dafür gibt es sortierte Strukturen wie Bäume.