Mit den Baumverfahren haben wir effiziente Datenstrukturen zum Finden von Einträgen mittels Suchschlüsseln betrachtet, die uns einen logarithmischen Aufwand beim Suchen garantieren. Hashverfahren gehen einen ganz anderen Weg: Die Datensätze werden einfach in einem normalen Feld mit direktem Zugriff gespeichert und eine spezielle Funktion, die Hashfunktion, ermöglicht für jeden gespeicherten Wert den direkten Zugriff auf den Datensatz.
Statt einer ausgereiften Datenstruktur benötigen wir nun also eine ausgefeilte Funktion zur Adressberechnung, die fast »magische« Fähigkeiten besitzen muss – sind doch die konkreten abzuspeichernden Werte vorher nicht bekannt, und das Feld sollte natürlich auch nicht beliebig groß werden. Wir werden allerdings sehen, dass uns eine gute Annäherung an eine derartig magische Funktion schon ausreicht, um mit hoher Wahrscheinlichkeit einen direkten Zugriff auf ein einzelnes Element zu ermöglichen.
Grundideen des Hashens
Das Grundprinzip von Hashverfahren lässt sich mit wenigen Aussagen charakterisieren:
Da es in der Regel sehr viel mehr möglicherweise zu speichernde Elemente als die N Positionen im Feld gibt und die zu speichernden Elemente vorher unbekannt sind, kann die Funktion nicht allen möglichen Elementen unterschiedliche Positionen zuweisen. Wird zwei Elementen dieselbe Position zugewiesen, spricht man von einer Kollision. Neben einer möglichst gut streuenden Hashfunktion ist die Behandlung von Kollisionen ein zentrales Merkmal von Hashverfahren.
Man kann sich leicht klar machen, dass bei einem genügend großen Wertevorrat auch immer N Elemente gefunden werden können, die durch h auf dieselbe Position abgebildet werden – ein Hashverfahren kann entarten. Durch eine gute Hashfunktion kann man die Wahrscheinlichkeit einer Entartung verringern, aber nie ganz ausschließen – wohl ein Grund, weshalb viele Programmierer Hashverfahren etwas misstrauisch betrachten und sie trotz ihrer guten Eigenschaften relativ selten einsetzen.
Abbildung 15–1 zeigt ein Beispiel für Hashen. Gespeichert wird in einem Feld von 0 bis 9, die Hashfunktion ist definiert als h(i) = i mod 10. Die Abbildung zeigt das Feld nach dem Einfügen von 42 und 119.
Eintrag |
|
0 |
|
1 |
|
2 |
42 |
3 |
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 |
119 |
Abb. 15–1 Beispiel für eine Hashtabelle
Anhand dieses Beispiels kann man auch gut die Möglichkeit der Kollision erläutern. Die Hashfunktion h(i) würde 69 an dieselbe Stelle wie 119 abspeichern wollen.
Im vorigen Abschnitt hatten wir bereits kurz die Grundideen von Hashverfahren betrachtet. Diese Grundkonzepte sollen nun vertieft werden.
Hashfunktionen
Von zentraler Bedeutung für Hashverfahren sind die Hashfunktionen. Die Hashfunktionen hängen natürlich vom Datentyp der zu speichernden Elemente und der konkreten Anwendung ab (die Mengen von zu speichernden string-Werten können je nach Anwendung sehr unterschiedlich aussehen).
Für Integerwerte als Suchschlüssel wird oft als Hashfunktion direkt die Funktion
h(i) = i mod N
gewählt. Dies funktioniert in der Regel allerdings nur dann gut, wenn N eine (große) Primzahl ist, die nicht nahe an einer großen Zweierpotenz liegt, da sonst unbeabsichtigt besondere algebraische Eigenschaften der eingegebenen Schlüssel eine Gleichverteilung verhindern. Gerade künstlich erzeugte Suchschlüssel haben oft verborgene algebraische Eigenschaften, die nicht auf den ersten Blick zu erkennen sind – man mache sich etwa klar, dass das gerne gewählte N = 2i etwa die Eigenschaft »ungerade« erhält. Werden beispielsweise generierte Artikelnummern durch eine der drei Kontrollziffern 1, 3 oder 7 abgeschlossen, würde ein Hashen mit N = 2i die Werte nur auf ungerade Adressen abbilden.
Für andere Datentypen kann eine Rückführung auf Integerwerte erfolgen:
h(s) = (a0 · s[0] + a1 · s[1] + … + al−1 · s[l − 1]) mod N
Güte von Hashfunktionen
Hashfunktionen sollen die Werte natürlich besonders gut »streuen«. Daher ist es oft sinnvoll, eventuell von Besonderheiten der Eingabewerte abhängige Funktionen zu wählen (Buchstaben des Alphabets tauchen in Namen unterschiedlich häufig auf!). Allerdings müssen Hashfunktionen auf jeden Fall effizient berechenbar sein (konstanter Zeitbedarf, auf keinen Fall abhängig von der Anzahl der gespeicherten Werte!).
Das Matrikelnummer-Beispiel zeigt, dass eine schlecht gewählte Hashfunktion die Güte des Verfahrens schnell negativ beeinflussen kann. Die Hashtabelle besteht hierbei aus 100 Buckets, gespeichert werden sollen Studentendatensätze, identifiziert durch die Matrikelnummer MATRNR. Die 6-stellige MATRNR wird fortlaufend vergeben.
Kollisionen
Eine Kollision tritt ein, wenn ein Datensatz mittels einer Hashfunktion in einem Bucket abgespeichert werden soll, das bereits durch einen anderen Datensatz belegt ist. Kollisionen sind (wenn man von festen Eingabebereichen mit gleich großer Hashtabelle absieht, etwa für Schlüsselwörter einer Programmiersprache) in Hashverfahren unvermeidbar, da die Menge möglicher Elemente größer ist als die Anzahl verfügbarer Positionen.
Zur Behandlung von Kollisionen gibt es mehrere Strategien, von denen wir im Folgenden einige kurz behandeln werden:
Die Wahrscheinlichkeit für Kollisionen nimmt mit dem Füllgrad der Tabelle zu, so dass es in der Regel (in Abhängigkeit von der Kollisionsbehandlungsstrategie) einen Füllgrad gibt, ab dem Hashtabellen ineffizient werden.
Unter einem Überläufer versteht man ein Element, das eine bereits gefüllte Position in einer Hashtabelle zum »Überlaufen« bringt. Bei der Verkettung von Überläufern werden alle (zusätzlichen) Einträge einer Feldposition jeweils in einer verketteten Liste verwaltet.
Verkettung von Überläufern
Die Abbildung 15–2 zeigt das Prinzip der Verkettung von Überläufern anhand einer Tabelle für die Hashfunktion für N = 10 und h(i) = i mod 10.
Abb. 15–2 Hashtabelle mit verketteten Überläufern
Die Verkettung von Überläufern kann zu einer Abspeicherung in einer linearen Liste entarten, wenn alle (oder die Mehrzahl) der Elemente auf dieselbe Position abgebildet werden. Statt einer Liste könnte man daher auch jeweils einen (möglichst ausgeglichenen) Suchbaum aufbauen, um selbst im Falle einer Entartung einen zumindest logarithmischen Aufwand garantieren zu können.
Sondieren zur Positionierung von Überläufern
Die Verkettung von Überläufern benutzt zusätzlichen Speicher, um Kollisionen zu behandeln. Alternativ kann man zur Abspeicherung von Überläufern andere, noch unbesetzte Positionen in der Hashtabelle benutzen. Den Prozess des Suchens einer derartigen Position bezeichnet man als Sondieren.
Lineares Sondieren
Das einfachste Sondierverfahren ist das sogenannte lineare Sondieren. Falls beim linearen Sondieren die Position h(e) in der Hashtabelle T (notiert als T[h(e)]) besetzt ist, prüft das Verfahren des linearen Sondierens nun der Reihe nach die Positionen
T[h(e) + 1], T[h(e) + 2], T[h(e) + 3], …, T[h(e) + i], …
um das Element e abzuspeichern. Natürlich wird genau genommen wieder modulo der Feldgröße gerechnet:
T[(h(e) + 1) mod N], T[(h(e) + 2) mod N], …
Als Ergebnis kann ein Element e nun an einer anderen Stelle als h(e) abgespeichert sein. Dies muss beim Suchen beachtet werden: Ist beim Suchen nach e die Position h(e) durch ein Element e′ mit e ≠ e′ besetzt, muss in der Sondierreihenfolge weitergesucht werden, bis das gesuchte Element oder eine unbesetzte Position gefunden wird.
Die Abbildung 15–3 verdeutlicht den Ablauf beim linearen Sondieren anhand eines einfachen Beispiels, bei dem wieder ein Feld der Größe 10 und die passende Modulofunktion als Hashfunktion genutzt wird. Beim Einfügen des dritten Elementes, der 49, wird eine besetzte Position T[h(49)] = T[9] vorgefunden. Das Sondieren prüft als Nächstes die Position T[(h(49) + 1 mod 10] = T[0], die sich als frei erweist und daher das Element aufnehmen kann.
Abb. 15–3 Lineares Sondieren
Würde nach dem Einfügeablauf in Abbildung 15–3 die Zahl 28 eingefügt werden, müsste nun insgesamt fünfmal sondiert werden, bis ein freier Platz gefunden wird. Eine derartige Folge von aufeinander folgenden besetzten Feldern neigt dazu, immer schneller zu wachsen, da die Wahrscheinlichkeit, dass in diesem Bereich ein weiteres Element eingefügt wird, mit der Größe des Bereiches steigt.
Gebräuchliche Varianten des linearen Sondierens sind die folgenden:
T[h(e) + c], T[h(e) + 2c], T[h(e) + 3c], …
Der Wert c muss natürlich in Abhängigkeit von N gewählt werden, damit möglichst alle Positionen auch abgedeckt werden (also möglichst ggT(c, N) = 1).
T[h(e) + 1], T[h(e) − 1], T[h(e) + 2], T[h(e) − 2], …
Allerdings sind Varianten mit einem c ≠ 1, −1 problematisch, da letztlich die Verteilung für die Länge der Sondierungsfolge gleich zur Verteilung im Fall von c = 1 bleibt, jedoch der Vorteil der Lokalität der Tabellenzugriffe (was wiederum das Caching etwa im CPU-Cache beeinflusst) verloren geht.
Quadratisches Sondieren
Lineares Sondieren neigt zur Bildung von »Klumpen«, in denen alle Positionen bereits besetzt sind und sich daher lange Sondierfolgen aufbauen. Dieses Manko vermeidet das quadratische Sondieren, indem die Folge der Quadratzahlen für die Sondierabstände genommen wird (hier erklärt sich nachträglich der Begriff »lineares Sondieren«, bei dem ein lineares Polynom statt eines quadratischen genutzt wird).
Falls T[h(e)] also bereits besetzt ist, versucht das quadratische Sondieren der Reihe nach mit
T[h(e) + 1], T[h(e) + 4], T[h(e) + 9], …, T[h(e) + i2], …
natürlich wieder modulo der Feldgröße einen freien Platz zu finden.
Die Abbildung 15–4 zeigt – mit derselben Eingabefolge, die in der Abbildung 15–3 für das lineare Sondieren verwendet wurde – die Arbeitsweise des quadratischen Sondierens.
Abb. 15–4 Quadratisches Sondieren
Auch hier ist natürlich die Variante möglich, die in beide Richtungen sondiert:
T[h(e) + 1], T[h(e) − 1], T[h(e) + 4], T[h(e) − 4], …
Im Allgemeinen verhält sich quadratisches Sondieren besser als lineares Sondieren. Allerdings ist es anfällig gegenüber falsch gewähltem N, wie das Beispiel N = 16 zeigt (16 mod 16 = 0 = 02, 25 mod 16 = 9 = 32, 36 mod 16 = 4 = 22, 49 mod 16 = 1 = 12, …). Das Sondieren führt hierbei auf bereits benutzte Quadratzahlen zurück! Diesen Effekt kann man durch die Wahl von Primzahlen für N vermeiden. Empfehlenswert ist dabei eine Primzahl N, die modulo 4 den Rest 3 liefert, da die Zahlen der Folge 0, 1, −1, 4, −4, …, ((N−1)/2)2, −((N−1)/2)2 modulo N genau die Menge {0, 1, …, N − 1} durchlaufen und somit die Sondierungsfolge alle Plätze der Hashtabelle erreicht.
Eine weitere Variante nutzt für ein N = 2k die Sondierungsfolge
T[h(e)+1], T[h(e)+3], T[h(e)+6], T[h(e)+10], …, T[h(e)+k(k+1)/2]
die ebenfalls alle Tabellenplätze erreicht und dabei von h(e) + (k −1)k/2 zu h(e) + k (k + 1)/2 durch einfache Addition von k mod N kommt.
Abschließend bleibt zu bemerken, dass auch Sondierverfahren zu einer (quasi-)linearen Abspeicherung der Eingabefolge entarten können, ohne dass man hier wie bei verketteten Überläufern etwa auf Baumverfahren ausweichen könnte.
Den Aufwand beim Hashen zu bestimmen erfordert einige Vorüberlegungen. Die Effizienz einer Hashspeicherung basiert stark auf der Güte der Hashfunktion – werden alle zu speichernden Elemente auf dieselbe Position abgebildet, entartet das Ganze zur Speicherung in einer sequenziellen Liste.
Füllgrad einer Tabelle
Bei einer guten Hashfunktion ist die Wahrscheinlichkeit, dass ein Element e auf die Position j abgebildet wird, für alle j ∊ 0 … N − 1 gleich groß und damit 
. Sind in einer Hashtabelle m Elemente abgespeichert, bezeichnet man den Füllgrad der Tabelle mit α = m/N.
Sehen wir uns zuerst den Aufwand bei geringer Kollisionswahrscheinlichkeit an, indem wir die bisher skizzierten Algorithmen für den Fall ohne Kollision betrachten. Das Suchen erfordert das Berechnen von h(e), für das wir konstanten Aufwand gefordert hatten, und das Lesen der Feldposition. Dies entspricht einem konstanten Aufwand O(1). Dieselbe Argumentation ergibt auch beim Einfügen den Aufwand O(1).
Gerade beim Einsatz von Sondierverfahren kann man allerdings auch beim sofortigen Finden des Elementes nur dann den Aufwand O(1) erreichen, wenn zu löschende Einträge lediglich markiert werden, da tatsächliches Entfernen Lücken in der Sondierungsfolge anderer Positionen reißen könnte. Das alternative »Re-Hashen« der gesamten Tabelle erfordert den Aufwand O(m).
Natürlich können Kollisionen nicht vernachlässigt werden. Praktische Erfahrungen zeigen, dass bei Sondierverfahren bei einem Füllgrad von über 80% das Einfüge-/Suchverhalten schnell dramatisch schlechter wird.
Bei einer Speicherstruktur wie einer Hashtabelle können wir nur mit Wahrscheinlichkeiten argumentieren, da die konkreten Positionen von Elementen ohne Kenntnis der Hashfunktion zufällig und gleichmäßig über das Feld verteilt werden. Wie groß ist nun die Wahrscheinlichkeit einer Kollision?
Diese Wahrscheinlichkeiten basieren natürlich auf dem Füllgrad α – in einer stark gefüllten Tabelle ist die Wahrscheinlichkeit einer Kollision naturgemäß größer als in einer wenig gefüllten, in einer leeren Tabelle ist sie sicher 0 und in einer vollständig gefüllten dann 1.
Nun bestimmt α den Anteil der belegten Buckets an der Gesamtzahl der Buckets, und somit ist die Wahrscheinlichkeit, dass das Bucket h(e) belegt ist, ebenfalls α. Im Fall der Kollision wird mittels Sondierung ein neues Bucket bestimmt, das möglicherweise wiederum belegt ist. Diesen Fall – ein Bucket belegt und das sondierte Bucket auch belegt – können wir mit ungefähr α2 abschätzen, da das neu sondierte Bucket nach derselben Argumentation mit Wahrscheinlichkeit α belegt ist. Wir sagen bewusst »abschätzen«, da natürlich eigentlich für die zweite Position ein neues 
genommen werden müsste, wenn die Sondiervorschrift garantiert ein neues Bucket bestimmt.
Mittlerer Aufwand bei erfolgloser Suche
Wie aufwendig ist nun die (erfolglose) Suche? Wir benötigen auf jeden Fall einen Zugriff, mit Wahrscheinlichkeit α einen zweiten, mit Wahrscheinlichkeit α2 einen dritten etc. Insgesamt ergibt sich die folgende Summenformel:
Mittlerer Aufwand bei erfolgreicher Suche
Die erfolgreiche Suche ist übrigens besser, da bei einer erfolglosen Suche so lange sondiert werden muss, bis ein freier Platz gefunden wird. Für wenig gefüllte Tabellen liegt der Aufwand in der gleichen Größenordnung. Wenn man über alle in der Tabelle gespeicherten Schlüssel mittelt, dann ergibt sich als erwartete mittlere Anzahl von Sondierungen im Erfolgsfall etwa 
. Hierbei wird von der Zufälligkeit in der Hashfunktion ausgegangen und über die eingefügten Schlüssel gemittelt. Für eine genauere Herleitung dieser Ergebnisse verweisen wir auf die Literatur. Dieser Aufwand ist konstant, wenn konstant ist.
Wenn man jetzt aber die Werte von α nahe an 1 betrachtet, merkt man, dass der Faktor 
sich gegen 1 entwickelt und daher keine so große Rolle spielt und es im Wesentlichen auf das 
ankommt. Das liegt nun gar nicht in der gleichen Größenordnung wie 
bei erfolgloser Suche, sondern wächst viel langsamer (aber auch gegen unendlich). Beispielsweise ergibt α = 0.99 für erfolglose Suche 100 Sondierungen, was oft inakzeptabel ist, für erfolgreiche Suche hingegen (im Mittel) ln(100), also etwa 5, ein Wert, der für viele Anwendungen akzeptabel ist.
Für den Aufwand beim (erfolglosen) Suchen von
kann man einige typische Werte betrachten. Bei einer halb gefüllten Tabelle benötigt man im Mittel bereits 
Zugriffe – hier kann man sich die Summenentwicklung leicht selbst verdeutlichen: Einen Zugriff benötigt man auf jeden Fall, in der Hälfte der Fälle ist der Platz belegt und man muss sondieren, beim Sondieren (das in der Hälfte der Fälle eintrat) trifft man wieder in der Hälfte der Fälle auf ein gespeichertes Element, so dass man insgesamt in einem Viertel der Fälle zweimal sondieren muss etc. Eine zu 90% gefüllte Tabelle erfordert bereits im Mittel 
Zugriffe.
Die Umsetzung der Idee von Hashverfahren in konkrete Datenstrukturen umfasst zwei Aufgaben:
Hashfunktion
Datenstruktur
Die Bereitstellung von Hashfunktionen wird in Java bereits durch die Superklasse java.lang.Object unterstützt, die eine Methode int hashCode() definiert. Beim Überschreiben dieser Methode in abgeleiteten Klassen sollten folgende Eigenschaften garantiert werden:
In der Klasse Object liefert die Methode hashCode im Prinzip einen Wert, der von der Speicheradresse des Objektes abgeleitet ist. Allerdings bieten konkrete Klassen wie java.lang.Integer oder java.lang.String eigene Implementierungen, die die oben angegebenen Eigenschaften erfüllen. So berechnet sich beispielsweise der Hashwert h eines Strings s der Länge n wie folgt:
h(s) = s[0] · 31(n−1) + s[1] · 31(n−2) + … + s[n − 1]
Für anwendungsspezifische Klassen lassen sich ebenfalls noch modifizierte Varianten durch Überschreiben dieser Methode angeben.
Auf der Basis der Methode hashCode kann die Indexberechnung für konkrete Objekte erfolgen. Hierzu ist eine geeignete Datenstruktur zu definieren, die im Wesentlichen ein Feld umfasst, in dem die einzelnen Objekte abgespeichert werden. Eine mögliche Schnittstelle ist in Programm 15.1 dargestellt.
interface Hashing {
void add(Object o)
throws HashTableOverflowException;
boolean contains(Object o);
}
Test auf Enthaltensein
Es werden zwei Methoden definiert, die das Einfügen eines Objektes (add) sowie den Test auf Enthaltensein (contains) ermöglichen. Für eine weiter gehende Nutzung dieses Datentyps könnte die Methode add noch so modifiziert werden, dass nicht nur das zu »hashende« Objekt gespeichert wird – d.h. der Schlüssel –, sondern auch weitere Nutzdaten. Entsprechend müsste noch eine Methode get hinzugefügt werden, die die Nutzdaten zu einem Suchschlüssel zurückgibt. Auch das Löschen von Einträgen ist hier nicht dargestellt.
Verkettung der Überläufer
Weiterhin sind in der Datenstruktur mögliche Kollisionen zu behandeln. Betrachten wir zunächst den Ansatz der Verkettung der Überläufer. Für diesen Fall besteht das Feld aus Listen, die die eigentlichen Objekte aufnehmen können (Programm 15.2). Im Konstruktor der Klasse LinkedHashTable wird zunächst ein Feld einer vorgegebenen Größe angelegt. Beim Einfügen eines Objektes wird nun der Hashwert durch Aufruf der jeweiligen Methode hashCode bestimmt. Basierend auf diesem Wert kann im nächsten Schritt der Feldindex idx berechnet werden, indem eine Modulorechnung mit der Feldgröße durchgeführt wird. Die Bitoperation »& 0x7fffffff« sorgt nur dafür, dass der Hashwert als positive Zahl interpretiert wird. Schließlich wird geprüft, ob im Feld an der Position idx bereits eine Liste erzeugt wurde. Ist dies nicht der Fall, so wird ein neues Listenobjekt angelegt und im Feld eingetragen. Danach kann das einzufügende Objekt als letztes Element an die aktuelle Liste angehängt werden.
import java.util.LinkedList;
import java.util.Iterator;
public class LinkedHashTable implements Hashing {
private LinkedList[ ] table; // Feld mit Listen
public LinkedHashTable(int size) {
// Feld aufbauen
table = new LinkedList[size];
}
public void add(Object o) {
// Feldindex über Hashwert bestimmen
int idx = (o.hashCode() & 0x7fffffff) % table.length;
if (table[idx] == null)
// noch keine Liste vorhanden
table[idx] = new LinkedList();
// an Liste anhängen
table[idx].addLast(o);
}
public boolean contains(Object o) {
// Feldindex über Hashwert bestimmen
int idx = (o.hashCode() & 0x7fffffff) % table.length;
if (table[idx] != null) {
// Liste gefunden
Iterator it = table[idx].iterator();
while (it.hasNext()) {
// sequenzielle Suche nach Element
Object obj = it.next();
if (obj.equals(o))
return true;
}
}
return false;
}
}
Das Suchen eines Objektes im Rahmen der Methode contains beginnt mit dem gleichen Prinzip. Auch hierbei wird zunächst der Feldindex bestimmt. Ist an dieser Position noch keine Liste vorhanden, kann die Suche sofort abgebrochen werden. Andernfalls wird die Liste elementweise durchsucht, indem das Suchobjekt mit dem jeweiligen Element unter Verwendung der Methode equals verglichen wird. Hier könnte auch direkt die contains-Methode der Klasse LinkedList genutzt werden, die bereits eine solche sequenzielle Suche implementiert. Entsprechend wäre der Programmabschnitt zur Suche durch den Aufruf
return table[idx].contains(o);
zu ersetzen. Bei beiden Varianten wird im Erfolgsfall der Wert true zurückgeliefert. Wurde dagegen kein entsprechendes Element gefunden, so ist das Ergebnis false.
Lineares Sondieren
Überlauf
Verfolgt man dagegen den Ansatz des linearen Sondierens, so werden die Objekte direkt im Feld gespeichert (Programm 15.3). Allerdings muss hier beim Einfügen geprüft werden, ob eine Kollision besteht, d.h., ob an der berechneten Position bereits ein Objekt gespeichert ist. In diesem Fall wird in der while-Schleife die nächste freie Position gesucht. Da bei diesem Ansatz die Anzahl der freien Plätze erschöpft sein kann, muss außerdem getestet werden, ob bei der Suche das Feld einmal vollständig durchlaufen wurde. In der hier betrachteten Implementierung wird dies als Fehler angesehen und über eine Ausnahme HashTableOverflowException signalisiert. In einer vollständigen Realisierung sollte aber an dieser Stelle das Feld vergrößert werden. Zu beachten ist aber dabei, dass dann auch für alle Objekte eine Neuberechnung der Indexwerte erfolgen muss!
public class HashTable implements Hashing {
private Object[ ] table;
public HashTable(int size) {
table = new Object[size];
}
public void add(Object o)
throws HashTableOverflowException {
int idx, oidx;
oidx = idx = (o.hashCode() & 0x7fffffff) % table.length;
while (table[idx] != null) {
idx = ++idx % table.length;
throw new HashTableOverflowException();
}
table[idx] = o;
}
public boolean contains(Object o) {
int idx, oidx;
oidx = idx = (o.hashCode() & 0x7fffffff) % table.length;
while (table[idx] != null) {
if (o.equals(table[idx]))
return true;
idx = ++idx % table.length;
if (idx == oidx)
break;
}
return false;
}
}
Das Suchen eines Objektes folgt wiederum demselben Prinzip. Ausgehend von der aus dem Hashwert berechneten Position wird geprüft, ob das dort gespeicherte Objekt das gesuchte ist. Sonst muss linear weitergesucht werden, wobei das Abbruchkriterium hier wieder ein vollständiger Durchlauf ist.
In der Java-Klassenbibliothek sind im Paket java.util mehrere weitere Hashbasierte Datenstrukturen vorhanden, so u.a. eine Klasse Hashtable, eine Implementierung für Set sowie für Map (siehe auch Abschnitt 13.6).
Cuckoo- oder Kuckucks-Hashen
Als Abschluss der Basisprinzipien des Hashens betrachten wir eine spezielle Variante, um die Möglichkeiten der Variation der Basisidee exemplarisch aufzuzeigen. Das Cuckoo-Hashing oder auch Kuckucks-Hashen wurde insbesondere im Zusammenhang mit modernen Prozessorarchitekturen untersucht, da es besser moderne Parallelverarbeitung in Prozessoren ausnutzen kann als einige klassische Verfahren.
Verdrängen bei Kollisionen
Cuckoo-Hashing nutzt statt einer Hashfunktion zwei Hashfunktionen. Im Fall einer Kollision bei der Nutzung einer Hashfunktion wird mit einer zweiten Hashfunktion ein alternativer Speicherplatz gesucht. Hierzu wird in der Grundvariante eine zweite Hashtabelle genutzt. Sollte auch dort bereits der Platz belegt sein, kann der existierende Eintrag aus der ersten Tabelle verdrängt und der neue Eintrag gespeichert werden. Der verdrängte Eintrag wird neu eingefügt, jetzt aber in die zweite Tabelle. Dort läuft der Prozess erneut an (mit den Tabellen in vertauschten Rollen). Dieses Verdrängen führte zur Namensgebung: »Ein Kuckuck wirft Eier aus dem fremden Nest, um die eigenen Eier unterzubringen.« Das Verfahren funktioniert auch wenn nur eine Hashtabelle mit zwei Hashfunktionen genutzt wird. Wir präsentieren die Variante mit den zwei Tabellen, da das Prinzip damit deutlicher erklärbar ist.
Das verdrängte Element kann nun wieder ein Element verdrängen und so weiter. Da es sich um unabhängige Hashfunktionen handelt, ist die Wahrscheinlichkeit groß, dass ein verdrängtes Element nicht auf einem Platz der bisherigen Verdrängungskette landet – aber ein derartiger Zyklus kann natürlich entstehen. In solchen Fällen müssen die Tabellen mit neuen Hashfunktionen neu aufgebaut werden.
Beim Cuckoo-Hashing muss bei der exakten Suche also immer genau in zwei Tabellen nachgeschaut werden. Cuckoo-Hashing kann mit einem klassischen Array oder mit Buckets, die mehrere Elemente fassen, realisiert werden.
Wir verdeutlichen Cuckoo-Hashing an einem kleinen Beispiel.
Um das Beispiel übersichtlich zu halten, verwenden wir einfache Hashfunktionen, die jeweils die letzte bzw. vorletzte Dezimalstelle einer Zahl extrahieren, also h1(k) = k mod 10 und h2(k) = (k ÷ 10) mod 10. Gespeichert werden die Zahlen in den zwei Tabellen T1 und T2.
Wir fügen die Zahlen 433, 129 und 555 in die Tabelle T1 ein. Beim Einfügen von 783 ist der Platz in Tabelle T1 belegt, so dass diese Zahl in T2 gespeichert werden muss. Bei einer Suche muss immer in beiden Tabellen nachgeschaut werden, also T1[h1(k)] = k ∨ T2[h2(k)] = k. Wird nun mit 103 eine weitere Zahl eingefügt, die mit 433 unter h1kollidiert, ist dies mit h2 weiterhin möglich. Abbildung 15–5 zeigt die beiden Hashtabellen nach diesen Operationen.
Wenn wir nun die Zahl 889 eingefügen wollen, so sind beide möglichen Positionen belegt. 889 kann aber in T1 die dort stehende Zahl 129 verdrängen, die in T2 an der Position T2[2] gespeichert werden kann. Das Ergebnis zeigt Abbildung 15–6.
Wird nun 789 eingefügt, sind wiederum beide Positionen belegt. Das Verdrängen von 889 aus T1 würde zu einem kaskadierenden Verdrängen führen: 889 würde in T2 dann 783 verdrängen, das wiederum 433 in T1 verdrängen würde. Dies würde funktionieren, da 433 an der Stelle T2[3] Platz hätte. Das Ergebnis zeigt Abbildung 15–7.
Abb. 15–5 Hashtabellen beim Cuckoo-Hashing
Abb. 15–6 Hashtabellen beim Cuckoo-Hashing nach Verdrängen von 129
Kaskadierendes Verdrängen kann nun natürlich auch zu Zyklen führen. Die Wahrscheinlichkeit derartiger Zyklen steigt, wie üblich bei Hashverfahren, mit dem Füllgrad der Tabellen. Im Falle eines Zyklus müssten die Hashfunktionen variiert werden und bei ungünstigem Füllgrad die Tabellen ggf. vergrößert werden.
Cuckoo-Hashing hat im Vergleich zu anderen Verfahren mit Kollisionsbehandlung folgende Vorteile:
Abb. 15–7 Hashtabellen beim Cuckoo-Hashing nach kaskadierendem Verdrängen
Diese Eigenschaften lassen Cuckoo-Hashing für kleine, im Cache moderner Prozessoren gehaltene Datenmengen gegenüber Hashverfahren mit verketteten Überläufern effizienter arbeiten.
Dynamische Bildbereiche
Hashverfahren werfen im praktischen Gebrauch trotz der guten Zeitkomplexität einige Probleme auf. Eines der schwerwiegendsten Probleme ist die mangelnde Dynamik: Der Bildbereich 0… N − 1 ist konstant und ab einem gewissen Füllgrad wird das Antwortverhalten schnell schlechter. Eine Vergrößerung des Bildbereichs erfordert ein komplettes Neu-Hashen in ein neues Feld. Sogenannte dynamische Hashverfahren versuchen diese Probleme zu lösen, indem sie dynamisch wachsende und schrumpfende Bildbereiche unterstützen.
In den meisten Lehrbüchern werden dynamische Hashverfahren als fortgeschrittene Techniken nur erwähnt und nicht im Detail behandelt. In diesem Lehrbuch wurden sie bewusst aufgenommen, da dynamische Hashverfahren zeigen, wie verschiedene der bisher gezeigten Techniken sinnvoll kombiniert werden können:
Dynamische Hashverfahren basieren auf einer Reihe von zu lösenden Problemen, deren Behandlung wir nun der Reihe nach diskutieren werden, bevor wir mit dem erweiterbaren Hashen ein konkretes Verfahren vorstellen werden.
Das erste Problem, das zu lösen ist, ist der Bildbereich der Hashfunktion. Die klassische Hashfunktion ist eine Abbildung auf den Bereich 0… N − 1 für eine Konstante N. Bei dynamischen Hashverfahren muss der Bildbereich wachsen können.
Hashfunktionen mit erweiterbarem Bildbereich
Einige Verfahren schlagen eine Familie von Hashfunktionen vor, die den Bildbereich jeweils vergrößern – in der Regel wird der Bildbereich verdoppelt. Mathematisch fordert man eine Funktionsfamilie (definiert auf dem Bereich der zu speichernden Elemente E)
hi : E → {0, …, 2i · N − 1}
als Folge von Hashfunktionen mit i ∊ {0, 1, 2, …} und N als Anfangsgröße des Hashverzeichnisses. Der Wert von i wird dabei als Level der Hashfunktion bezeichnet.
Um bei einem Übergang von einem Level zum nächsten die gespeicherten Elemente von Buckets nicht komplett umverteilen zu müssen, fordert man für diese Hashfunktionen die folgenden Bedingungen:
Die Elemente, die einem Bucket j durch hi zugeordnet werden, lassen sich durch hi+1 also auf jeweils eines von zwei Buckets verteilen: j oder j + (2i · N).
Diese Bedingungen sehen auf den ersten Blick schwer erfüllbar aus, werden aber beispielsweise erfüllt, wenn hi(w) als w mod (2i · N) gewählt wird.
Für die Implementierung und weitere Optimierung hat sich eine andere Darstellung dieser Familie von Hashfunktionen bewährt, die mathematisch äquivalent, aber oft leichter im Rechner verarbeitbar ist.
Hier wird statt einer Familie von Hashfunktionen genau eine Hashfunktion gewählt. Der Zielbereich dieser Hashfunktionen ist aber das Intervall [0.0 … 1.0), also keine ganzen Zahlen, sondern Gleitpunktzahlen. Auch hier wird eine gleichmäßige Verteilung gefordert. Zur Verarbeitung werden die errechneten Hashwerte im binären Zahlsystem notiert, also beispielsweise:
0.0 |
= |
b0.000000… |
0.5 |
= |
b0.100000… |
0.75 |
= |
b0.110000… |
0.99999… |
= |
b0.111111… |
Die ersten i Bits hinter dem Punkt, als Binärdarstellung ganzer Zahlen interpretiert, adressieren ein Feld der Größe 2i. Durch Hinzunahme eines Bits verdoppelt man den Bildbereich und realisiert dadurch einen dynamisch erweiterbaren Bildbereich.
Zur konkreten Implementierung erweiterbarer Bildbereiche verwendet man üblicherweise eine abgewandelte Darstellung. Die Hashwerte werden als Bitfolgen (potenziell hinreichend lang) dargestellt und beim Level i werden die ersten i Bits als Zahl interpretiert. Die Bits können dabei als Binärzahl in üblicher Schreibweise oder in umgekehrter Reihenfolge interpretiert werden. Das von uns im folgenden Abschnitt beschriebene erweiterbare Hashen nutzt die erste Variante.
Bisher adressierten Hashwerte genau einen Speicherplatz für ein Element. Kollisionen bei Bitfolgen als Hashwerte können nun oft durch ein Verdoppeln des Bildbereichs aufgelöst werden, da ein weiteres Bit hinzugenommen wird. Eine derartige Auflösung gelingt im Mittel natürlich nur in der Hälfte der Fälle, oft entsprechen Kollisionen sogar weitgehend (d.h. für viele Positionen) identischen Bitfolgen.
Block: Bucket für mehrere Werte
In vielen Fällen kann man Kollisionen einfach dadurch behandeln, dass ein Bucket mehr als ein Element aufnehmen kann. Eine Hashfunktion liefert die Adresse eines Blockes, der k Elemente abspeichern kann. Die Zahl k wird beispielsweise in Datenbankanwendungen derart gewählt, dass ein Block einer Transporteinheit zwischen Festplatte und Hauptspeicher entspricht, also beispielsweise 1024 Byte umfasst.
Natürlich können auch Blöcke für k Elemente Überlauf nicht verhindern. Ist im Falle eines Überlaufs die Hashtabelle hinreichend gefüllt, so kommt eine Erweiterung des Bildbereichs (»ein Bit mehr«) in Frage (Elemente eines Blockes können auf zwei Blöcke aufgeteilt werden) – andernfalls muss man (ggf. übergangsweise) Überlauflisten verwalten.
Eine Erweiterung des Bildbereichs würde in unseren bisherigen Verfahren eine Verdopplung der Blöcke bedeuten – nach einer Verdopplung des Speicherbereichs wäre der Speicherplatz dann auch gleich unter 50% ausgenutzt. Verschärft wird diese Problematik, wenn die Daten ungleich verteilt werden.
Dies können wir dadurch beheben, dass der Bildbereich nur dort erweitert wird, wo dies aufgrund der Speicherdichte notwendig erscheint. Als Beispiel könnten mehr Elemente auf den Bereich zwischen 0.0 und 0.5 als zwischen 0.5 und 1.0 abgebildet werden. Dann kann es sinnvoll sein, für Hashwerte, die (als Binärzahl) mit 0.0 beginnen, mehr Bits zur Adressierung zu nutzen als für diejenigen, die mit 0.1 beginnen.
Allerdings ist Vorsicht geboten: Jetzt kann man nicht mehr direkt ein Feld adressieren, da unterschiedlich lange Bitfolgen zur Adressierung genommen werden (Adressierung über 11 und 011 liefert ansonsten in beiden Fällen den 3. Block!).
Mit unterschiedlich langen Bitfolgen kann man ein Feld nicht mehr direkt adressieren. Allerdings wissen wir bereits, dass unterschiedlich lange Bitsequenzen effizient über einen Trie verwaltet werden können. Für die Effizienz kommt uns dabei zugute, dass bei einer geeigneten Hashfunktion ein derartiger Trie ziemlich ausgeglichen sein dürfte.
Tries als Bäume sind weniger effizient als der Direktzugriff über ein Feld, so dass wir mit der vierten Idee eigentlich einen erheblichen Effizienzverlust erzeugt haben. Allerdings hilft uns, dass der Trie bei einer geeigneten Hashfunktion so gut wie ausgeglichen sein sollte. Einen ausgeglichenen Trie können wir wiederum als ein Feld organisieren, indem die auf einer Stufe stehenden Blätter direkt adressiert werden. Der Trick besteht nun darin, den tatsächlichen Trie auf einen vollständig ausgeglichenen Trie aufzufüllen und diesen effizient mittels eines Feldes zu speichern, dessen Einträge Zeiger auf Blöcke sind.
Binärer Trie als Feld gespeichert
Als Suchstruktur wird also statt eines allgemeinen binären Präfixbaumes ein ausgeglichener binärer Präfixbaum genommen, der als Feld mit fester Größe 2d realisiert wird. Der Wert d wird dabei als Tiefe des Baumes bezeichnet. In Teilen des (ja eigentlich nicht ganz ausgeglichenen) tatsächlichen Tries, in dem die Tiefe nicht erreicht wird, zeigen mehrere Blätter des vervollständigten Tries auf denselben Block.
Ein Verfahren, das die genannten Ideen umsetzt, ist das sogenannte erweiterbare Hashen (engl. extensible hashing). Die Abbildung 15–8 zeigt die Realisierung eines ausgeglichenen Tries mit der Tiefe d = 2 und einer Blockgröße von 2.
Abb. 15–8 Erweiterbares Hashen: Beispiel der Tiefe d = 2
Verdopplung des Indexfeldes
Die Hashtabelle ist im Beispiel zu 100% gefüllt. Ein weiterer Eintrag würde einen Block zum Überlaufen bringen und eine Verdopplung des Indexfeldes erfordern. Würde im Beispiel ein weiterer Wert mit dem Hashwert 00111111 eingefügt werden, müsste der Block mit der Adresse 00 gesplittet werden.
Da der Index ein ausgeglichener Trie ist, muss hierfür die Tiefe um eins erhöht werden. Das Indexfeld verdoppelt damit seine Größe.
Um nun zu vermeiden, dass auch die Anzahl der Blöcke verdoppelt wird, können Blätter des Baumes gemeinsam auf denselben Block zeigen. Beim Verdoppeln des Indexfeldes geht man nun zuerst wie folgt vor: Ist einem Blatt x vor dem Verdoppeln das Bucket s zugeordnet, zeigen nach dem Verdoppeln die beiden Söhne von x, also x0 und x1, ebenfalls beide auf s.
Die Abbildung 15–9 zeigt das derart verdoppelte Indexfeld. Man beachte, dass die Blöcke an sich nicht verändert wurden; es erfolgte kein Re-Hashen.
Abb. 15–9 Erweiterbares Hashen mit verdoppelter Feldgröße
Nun kann der Block, der vorher nur mit 00 adressiert war, aufgeteilt werden, da er ja nun sowohl mit 000 als auch mit 001 adressiert wird. Die Hashtabelle nach Einfügen von 00111111 zeigt die Abbildung 15–10.
Wir verzichten an dieser Stelle auf eine weiter gehende Diskussion des erweiterbaren Hashens und nennen stattdessen nur einige der Eigenschaften dieses Verfahrens:
Abb. 15–10 Aufteilen eines Blockes beim erweiterbaren Hashen
Zyklisches Verhalten beim Einfügen
Eine weitere Verbesserung kann das Problem des zyklischen Verhaltens beim Einfügen beheben. Kurz vor dem Erhöhen der Tiefe ist bei tatsächlicher Gleichverteilung der Hashwerte die Speicherauslastung am besten, so dass die Wahrscheinlichkeit, dass ein Einfügen die Aufteilung eines Blockes bedeutet, am größten ist. Zu diesem Zeitpunkt ist im Mittel das Einfügen mit größerem Aufwand verbunden – bei gleichmäßigem Wachstum der Speicherstruktur verschlechtert bzw. verbessert sich der Aufwand beim Einfügen also zyklisch. Das zyklische Verhalten kann durch Umverteilen mittels der neuen Hashfunktion 2h(k) − 1 gemildert werden. Die Tabelle 15–1 zeigt den Effekt dieser Umverteilung mittels der Exponentialfunktion verteilt.
In den folgenden Programmausschnitten soll nun die konkrete Umsetzung der diskutierten Techniken des dynamischen Hashens am Beispiel der vorgestellten Variante des erweiterbaren Hashens gezeigt werden. Die Umsetzung erfolgt direkt in Java, da der Schwerpunkt der Realisierung eher im Bereich der Datenstrukturen und nicht in den Algorithmen liegt.
Die Basisstrukturen für die Realisierung der Klasse ExtendibleHashing sind die Blöcke (Klasse Block) sowie der Trie, der einfach als Indexfeld hashIndex mit Blöcken als Elementen implementiert ist (Programm 15.4). Die Blöcke sind als Objekte modelliert, da mehrere Indexeinträge auf denselben Block zeigen können. Zur Vereinfachung haben wir einen Block als Vektor (Klasse java.util.ArrayList) fester Maximallänge realisiert. Einer unserer Blöcke kann also maximal 5 Objekte speichern. Weiterhin wird eine Hashfunktion hashValueToBitSet benötigt, die einen Bitvektor der passenden Tiefe aus dem Hashwert erzeugt. Diese Hashfunktion nutzt einfach die Java-Methode hashCode und baut aus der rückwärts interpretierten Bitrepräsentation des damit berechneten Hashwertes den Bitvektor auf. Dies ist natürlich nur eine primitive Variante, die keine Gleichverteilung garantiert. Für den realen Einsatz sollte hier eine wie in Abschnitt 15.3.2 skizzierte Hashfunktion zum Einsatz kommen.
Tab. 15–1 Umverteilung von Hashwerten mit Exponentialfunktion
n |
2n − 1 |
0.0 |
0.0 |
0.1 |
0.0717735 |
0.2 |
0.1486984 |
0.3 |
0.2311444 |
0.4 |
0.3195079 |
0.5 |
0.4142136 |
0.6 |
0.5157166 |
0.7 |
0.6245048 |
0.8 |
0.7411011 |
0.9 |
0.866066 |
1.0 |
1.0 |
Die Methode getPosition benötigt man zum Suchen, Einfügen und Löschen von Objekten, indem über den Bitvektor und die aktuelle Tiefe der zum Zugriff auf das Indexfeld erforderliche Wert aus dem Hashwert eines Objektes ermittelt wird. Der richtige Block wird durch die Hashfunktion eindeutig bestimmt, auch wenn der Trie nicht vollständig aufgebaut ist.
public class ExtendibleHashing implements Hashing {
final static int MAXSIZE = 5;
static class Block {
ArrayList elems = new ArrayList();
int bdepth;
public Block(int d) { bdepth = d; }
public ArrayList elements() { return elems; }
public int getDepth() { return bdepth; }
}
private int depth;
private Block hashIndex[] = null;
private BitSet hashValueToBitSet(Object o) {
BitSet bits = new BitSet(32);
int h = o.hashCode();
for (int i = 0; i < 32; i++)
bits.set(i, (h & (1 << i)) != 0);
return bits;
}
private int getPosition(Object o, int d) {
BitSet bits = hashValueToBitSet(o);
int pos = 0;
for (int i = 0; i < d; i++) {
pos *= 2;
if (bits.get(i)) pos++;
}
return pos;
}
...
}
Die Initialisierung im Rahmen des Konstruktors erzeugt einen Index der Größe 2 mit jeweils einem Block der Tiefe 1, in dem kein Element gespeichert ist (Programm 15.5).
public ExtendibleHashing() {
depth = 1;
hashIndex = new Block[2];
hashIndex[0] = new Block(1);
hashIndex[1] = new Block(1);
}
Die Verdopplung des Indexes erfolgt wie im Schritt von Abbildung 15–9 nach Abbildung 15–10 mithilfe der Methode extendIndex (Programm 15.6). Nach der Verdopplung zeigen jeweils ein gerader Indexeintrag und der darauf folgende ungerade Eintrag auf denselben Block.
private void extendIndex() {
int nsize = 1 << depth;
Block newIndex[] = new Block[nsize * 2];
for (int i = 0; i < nsize; i++) {
newIndex[2 * i] = hashIndex[i];
newIndex[2 * i + 1] = hashIndex[i];
}
hashIndex = newIndex;
depth++;
}
Das Einfügen ist eine komplexere Operation, da der durch getPosition gefundene Block bereits voll sein kann. Er muss dann gesplittet werden, wobei gegebenenfalls sogar eine Verdopplung der Indexgröße notwendig wird. Das Splitten erfolgt in einer Schleife, da ein Erfolg nicht beim ersten Splitten garantiert werden kann.
public void add(Object o) {
int idx = getPosition(o, depth);
Block b = hashIndex[idx];
if (b.elements().contains(o))
return;
while (b.elements().size() == MAXSIZE) {
// solange Block voll ist
if (b.getDepth() == depth) {
extendIndex();
idx = getPosition(o, depth);
}
splitBlock(idx);
b = hashIndex[idx];
}
// Element hinzufügen
b.elements().add(o);
}
Dem aufmerksamen Leser dürfte nicht entgangen sein, dass diese Realisierung die Gefahr einer Endlositeration beinhaltet, wenn nämlich mehr als MAXSIZE Objekte den identischen Hashwert haben. Auch ohne Endlositeration kann der Index sehr groß werden, wenn zu viele Objekte auf dasselbe Bitpräfix abgebildet werden. Als Lösung bietet es sich an, Überlauflisten bei Blöcken zu verwalten und einen Block-Split nur dann durchzuführen, wenn ein global verwalteter Füllgrad einen bestimmten Schwellwert übersteigt. Wir haben auf diese (notwendige!) Verfeinerung verzichtet, um das Beispiel einfacher zu halten.
private void splitBlock(int idx) {
Block b = hashIndex[idx];
Block b0 = new Block(b.getDepth() + 1);
Block b1 = new Block(b.getDepth() + 1);
Iterator it = b.elements().iterator();
while (! it.hasNext()) {
// Elemente neu verteilen
Object elem = it.next();
BitSet bits = hashValueToBitSet(elem);
if (! bits.get(b.getDepth()))
b0.elements().addElement(elem);
else
b1.elements().addElement(elem);
it.remove();
}
int diff = depth - b.getDepth();
int zdiff = 1 << diff; // 2diff Einträge
int start = (idx / zdiff) * zdiff;
for (int i = start; i < start + zdiff; i++) {
if (i < start + (1 << (diff - 1)))
hashIndex[i] = b0;
else
hashIndex[i] = b1;
}
}
Das Splitten eines Blockes erfolgt dadurch, dass zwei neue Blöcke erzeugt werden und die Einträge des alten Blockes in Abhängigkeit vom Bit der Split-Ebene auf diese verteilt werden. Etwas komplexer ist die Adjustierung des hashIndex-Feldes, da je nach der Differenz zwischen globaler Tiefe und lokaler Tiefe des alten Blockes 2, 4 oder mehr Einträge aktualisiert werden müssen.
Einer der Gründe der Aufnahme des erweiterbaren Hashens in dieses Buch ist die Erfahrung, dass Eigenschaften von Datenstrukturen nicht als unumstößlich angesehen werden sollten, um zu vermeiden, dass man geschickte Kombinationsmöglichkeiten der klassischen Verfahren aufgrund derartiger Vorbehalte nicht erkennt.
Das erweiterbare Hashen widerlegt quasi die folgenden »Lehrbuchmeinungen«:
Das erweiterbare Hashen kombiniert die Ideen der drei Ansätze derart, dass die jeweiligen Nachteile wegfallen, aber die Vorteile bewahrt bleiben!
