Erstaunlicherweise gibt es ein Suchverfahren, welches noch schneller ist als das binäre Suchen. Um es anzuwenden, muss man die Objekte in einer sogenannten Hash-Tabelle abspeichern. Solche Hash-Tabellen gibt es in zahlreichen Varianten. Hier soll nur ihr Grundprinzip anhand einer besonders einfachen Varianten dargestellt werden.
Eine Hash-Tabelle ist eine Reihung von Listen. Etwas konkreter: Jede Komponente der Reihung ist der Beginn einer Liste und hat entweder den Wert null (dann ist diese Liste noch leer) oder enthält eine Referenz auf das erste Objekt einer Liste.
Die Reihung, aus der eine Hash-Tabelle besteht, hat eine feste, unveränderbare Länge (z.B. die Länge 10 oder die Länge 10.000 oder ... , je nach Anwendung). Die einzelnen Listen in der Reihung haben anfänglich alle die Länge 0, können aber jederzeit verlängert werden, indem man ein weitere Objekte einfügt. Normalerweise sind die einzelnen Listen unsortiert (es gibt aber auch eine Variante von Hash-Tabelle, bei der die Listen sortiert gehalten werden).
In der Hash-Tabelle speichert man Objekte ab, die im einfachsten Fall nur aus einem Schlüssel (und in realistischeren Fällen aus einem Schlüssel und irgendwelchen dazugehörigen Daten) bestehen. Als konkrestes Beispiel wollen wir folgenden Fall betrachten: Die 14 Schlüssel (vom Typ String)
"Ali", "Babsy", "Alfred", "Arno", "Alice", "Benno", "Kurt", "Alex", "Angy", "Bine", "Max", "Franz", "Susi", "Alf"
sollen (ohne weitere dazugehörige Daten) in eine Hash-Tabelle der Länge 10 eingefügt werden. Nach dem Einfügen der Schlüssel soll es dann möglich sein, von einem beliebigen Schlüssel (String) zu prüfen, ob er in der Hash-Tabelle vorkommt oder nicht.
Das Einfügen eines neuen Objektes in die Hash-Tabelle erfolgt in zwei Schritten:
Schritt 1: Aus dem Schlüssel des neuen Objekts wird mit einer sogenannten Hash-Funktion ein Index (in unserem Beispiel: eine Zahl zwischen 0 und 9) berechnet.
Schritt 2: Dann wird das neue Objekt in die (dem Index) ensprechende Liste eingefügt.
Das Suchen eines Schlüssels in der Hash-Tabelle erfolgt ebenfall in zwei Schritten:
Schritt 1: Aus dem Schlüssel, nach dem gesucht werden soll, wird mit der Hash-Funktion ein Index (im Beispiel: eine Zahl zwischen 0 und 9) berechnet.
Schritt 2: Dann wird der Schlüssel in der (dem Index) entsprechenden Liste gesucht.
Hier wird also vorausgesetzt dass der Leser weiss, wie man ein Objekt in eine Liste einfügt bzw. wie man einen Schlüssel in einer Liste sucht (siehe Kapitel 4.4. auf Seite 35).
Das Geheimnis einer Hash-Tabelle steckt also im Wesentlichen in der verwendeten Hash-Funktion. Es gibt sehr viele verschiedene Hash-Funktionen. Was sie leisten und was sie gut oder schlecht macht soll anhand einiger konkreter Beispiele erläutert werden.
Jede Hash-Funktion hat einen Schlüssel als Parameter (in unserem Beispiel ist das ein Parameter vom Typ String) und liefert als Ergebnis einen Index der Hash-Tabelle (im Beispiel ein int-Wert zwischen 0 und 9). Beginnen wir mit einer der schlechtesten Hash-Funktionen die es gibt:
int hash01(String s) {
return 3; // oder eine andere Zahl zwischen 0 und 9
}
Wenn man diese Hash-Funktion verwendet, werden alle Objekte in die Liste 3 der Hash-Tabelle eingefügt und die anderen Listen (0 bis 2 und 4 bis 9) bleiben leer. Hier eine Darstellung der Hash-Tabelle, nachdem alle vierzehn Beispiel-Schlüssel (siehe oben) mit Hilfe der Funktion hash01 eingefügt wurden:
|
Index |
Elemente in den Listen |
0 |
|
1 |
|
2 |
|
3 |
Ali Babsy Alfred Arno Alice Benno Kurt Alex Angy Bine Max Franz Susi Alf |
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 |
|
Tabelle 4.6: Konstante Hash-Funktion
Die Anzahl der Suchschritte mit hash01 ist insgesamt 105. Dies bedeutet: Wenn man jeden Schlüssel, der in der Hash-Tabelle vorkommt, einmal sucht, braucht man dazu insgesamt (und „im wesentlichen“) 105 „Listen-Suchschritte“. Den Schlüssel "Ali" findet man nach einem Schritt, für "Babsy" braucht man zwei Schritte, für "Alfred" drei Schritte, ... und für "Alf" 14 Schritte, macht insgesamt 105 Schritte. Diese Zahl ist ein Maß für die Güte (bzw. für die „Schlechtigkeit“) der verwendeten Hash-Funktion.
Wenn man die Funktion hash01 als Hash-Funktion verwendet, dauert das Einfügen eines Objekts und das Suchen eines Schlüssels etwa so lange wie bei einer Liste (hinzu kommt sogar noch je ein Aufruf der Hash-Funktion, der allerdings häufig vernachlässigt werden kann).
Die folgende Funktion hash02 ist schon etwas besser als hash01:
int hash02(String s) {
if(s.charAt(0) % 2 == 0)
return 3; // oder eine andere ungerade Zahl
else
return 4; // oder eine andere gerade Zahl
}
Je nachdem ob das erste Zeichen des Schlüssels (s.charAt(0)) durch eine gerade oder durch eine ungerade Zahl kodiert wird, liefert diese Hash-Funktion den Index 3 oder den Index 4. Alle Objekte werden also in die Liste 3 oder in die Liste 4 eingefügt, die Listen 0 bis 2 und 5 bis 9 bleiben garantiert leer. Hier wieder eine Darstellung der Hash-Tabelle, nachdem alle vierzehn Beispiel-Schlüssel eingefügt wurden:
|
Index |
Elemente in den Listen |
0
|
|
1
|
|
2
|
|
3
|
Babsy Benno Bine Franz
|
4
|
Ali Alfred Arno Alice Kurt Alex Angy Max Susi Alf
|
5
|
|
6
|
|
7
|
|
8
|
|
9
|
|
Tabelle 4.8: Zweiwertige Hash-Funktion
Die Anzahl der Suchschritte mit hash02 ist insgesamt 65. Hieran kann man erkennen, dass die Funktion hash02 deutlich besser als hash01 ist.
Hier eine noch bessere Hash-Funktion:
int hash03(String s) {
return s.charAt(0) % LAENGE_DER_HASHTAB;
}
Hier wird der Index aus dem ersten Zeichen des Schlüssels berechnet. Die Operation % LAENGE_DER_HASHTAB stellt sicher, dass wir immer einen gültigen Index der Hash-Tabelle bekommen. Hier wieder eine Darstellung der gefüllten Hash-Tabelle:
|
Index |
Elemente in den Listen |
0
|
Franz |
1
|
|
2
|
|
3
|
Susi |
4
|
|
5
|
Ali Alfred Arno Alice Kurt Alex Angy Alf |
6
|
Babsy Benno Bine |
7
|
Max |
8
|
|
9
|
|
Tabelle 4.9: Alphabetische Hash-Funktion
Die Anzahl der Suchschritte mit hash03 ist insgesamt 45. Man sieht: Die Funktion hash03 bewirkt, dass alle Schlüssel mit gleichem Anfangsbuchstaben in dieselbe Liste kommen. Allerdings können in einer Liste auch Schlüssel mit verschiedenen Anfangsbuchstaben stehen (weil z.B. 'A' % 10 gleich 'K' % 10 gleich 5 ist).
Aufgabe: Die Funktion hash03 bewirkt, dass alle mit 'A' und alle mit 'K' beginnenden Schlüssel in die Liste 5 kommen. Nennen Sie einen weiteren Anfangsbuchstaben, der von hash03 der Liste 5 zugeordnet wird.
Für ein genaueres Verständnis von Hash-Funktionen besonders wichtig ist die folgende Tatsache: Ob die Funktion hash03 besonders gut oder schlecht oder mittelmäßig ist, kann man nicht allein anhand der Funktion selbst entscheiden. Vielmehr muß man auch die Schlüssel berücksichtigen, auf die man sie anwendet. Für die vierzehn Beispiel-Schlüssel ist hash03 nicht besonders gut, denn sie läßt 5 der 10 Listen unserer Hash-Tabelle leer und bewirkt, dass acht der vierzehn Schlüssel in dieselbe Liste (Liste 5) eingefügt werden. Am besten ist es, wenn eine Hash-Funktion alle Schlüssel möglichst gleichmäßig auf alle Listen verteilt.
Aufgabe: Geben Sie vierzehn Schlüssel (möglichst allgemein bekannte Vornamen) an, die von der Hash-Funktion hash03 möglichst gleichmäßig auf die zehn Listen der Hash-Tabelle verteilt werden (dabei heißt „möglichst gleichmäßig“: pro Liste ein oder zwei Schlüssel).
Die folgende Funktion hash04 ist für die 14 Beispiel-Schlüssel besser als hash03:
int hash04(String s) { // Der Index wird aus drei Zeichen von s berechnet
// (dem ersten und dem letzten Zeichen und einem Zeichen aus der Mitte):
int vorn = s.charAt[0] % 3;
int mitte = s.charAt[s.size()/2] % 5;
int hinten = s.charAt[s.size()-1] % 7;
return (vorn + mitte + hinten) % LAENGE_DER_HASHTAB;
}
Hier die mit Hilfe der Funktion hash04 gefüllte Hash-Tab:
|
Index |
Elemente in den Listen |
0
|
|
1
|
|
2
|
Susi |
3
|
Bine |
4
|
Alex |
5
|
Ali Babsy Alice Max |
6
|
Benno Franz |
7
|
Angy |
8
|
Alfred Arno Kurt |
9
|
Alf |
Tabelle 4.10: Hash-Funktion aus drei Zeichen
Suchschritte insgesamt mit hash04: 24. Man sieht: hier sind nur noch zwei der zehn Listen leer und die längsten Listen enthalten drei Schlüssel. Die folgende Hash-Funktion ist für die vierzehn Beispiel-Schlüssel noch etwas besser:
int hash05(String s) {
// Der Index wird aus allen Zeichen von s nach einer mittelkomplizierten Formel berechnet:
int i = 0;
for (int j=0; j<s.size(); j++)
i += s[j] % 32 + j;
return i % LAENGE_DER_HASHTAB;
}
Die Funktion hash05 verteilt die vierzehn Beispiel-Schlüssel wie folgt auf die zehn Listen unserer Hash-Tabelle:
|
Index |
Elemente in den Listen |
0
|
Alice Benno |
1
|
Alfred Max |
2
|
Alf |
3
|
Angy |
4
|
Arno Susi |
5
|
Ali Franz |
6
|
Kurt Bine |
7
|
|
8
|
Alex |
9
|
Babsy |
Tabelle 4.11: Hash-Funktion nach Formel
Suchschritte insgesamt mit hashFunk05: 19. Das ist schon nahe am Optimum: Nur noch eine Liste ist leer geblieben und keine Liste enthält mehr als zwei Schlüssel.
In Zusammenhang mit Hash-Tabellen können noch folgende Überlegungen getroffen werden:
Indem man eine Hash-Tabelle verlängert (d.h. die Anzahl der Listen erhöht) kann man häufig die Länge der einzelnen Listen günstig beeinflussen ("tradeoff between space and time").
Bei einer guten Hash-Tabelle (d.h. bei einer Hash-Tabelle mit einer guten Hash-Funktion) ist die Zeit für das Suchen eines Schlüssels fast eine Konstante und nur sehr schwach abhängig von der Größe der Tabelle (d.h. von der Länge der Hash-Tabelle und von der Anzahl der eingetragenen Objekte).
Hash-Funktionen werden in der Praxis typischerweise von Spezialisten entwickelt, die fundierte Kenntnis in Statistik haben.
Je mehr man über die Schlüssel weiss, die in die Hash-Tabelle eingefügt werden sollen, desto besser kann man die Hash-Funktion konstruieren.
Eine typische Anwendung: Viele Compiler verwenden eine Hash-Tabelle, um die vom Programmierer erfundenen Bezeichner (und das, wofür diese Bezeichner stehen) zu speichern.