Hashtabelle

Grundidee und Funktionsweise

Eine Hashtabelle, auch Hash Map oder Streuwerttabelle, ist eine Indexstruktur zum schnellen Speichern und Auffinden von Datenelementen in großen Datenmengen. Im Vergleich zu Baumstrukturen wie einem B+-Baum oder zu Skip-Listen benötigen Einfüge- und Löschoperationen üblicherweise konstanten Zeitaufwand.

Das Hashverfahren verwendet eine mathematische Hashfunktion. Sie berechnet aus dem Schlüssel, der ein Datenobjekt eindeutig identifiziert, einen Hashwert. Dieser bestimmt die Position in der meist als Array implementierten Tabelle. Ein solcher Speicherbereich heißt Bucket. Dadurch muss das Verfahren nicht alle Datenobjekte durchsuchen. Im Idealfall erhält jedes Objekt einen eigenen Bucket.

Hashtabellen bilden unter anderem Mengen, Caches und assoziative Arrays ab. Bei einem assoziativen Array, auch Map, Lookup Table, Dictionary oder Wörterbuch genannt, wird einem Schlüssel ein Wert zugeordnet, der über den Schlüssel schnell nachgeschlagen werden kann. Compiler und Interpreter verwenden Hashtabellen häufig als Symboltabellen. Datenbanken nutzen sie als Hashindizes für Tabellen.

Kollisionen und ihre Auflösung

Eine Hashfunktion ist im Allgemeinen nicht injektiv: Verschiedene Schlüssel können denselben Hashwert und damit denselben Bucket erhalten. Dies heißt Kollision. Bei einer Suche berechnet das Verfahren zunächst den Bucket und vergleicht danach den Suchschlüssel direkt mit den dort infrage kommenden Objekten. Häufen sich viele Objekte in wenigen Buckets, während andere unbenutzt bleiben, kann die Hashtabelle entarten.

Zwei grundlegende Lösungsformen sind:

• Beim geschlossenen Hashing mit offener Adressierung wird bei einem belegten Platz ein anderer freier Tabellenplatz gesucht. Typische Prüfverfahren sind lineares Sondieren mit meist konstantem Abstand 1, quadratisches Sondieren mit quadratisch wachsenden Abständen und Doppel-Hashing, bei dem eine zweite Hashfunktion den Abstand liefert.

• Beim offenen Hashing mit geschlossener Adressierung enthält jeder Bucket einen Behälter für alle Daten mit demselben Hashwert. Dieser wird häufig als lineare Liste umgesetzt. Nach der Berechnung des Buckets müssen dessen Einträge durchsucht werden. Im schlimmsten Fall befinden sich alle Elemente in demselben Bucket.

Die Bezeichnungen offenes und geschlossenes Hashing werden teilweise genau umgekehrt verwendet.

Verkettung, offene Adressierung und Kuckucks-Hashing

Beim Hashing mit Verkettung (separate chaining) enthält jeder Bucket eine dynamische Datenstruktur, beispielsweise eine Liste oder einen Baum. Darin lassen sich mehrere Schlüssel speichern. Die Operationszeit setzt sich aus der konstanten Zeit zum Bestimmen des Buckets und der Zeit für die Operation innerhalb seiner Datenstruktur zusammen. In einer guten Hashtabelle enthalten Buckets meistens keinen oder einen, gelegentlich zwei oder drei Einträge. Viele größere Buckets zeigen, dass das Hashing ungünstig arbeitet. In Datenbanken ist Verkettung verbreitet; dort können Buckets ein Vielfaches der Sektorengröße des Speichermediums umfassen und sektorenweise eingelesen werden.

Bei offener Adressierung liegt jeder Datensatz direkt in der Tabelle, und jeder Bucket nimmt häufig nur einen Schlüssel auf. Für m Buckets wird eine Folge von bis zu m Hashfunktionen beziehungsweise Prüfpositionen verwendet. Beim Einfügen folgt man dieser Prüfsequenz bis zu einem freien Bucket. Bei der Suche wird dieselbe Reihenfolge durchlaufen, bis der Schlüssel oder ein noch nie benutzter Bucket gefunden wird.

Kuckucks-Hashing verwendet zwei Hashfunktionen und damit zwei mögliche Speicherorte je Schlüssel. Ist der erste Platz belegt, verdrängt der neue Schlüssel den vorhandenen; dieser wandert zu seinem alternativen Platz. Das setzt sich gegebenenfalls fort. Entsteht eine Schleife, wird üblicherweise nach log n Schritten abgebrochen und die Tabelle mit zwei neuen Hashfunktionen aufgebaut. Die Wahrscheinlichkeit eines solchen Rehashings liegt pro Einfügen in der Größenordnung O(1/n).

Sondierungsalgorithmen

Beim linearen Sondieren wird ab der Ausgangsposition jeweils der nächste Bucket geprüft:

h_i(x) = (h(x) + i) mod m.

Nach dem letzten Bucket beginnt die Suche wieder am Anfang. Das Verfahren kann alle Buckets erreichen, ist speichersparend und wegen benachbarter Speicherzugriffe in der Praxis oft schnell. Allerdings entstehen zusammenhängende Cluster, in denen die Zugriffszeit steigt; dies heißt primäres Clustering. Löschungen werden häufig durch Tombstones markiert: Sie kennzeichnen einen zuvor belegten Platz, beenden eine Suche aber nicht. Für den Lastfaktor α = n/m beträgt der Erwartungswert bei erfolgloser Suche 1/2 · (1 + (1/(1−α))²), bei erfolgreicher Suche 1/2 · (1 + 1/(1−α)).

Quadratisches Sondieren prüft Positionen mit quadratisch wachsendem Abstand in wechselnden Richtungen, beispielsweise h(k)+1, h(k)−1, h(k)+4, h(k)−4 und h(k)+9:

h_i(x) = (h(x) + (−1)^(i+1) · ⌈i/2⌉²) mod m.

Für m = 4·j+3 mit primem m erreicht die Sondierungsfolge jeden Bucket. Das Verfahren vermindert primäres Clustering, kann aber sekundäres Clustering erzeugen; in manchen Fällen stehen nur ⌊m/2⌋ Buckets zur Auswahl. Die Erwartungswerte sind 1/(1−α) − α + ln(1/(1−α)) bei erfolgloser und 1 + ln(1/(1−α)) − α/2 bei erfolgreicher Suche.

Doppel-Hashing verwendet zwei unabhängige Hashfunktionen h und h′:

h_i(x) = (h(x) + h′(x)·i) mod m.

Unabhängigkeit bedeutet, dass die Wahrscheinlichkeit einer Doppelkollision h(x)=h(y) und h′(x)=h′(y) gleich 1/m² ist. Die Kosten liegen nahe am idealen Hashing. Die Erwartungswerte betragen 1/(1−α) bei erfolgloser und (1/α)·ln(1/(1−α)) bei erfolgreicher Suche. Beim Robin-Hood-Hashing kann ein neuer Schlüssel einen vorhandenen verdrängen, wenn sein Prüfwert größer ist; dadurch sinken die schlechtesten Suchzeiten und deren Streuung.

Brent-Bansley-Hashing vergleicht bei einer Kollision alternative Plätze des neuen und des vorhandenen Elements. Ist der alternative Platz des vorhandenen Elements frei, werden die Elemente entsprechend umgesetzt; andernfalls wird die Prüfung fortgesetzt. Elastic Hash und Funnel Hash werden im Artikel im Zusammenhang mit optimalen Grenzen für offene Adressierung ohne Umordnung genannt.

Leistung und dynamische Tabellen

Bei geeigneter Hashfunktion und wenigen Kollisionen benötigt ein Zugriff auf n gespeicherte Elemente im Mittel O(1), also konstanten Zeitaufwand. Dafür bleiben in der Praxis üblicherweise 20 bis 30 Prozent der Tabellenfelder ungenutzt. Ein B-Baum benötigt für einen Zugriff dagegen O(log n); seine gesamte Datenstruktur beansprucht Speicher der Größenordnung O(n).

Der Füllgrad ist definiert als:

Füllgrad = gespeicherte Elemente / Buckets.

Mit wachsendem Füllgrad steigt die Kollisionswahrscheinlichkeit. Im schlechtesten Fall müssen alle Einträge durchsucht werden, sodass ein Zugriff O(n) kostet. Abhilfe schafft eine größere Tabelle mit anschließender Restrukturierung. Hashtabellen pflegen außerdem normalerweise keine Ordnungsbeziehung zwischen Schlüsseln; Nachbarschaftssuchen sowie die Suche nach dem kleinsten oder größten Schlüssel sind daher nicht effizient.

Dynamisches Hashing vergrößert die Tabelle bei Bedarf. Da eine gewöhnliche Änderung des Wertebereichs der Hashfunktion auch bereits gespeicherte Hashwerte verändern würde, verwendet man dafür besondere Hashfunktionen, deren Wertebereich ohne Änderung vorhandener Hashwerte erweitert werden kann. Vorteile sind ein nicht fest begrenztes Datenvolumen, problemloses Löschen und keine Clusterbildung durch Adresskollisionen. Ohne ordnungserhaltende Hashfunktion bleiben geordnetes Durchlaufen sowie die effiziente Suche nach minimalem oder maximalem Schlüssel unmöglich.

Einsatz und Grenzen in Datenbanken

In Datenbanken können Hashindizes große Datenmengen sehr schnell durchsuchen, weil die Berechnung des Hashwerts die möglichen Zielobjekte in einem Schritt stark einschränkt. Unter günstigen Bedingungen entstehen dadurch ideale Zugriffszeiten.

Gegen den Einsatz sprechen mögliche Entartung bei wachsenden Datenmengen, der Aufwand für Vergrößerung und erneutes Hashen sowie ungünstige Ein-/Ausgabe-Zugriffsmuster, wenn die Tabelle auf einem Datenträger liegt. Deshalb müssen Hashindizes gegen alternative Indexstrukturen wie B+-Bäume abgewogen werden.

Die meisten Hashfunktionen mischen Schlüssel gezielt, um sie gleichmäßig zu verteilen. Deshalb kann man normalerweise nicht effizient zum gemäß einer Ordnung nächsten oder vorherigen Datensatz wechseln, Wertebereiche durch Ungleichheitsbedingungen wie „größer als“ oder „kleiner als“ abfragen oder alle Werte sortiert lesen. Spezielle ordnungserhaltende Hashfunktionen ermöglichen dies, setzen für einen effizienten Einsatz aber meist eine vorherige Analyse der Datenverteilung voraus. Sie werden daher vor allem in Datenbanksystemen verwendet, die solche Analysen beispielsweise zur Anfrageoptimierung durchführen.