Wie können wir eine Zahl i abspeichern und möglichst schnell wiederfinden, d. h., entscheiden, ob wir diese Zahl gespeichert haben oder nicht? Hätten wir ein unendlich langes Array A zur Verfügung, so könnten wir einfach die Zahl i in das i-te Element A[i] des Arrays schreiben. Der Test, ob wir i abgespeichert haben, würde dann nur Zeit O(1) benötigen: Wir müssten nur an Stelle A[i] nachschauen. Steht dort eine 0, haben wir i nicht gespeichert. Steht dort die Zahl i, so haben wir i gespeichert. (Das Problem, ein unendlich langes Array mit lauter Nullen zu initialisieren, vernachlässigen wir bei dieser Beschreibung.)

Nun gibt es aber kein unendlich langes Array A. Daher behelfen wir uns mit einem Trick: Wir hacken (engl. „to hash“; vgl. auch mit dem franz Wort „Hashé“) das Array A gedanklich in Stücke, und zwar vor den Stellen m, 2m, 3m usw., wobei m die Größe eines Arrays T ist, das wir uns in Bezug auf die Größe unseres Hauptspeichers wirklich leisten können, also etwa m=1000. Die Einzelstücke legen wir (gedanklich) alle untereinander, so dass die Elemente 0, m, 2m, 3m usw. des ursprünglichen Arrays A alle untereinander zu liegen kommen: Sie werden alle auf das Element T[0] des Arrays T „gehasht“. Abbildung 3.4 veranschaulicht dies.

Abbildung 3.4. Hashing

Die Grundidee von Hashing: Haue ein unendlich großes Array in Stücke und lege die Einzelstücke untereinander. Positionen i mit gleichem Hash-Wert kommen untereinander zu liegen. Der Hash-Wert ist hier i mod m.

Wollen wir nun eine Zahl i abspeichern, so speichern wir sie an der Stelle i mod m im Array T ab, d. h. im Element T[i mod m]. T wird in diesen Zusammenhang als Hash-Tafel (hash table), Hash-Tabelle oder einfach als Hash bezeichnet. Das Verfahren selbst wird als Hashing bezeichnet. Die einzelnen Positionen in der Hash-Tafel werden als Slots bezeichnet. (Wie der Name nahelegt und wie wir gleich sehen werden, können mehrere Zahlen in einen Slot fallen, also auf dieselbe Position gehasht werden.)

Eine Funktion wie h(i)=i mod m, die zu einem ganzzahligen i die Nummer des Slots in einer Hash-Tafel berechnet, wird als Hash-Funktion bezeichnet, der von ihr berechnete Wert h(i) als Hash-Wert (hash value).

Nun taucht ein neues Problem auf: Mehrere i können auf dieselbe Position gehasht werden; z. B. werden alle Vielfachen von m auf die Position 0 gehasht. Um mit solchen Kollisionen umgehen zu können, besteht das Array T bei Hashing mit Verkettung (hashing with chaining) nicht aus ganzen Zahlen, sondern aus verketteten Listen von ganzen Zahlen, eine für jeden Slot. In einen Slot können nun beliebig viele Zahlen fallen; sie werden in der Liste gespeichert. Abbildung 3.5 zeigt Hashing mit Verkettung bei einer Hash-Tafel mit 4 Slots und 7 gespeicherten Zahlen.

Abbildung 3.5. Hashing mit Verkettung

Hashing mit Verkettung: Eine Hash-Tafel mit 4 Slots und 7 gespeicherten Zahlen. Die Hash-Funktion ist h(i)=i mod 4. Es ist z. B. h(17)=1 und h(-4)=0. Der Belegungsfaktor ist 7/4. Bei einer Verdoppelungsstrategie würde das Einfügen einer weiteren Zahl zu einem Rehash in eine Tafel der Größe 8 führen.

Um eine Zahl i zu speichern, wird h(i) berechnet und i wird an die i-te Liste angehängt. Dazu ist immer lediglich Zeit O(1) nötig. Um dagegen nachzuschauen, ob i im Hash gespeichert ist, wird ebenfalls h(i) berechnet und die i-te Liste wird nach der Zahl i durchsucht. Die Zeit, die dazu benötigt wird, ist proportional zur Länge der i-ten Liste.

Wie lang also wird die i-te Liste? Im schlechtesten Fall werden alle Zahlen auf denselben Slot gehasht; dann entartet die Struktur zu einer gewöhnlichen linearen Liste. Im besten Fall verteilt die Hash-Funktion die Zahlen gleichmäßig auf alle m Listen. Dann ist bei n gespeicherten Zahlen die Länge jeder Liste n/m und die mittlere Zugriffszeit daher O(n/m). Der Quotient n/m wird als Belegungsfaktor (load factor) bezeichnet. Ist n kleiner gleich m, d. h., sind insgesamt höchstens so viele Zahlen gespeichert wie es Slots gibt, so ist bei gleichmäßiger Verteilung die mittlere Zugriffzeit ebenfalls O(1), also konstant.

Werden nun mehr und mehr Zahlen gespeichert, d. h., wächst n immer weiter an, so wird auch der Belegungsfaktor und damit die mittlere Zugriffszeit O(n/m) immer größer. Irgendwann würde n viel größer als m sein und dann könnte die Zugriffszeit nicht mehr als konstant angesehen werden. Damit dies nicht geschieht, wird ein weiterer Trick angewendet: Um den Belegungsfaktor immer kleiner als 2 zu halten, wird die Größe der Tafel verdoppelt, wenn n doppelt so groß wie m ist. Das bedeutet, dass alle Elemente der alten Tafel in eine neue „umgehasht“ werden, die doppelt so viele Slots enthält. Dies wird als Rehash bezeichnet. Werden dagegen sehr viele Zahlen aus dem Hash gelöscht und sinkt dadurch der Belegungsfaktor auf 1/2 oder darunter, wird die Größe der Tafel halbiert und es findet ebenfalls ein Rehash statt. Unmittelbar nach einem Rehash ist der Belegungsfaktor immer 1, sei es nach Verdoppelung oder Halbierung der Tafelgröße.

Ein solcher Rehash kann durchaus seine Zeit dauern - er ist proportional zu n. Man kann aber leicht durch eine amortisierte Analyse zeigen, dass sich die Kosten eines Rehashs im Durchschnitt kaum bemerkbar machen. Verteilt man seine Kosten auf die Zugriffsoperationen, die danach erfolgen können, bevor ein erneuter Rehash stattfindet, so zeigt die Analyse, dass die amortisierte Zeit einer Operation immer O(2·n/m) ist, und daher wegen n/m<2 als konstant angesehen werden kann. Das ist letztendlich der Grund, warum Hashing ein so schnelles Verfahren zum Speichern und Wiederauffinden von Informationen ist.

Wir haben bisher nur von Zahlen gesprochen, die gespeichert werden sollen. Tatsächlich aber kann Hashing dazu verwendet werden, beliebige Informationen zu speichern und wieder aufzufinden - es muss nur jeder zu speichernden Information ein Hash-Wert h zugeordnet werden können, der sich mit Hilfe eines Algorithmus berechnen lässt. Die Implementierung des Hashes speichert dann nicht nur diesen Hash-Wert h, sondern mit ihm zusammen auch ein Verweis auf die ursprüngliche (ungehashte) Information, die in diesem Zusammenhang als Schlüssel bezeichnet wird.

Jeder Compiler z. B. speichert die im Programmtext auftretenden, vom Programmierer verwendeten Bezeichner wie Variablennamen, Funktionsnamen usw. in einer Hash-Tafel. Hierzu ist eine Funktion h nötig, die aus einem String eine Zahl berechnet, die als Hash-Wert verwendet werden kann. Die einfachste Möglichkeit dazu ist es, die ASCII-Werte der Zeichen als langen Bitstring zu interpretieren (genauer gesagt: als Koeffizienten eines Polynoms zur Basis 2^7).

Hashing wird auch als Verfahren benutzt, um einen assoziativen Containertyp zu implementieren. Hierbei wird zu jedem Schlüssel in der Tafel auch noch ein Verweis auf den zum Schlüssel assoziierten Wert gespeichert.

So speichert etwa ein Compiler zu jedem Variablennamen den Typ der Variablen, wie er in der Deklaration festgelegt wird.

Das gesamte Verfahren steht und fällt natürlich mit der Annahme, dass die Schlüssel gleichmäßig auf die einzelnen Slots verteilt werden. Damit diese Annahme erfüllt ist, müssen die Wahrscheinlichkeitsverteilung, mit der die Schlüssel aus ihrem Definitionsbereich gezogen und in den Hash eingefüttert werden, und die verwendete Hash-Funktion zueinander passen.

Formaler ausgedrückt: Wenn P(k) die Wahrscheinlichkeit ist, mit der Schlüssel k dem Verfahren eingefüttert wird, und man alle P(k) summiert für die k, die auf Slot j gehasht werden, dann sollte man die Summe 1/m erhalten. Und dies sollte für alle Slots j gelten. Das heißt anders ausgedrückt, dass auf jeden Slot 1/m-tel aller Schlüssel gehasht werden.

Obige Funktion h(i)=i mod m z. B. verteilt Zahlen gleichmäßig auf die Hash-Tafel, wenn nur die Zahlen selbst aus einem (im Vergleich zur Anzahl der Slots) sehr großen Intervall stammen und alle mit der gleichen Wahscheinlichkeit daraus gezogen werden.

Dies ist aber nicht immer der Fall. Weiß man z. B. von vorneherein, dass nur gerade Zahlen als Schlüssel auftreten werden, so würde diese Funktion jeden zweiten Slot leer lassen (wenn m aufgrund von Verdoppelungen und Halbierungen eine Potenz von 2 ist). Hier wäre es besser, eine Hash-Funktion zu benutzen, die zuerst einmal das letzte Bit des Schlüssels abschneidet.

Zudem gehen die bisherigen Überlegungen davon aus, dass der Hash-Wert selbst in konstanter Zeit berechnet werden kann. Die Geschwindigkeit, mit der die Hash-Funktion arbeitet, spielt beim Gesamtverfahren natürlich ebenfalls eine Rolle. Die oben vorgestellte Funktion, die aus jedem String eine Zahl macht, braucht umso mehr Zeit, je länger der String ist.

Es gibt keine Hash-Funktion, die für jeden Typ von Eingabeschlüssel geeignet ist und die bei jeder Verteilung der Schlüssel gleich gut arbeitet. Eine gute Hash-Funktion für eine bestimmte Art von Schlüsseln und eine bestimmte Verteilung zu finden, ist immer ein Kunst. Auf die Konstruktion von guten Hash-Funktionen näher einzugehen, würde den Rahmen dieser Einführung sprengen.

LEDA bietet Hashing mit Verkettung und Tafelverdoppelung an, gekapselt in die Klasse h_array. Die Größe der ersten Tafel ist m=1, d. h., die Datenstruktur startet mit nur einem Slot. (Diese initiale Größe lässt sich im Konstruktor auch auf einen anderen Wert einstellen.) Die von LEDA verwendete Hash-Funktion ist h(i)=i mod m, wobei m bei jeder Verdoppelung bzw. Halbierung ebenfalls verdoppelt bzw. halbiert wird. m ist also immer eine Potenz von 2. (Es sei denn, die initiale Tafelgröße wurde auf einen anderen Wert l als 1 gesetzt; dann ist sie immer von der Form l·2^k.) Die Eingabeschlüssel i müssen aus dem Intervall stammen, das vom C++-Typ int umfasst wird, also i. d. R. dem Intervall [-2^31..2^31-1].

Um dem Benutzer die Möglichkeit zu geben, die Berechnung des Hash-Wertes zu beeinflussen, kann dieser der Funktion eine eigene Funktion g vorschalten. LEDA hasht dann den Schlüssel i auf den Wert h(g(i))). g muss ganze Zahlen vom Typ int liefern. Es handelt sich dabei also um ein zweistufiges Verfahren.

Für die Zahlentypen von C++ ist g vordefiniert als die Identitätsfunktion g(i)=i. Für Pointer auf void ist g vordefiniert als die Funktion, die die Adresse des Pointers als ganze Zahl interpretiert und zurückliefert. Will der Benutzer g für diese Typen abändern, so muss er die Funktion

int Hash(const int& i);

bzw. ihre Äquivalente für die anderen Zahlentypen überschreiben. Um einen selbstdefinierten Typ T ebenfalls zu einem gehashten Typ zu machen und ihn somit als Schlüsseltyp eines h_array benutzen zu können, muss der Benutzer gemäß der LEDA-Regel „Anforderungen an gehashte Typen“ die Funktion

int Hash(const T& i);

implementieren, die in den Namensraum leda eingeordnet sein muss. Diese wird dann von LEDA als Eingabe g(i) des Hashings h benutzt.

Darüber hinaus muss für den Typ T der Gleichheitsoperator

bool operator == (const T&, constT&);

definiert sein. Das liegt an Folgendem: Wenn in dem assoziativen Container vom Typ h_array zwei unterschiedliche Schlüssel k1 und k2 mit den assoziierten Werten v1 bzw. v2 auf denselben Slot gehasht werden, so soll später dennoch anhand der Schlüssel k1 bzw. k2 auf v1 bzw. v2 zugegriffen werden können, ohne diese Werte zu verwechseln. Dazu müssen k1 und k2 innerhalb der Implementierung des Hashs aber unterscheidbar sein, was nicht über ihre Hashwerte geschehen kann - diese sind ja gleich. Daher muss der Operator == die Möglichkeit zur Unterscheidung implementieren.

Zusätzlich muss der Operator == eine Äquivalenzrelation auf T realisieren. Außerdem muss für alle Objekte x und y des Typs T gelten: Wenn x == y ist, dann auch Hash(x) == Hash(y).

Sind dagegen zwei Objekte x und y gleich, d. h., es gilt x == y, so sollte die Hashfunktion sie nicht als verschieden ansehen. Es muss dann auch Hash(x) == Hash(y) gelten.

Darüber hinaus bietet LEDA mit der Klasse map noch eine besonders schnelle Implementierung für Schlüssel an, die ganzzahlig, vom Pointer-Typ oder vom Item-Typ sind. Das dabei verwendete Verfahren ist einstufig und kann vom Benutzer nicht beeinflusst werden: Die Schlüssel k werden als 32-Bit-Werte interpretiert, und k wird dann auf die Position k mod 2^m gehasht, wobei m die aktuelle Anzahl der Slots ist. Auch dieses Verfahren arbeitet mit Tafelverdoppelung. Es ist i. Allg. wesentlich schneller als das zweistufige Verfahren von h_array, weil die Hash-Funktion festverdrahtet ist; dafür ist man hier bei der Wahl der Schlüsseltypen sehr eingeschränkt.