Hash-Tabelle — So funktionieren Hashing und Kollisionsauflösung

Eine Hash-Tabelle speichert Schlüssel-Wert-Paare, indem sie jeden Schlüssel per Hashing in einen Array-Index umwandelt. Dadurch kann die Tabelle direkt in die Nähe der richtigen Stelle springen, statt alle gespeicherten Einträge nacheinander zu durchsuchen.

Deshalb liegen Hash-Tabellen bei Suche, Einfügen und Löschen im Durchschnitt oft nahe bei $O(1)$. Diese Aussage gilt aber nur unter Bedingungen: Die Hashfunktion muss die Schlüssel einigermaßen gut verteilen, und die Tabelle braucht weiterhin eine Regel für Kollisionen.

Was eine Hash-Tabelle macht

Eine Hash-Tabelle speichert Schlüssel-Wert-Paare wie "name" -> "Ada" oder 42 -> "blue". Sie hat zwei Hauptbestandteile:

• ein Array aus Slots oder Buckets
• eine Hashfunktion, die jeden Schlüssel auf einen dieser Slots abbildet

Wenn das Array $m$ Slots hat, kann man sich die Hashfunktion als eine Vorschrift vorstellen, die einen Index von $0$ bis $m-1$ erzeugt.

Für ein kleines Beispiel mit ganzen Zahlen könnte die Regel sein

$$h(k) = k \bmod 8$$

Dann geht der Schlüssel $10$ in Slot $2$, weil $10 \bmod 8 = 2$.

Echte Hashfunktionen sind sorgfältiger konstruiert, besonders für Zeichenketten und größere Datenmengen. Die Grundidee bleibt aber gleich: schnell einen Index berechnen und dann den dort gespeicherten Eintrag prüfen.

Warum Hash-Kollisionen unvermeidbar sind

Eine Kollision entsteht, wenn zwei verschiedene Schlüssel auf denselben Slot abgebildet werden.

Das ist normal, weil die Tabelle meist weniger Slots hat als es mögliche Schlüssel gibt. Bei

$$h(k) = k \bmod 8$$

werden die Schlüssel $10$, $18$ und $26$ alle auf Slot $2$ abgebildet. Die Funktion arbeitet also genau wie definiert, und trotzdem muss die Tabelle einen Konflikt auflösen.

Eine Hash-Tabelle verspricht also nicht für jeden Schlüssel einen eindeutigen Slot. Sie verspricht einen schnellen Weg, die Suche einzugrenzen, sofern Kollisionen gut behandelt werden.

Durchgerechnetes Beispiel: Eine Tabelle, eine Kollision

Angenommen, eine Tabelle hat $8$ Slots und verwendet

$$h(k) = k \bmod 8$$

Füge die Schlüssel $10$, $18$ und $7$ ein.

Zuerst geht $10$ in Slot $2$, weil $10 \bmod 8 = 2$.

Als Nächstes wird auch $18$ auf Slot $2$ gehasht, also entsteht eine Kollision.

Dann geht $7$ in Slot $7$, daher gibt es bei diesem Einfügen keine Kollision.

Das nützliche Muster ist immer gleich:

1. Den Schlüssel hashen.
2. Zum vorgeschlagenen Slot gehen.
3. Wenn dort schon ein anderer Schlüssel liegt, die Kollisionsregel anwenden.

Wenn dieses Muster klar ist, lassen sich die zwei wichtigsten Strategien zur Kollisionsbehandlung leichter verstehen.

Verkettung vs. offene Adressierung

Verkettung speichert an jedem Slot einen Bucket

Bei der Verkettung speichert jeder Slot statt nur eines Eintrags eine kleine Sammlung von Einträgen.

Wenn $10$ und $18$ beide auf Slot $2$ gehasht werden, könnte Bucket $2$ enthalten:

• $(10, \text{value}_1)$
• $(18, \text{value}_2)$

Um den Schlüssel $18$ zu finden, springt die Tabelle zu Bucket $2$ und vergleicht nur die Einträge in diesem Bucket.

Verkettung ist konzeptionell einfach, und Löschen ist meist einfacher als bei offener Adressierung. Der Nachteil ist, dass lange Buckets die Operationen verlangsamen.

Offene Adressierung bleibt innerhalb des Arrays

Bei der offenen Adressierung enthält jeder Array-Slot höchstens einen Eintrag. Wenn der eigentliche Slot schon belegt ist, prüft die Tabelle nach einer festen Regel andere Slots.

Eine häufige Regel ist lineares Sondieren: Wenn Slot $2$ belegt ist, probiere $3$, dann $4$, dann $5$ und beginne bei Bedarf wieder von vorn.

Dadurch braucht man keine separaten Bucket-Listen, aber benachbarte belegte Slots können sich zu Clustern aufbauen. Wichtig ist außerdem, dass Suche und Löschen dieselbe Sondierungsregel beachten wie beim Einfügen.

Wann $O(1)$ eine faire Aussage ist

Hash-Tabellen werden oft so beschrieben, dass Suche, Einfügen und Löschen im Durchschnitt $O(1)$ haben. Diese Aussage über den Durchschnittsfall hängt von Bedingungen ab:

• die Hashfunktion verteilt die Schlüssel einigermaßen gut
• der Lastfaktor bleibt unter Kontrolle
• die Kollisionsstrategie ist korrekt implementiert

Der Lastfaktor ist das Verhältnis

$$\text{load factor} = \frac{\text{number of stored entries}}{\text{number of slots}}$$

Wenn die Tabelle zu voll wird, treten Kollisionen häufiger auf, und die Leistung wird schlechter. Deshalb vergrößern viele Implementierungen das Array, wenn es sich füllt.

Die Laufzeit im schlechtesten Fall kann sich trotzdem in Richtung $O(n)$ verschlechtern, wenn sich zu viele Schlüssel im selben Bereich sammeln.

Häufige Fehler bei Hash-Tabellen

Anzunehmen, Kollisionen bedeuteten, dass die Hashfunktion versagt hat

Das tun sie nicht. Kollisionen sind zu erwarten. Die eigentliche Frage ist, ob die Tabelle effizient damit umgeht.

$O(1)$ als bedingungslos zu behandeln

$O(1)$ ist meist eine Aussage über den Durchschnittsfall, nicht ein Versprechen für jede Eingabe und jeden Zeitpunkt.

Hashing hier mit Verschlüsselung zu verwechseln

Eine Hashfunktion im Kontext grundlegender Datenstrukturen dient vor allem der schnellen Indexierung, nicht der Geheimhaltung. Das sind unterschiedliche Ziele.

Zu vergessen, den tatsächlichen Schlüssel zu vergleichen

Zwei Schlüssel können denselben Hashwert haben. Nachdem die Tabelle im richtigen Bucket oder an der richtigen Sondierungsposition angekommen ist, muss sie trotzdem prüfen, ob der Schlüssel wirklich übereinstimmt.

Wann Hash-Tabellen verwendet werden

Hash-Tabellen werden überall dort verwendet, wo schneller schlüsselbasierter Zugriff wichtig ist. Häufige Beispiele sind Wörterbücher, Symboltabellen, Caches, Indizierung und das Zählen von Häufigkeiten in Daten.

Sie passen besonders gut, wenn exakte Suche nach einem Schlüssel wichtiger ist als eine sortierte Reihenfolge der Einträge. Wenn du geordnete Traversierung, Bereichsanfragen oder nächstgelegene Werte brauchst, ist eine andere Struktur möglicherweise besser.

Probiere ein ähnliches Kollisionsbeispiel aus

Nimm ein kleines Array mit $8$ Slots und verwende $h(k)=k \bmod 8$. Füge einige Schlüssel wie $3$, $11$, $19$ und $27$ ein. Löse die Kollisionen dann einmal mit Verkettung und einmal mit linearem Sondieren.

Schon diese eine Übung macht die Hauptidee sehr schnell greifbar: Kollisionen sind unvermeidbar, und die Kollisionsregel verändert das Verhalten der Tabelle. Wenn du einen sinnvollen nächsten Schritt willst, probiere deine eigene Variante mit einer anderen Tabellengröße aus und beobachte, wie sich die Kollisionen ändern.