09 – Hash-Tabelle

 

Wir haben bisher die statische Datenstruktur Feld (array) und die dynamische Datenstruktur Liste kennengelernt. Eine Hash-Tabelle ist ein Zwischending, nämlich ein Feld mit einer Überlaufliste.

Idee
Der Rechenaufwand für Operationen in Listen steigt schnell mit der Listenlänge. Die Hash-Tabelle setzt daher auf mehrere kurze Listen.

Die Grundlage für den Datentyp ist ein statisches Feld F mit fester Länge nF (typischerweise eine Primzahl):

Jedes “Kästchen” des Feldes hat einen Index. Es werden nun nK Werte eingefügt, die über einen Schlüssel (key) identifiziert werden. Der Wertebereich der Schlüssel ist allerdings viel größer als die Anzahl der Speicherplätze in dem statischen Feld (es gilt also nK >> nF).
Der Schlüssel wird daher mit einer bestimmten Operation auf einen Wert x ∈ {0, …, nF-1} reduziert. Nun können die Elemente in das Feld eingefügt werden und zwar bei dem Index des reduzierten (“verhackstückten”) Schlüssels.
Aufgrund der Ungleichung nK >> nF gibt es aber mehr Elemente als Indizes. Verschiedene Elemente fallen durch Anwendung der Hashfunktion auf den gleichen Index. Diese werden dann mit einer Liste an das Feld angehängt:

Es wird eine Hashfunktion benötigt, die den Schlüssel auf einen Wert zwischen 0 und nF-1 reduziert. Von dieser Funktion hängt hauptsächlich ab, wie gut die Hash-Tabelle funktioniert. Eine Möglichkeit für eine solche Funktion ist die Modulofunktion. Diese teilt den Eingabewert durch nF und gibt als Ausgabewert den ganzzahligen Rest der Division zurück.

Das statische Feld sollte so gewählt werden, dass die angehängten Überlauflisten nicht zu lang werden (da sonst die Rechenzeit zunehmen würde).

Diese Datenstruktur ist gut zum “schnellen Speichern und Wiederfinden”. Ein Sortieren ist hier nicht möglich.