Hashtabelle

In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Als Indexstruktur werden Hashtabellen verwendet, um Datenelemente in einer großen Datenmenge aufzufinden. Anders als alternative Index-Datenstrukturen wie beispielsweise Baumstrukturen (wie etwa ein B+-Baum) und die Skip-List, zeichnen sich Hashtabellen durch einen üblicherweise konstanten Zeitaufwand bei Einfüge- bzw. Entfernen-Operationen aus. Beim Einsatz einer Hashtabelle zur Suche in Datenmengen spricht man auch von einem Hashverfahren oder Streuspeicherverfahren.

Hashverfahren

Das Hashverfahren ist ein Algorithmus zum Suchen von Datenobjekten in großen Datenmengen. Es basiert auf der Idee, dass eine mathematische Funktion die Position eines Objektes in einer Tabelle berechnet. Dadurch erübrigt sich das Durchsuchen vieler Datenobjekte, bis das Zielobjekt gefunden wurde.

Der Algorithmus

Beim Hashverfahren werden die Zieldaten in einer Hashtabelle gespeichert. Eine Hashfunktion berechnet zu jedem Datenobjekt einen Hashwert, der als Index in der Tabelle verwendet wird. Zum Berechnen dieses Hashwertes wird ein Schlüssel benötigt, der dieses Objekt eindeutig identifiziert. Dieser Schlüssel wird von der Hashfunktion zum Berechnen des Hashwertes verwendet. Das Datenobjekt wird an einer durch den Hashwert festgelegten Stelle (englisch Bucket) in der Tabelle gespeichert. Im Idealfall bekommt jedes Objekt einen eigenen Bucket. Hashfunktionen müssen jedoch nicht eindeutig sein, so dass zwei verschiedene Objekte denselben Hashwert haben können. Diesen Fall nennt man Kollision. Eine Kollision benötigt eine spezielle Behandlung durch das Verfahren.

Bei einer Suche in der Hashtabelle wird nun ähnlich vorgegangen. Zunächst wird aus einem Suchschlüssel wieder ein Hashwert berechnet, der den Bucket des gesuchten Datenobjektes bestimmt. Falls es zu einer Kollision gekommen ist, muss jetzt nur noch durch direkten Vergleich des Suchschlüssels mit den Objekten das gesuchte Ziel bestimmt werden.

In der Praxis wird die Tabelle als ein Array implementiert. Zur Behandlung von Kollisionen werden kollidierte Daten nach einer Ausweichstrategie in anderen alternativen Feldern oder in einer Liste gespeichert. Schlimmstenfalls können Kollisionen zu einer Entartung der Hashtabelle führen, wenn wenige Hashwerte sehr vielen Objekten zugewiesen wurden, während andere Hashwerte unbenutzt bleiben.

Kollisionen

Da Hash-Funktionen im Allgemeinen nicht injektiv sind, können zwei unterschiedliche Schlüssel zum selben Hash-Wert, also zum selben Feld in der Tabelle führen. Dieses Ereignis wird als Kollision bezeichnet. In diesem Fall muss die Hashtabelle mehrere Werte an derselben Stelle aufnehmen. Um dieses Problem zu handhaben, gibt es diverse Kollisionsauflösungsstrategien.

Eine Möglichkeit wird geschlossenes Hashing mit offener Adressierung genannt. Wenn dabei ein Eintrag an eine schon belegte Stelle in der Tabelle abgelegt werden soll, wird stattdessen eine andere freie Stelle genommen. Es wird häufig zwischen drei Varianten unterschieden:

lineares Sondieren: es wird um ein konstantes Intervall verschoben nach einer freien Stelle gesucht. Meistens wird die Intervallgröße auf 1 festgelegt.
quadratisches Sondieren: Nach jedem erfolglosen Suchschritt wird das Intervall quadriert.
doppeltes Hashen: eine weitere Hash-Funktion liefert das Intervall.

Eine weitere Möglichkeit ist offenes Hashing mit geschlossener Adressierung. Anstelle der gesuchten Daten enthält die Hashtabelle hier Behälter (englisch Buckets), die alle Daten mit gleichem Hash-Wert aufnehmen. Bei einer Suche wird also zunächst der richtige Zielbehälter berechnet. Damit wird die Menge der möglichen Ziele erheblich eingeschränkt. Dennoch müssen abschließend die verbliebenen Elemente im Behälter durchsucht werden. Im schlimmsten Fall kann es passieren, dass alle Elemente gleiche Hash-Werte haben und damit im selben Bucket abgelegt werden. In der Praxis kann das aber durch die Wahl einer geeigneten Größe für die Hashtabelle sowie einer geeigneten Hash-Funktion vermieden werden. Oft wird die Verkettung durch eine lineare Liste pro Behälter realisiert.

Vorteile

Je nach Anwendungsfall hat die Verwendung einer Hashtabelle Vorteile sowohl in der Zugriffszeit (gegenüber anderen Baumindexstrukturen) als auch im benötigten Speicherplatz (gegenüber gewöhnlichen Arrays).

Idealerweise sollte die Hashfunktion für die zu speichernden Daten so gewählt sein, dass die Anzahl der Kollisionen minimiert wird und unter einer Konstante bleibt. Trifft dies zu, dann benötigt eine Hashtabelle mit gespeicherten Elementen per Zugriff auf einen Hashtabellen-Eintrag im Mittel nur konstanten Zeitaufwand ( O(1) ). Je nach Hashfunktion muss die Hashtabelle zusätzliche ungenutzte Felder enthalten (in der Praxis üblicherweise 20 bis 30 Prozent), damit die Anzahl der Kollisionen beschränkt werden kann.

Im Vergleich dazu ist der Zugriff auf ein Element in einem B-Baum in der Größenordnung von $O(\log n)$ . Die komplette Baum-Datenstruktur benötigt Speicher in der Größenordnung von O(n) .

Nachteile

Als Füllgrad wird die Anzahl der gespeicherten Elemente geteilt durch die Anzahl aller Buckets bezeichnet (Füllgrad = Anzahl/Buckets). Mit steigendem Füllgrad wächst die Wahrscheinlichkeit einer Kollision und die Entartung nimmt zu. Dann kann nur eine Vergrößerung der Tabelle mit nachfolgender Restrukturierung wieder zu akzeptablem Laufzeitverhalten führen.

Außerdem ist eine der Suchoperation nachfolgende Nachbarschaftssuche unmöglich, da jede Ordnungsbeziehung, die zwischen den Schlüsseln bestehen könnte, verworfen wird (s.a. Abschnitt #Einsatz in Datenbanken).

Komplexität

Wurden Hash-Funktion und Größe der Hashtabelle geeignet gewählt, ist der Aufwand für die Suche in der Tabelle (englisch Look-Up) O(1). Wegen der möglichen Kollisionen hat eine Hashtabelle allerdings im so genannten Worst-Case ein sehr viel schlechteres Verhalten. Dieser wird mit O(n) abgeschätzt, wobei das n der Anzahl der in der Hashtabelle gespeicherten Einträge entspricht. Es werden dabei also alle Einträge in der Tabelle durchsucht.

Varianten des Hashverfahrens

Es gibt mehrere Varianten des Hashverfahrens, die sich für bestimmte Daten besser eignen. Ein wichtiger Faktor hierbei ist die Dynamik, mit der sich die Anzahl der Elemente ändert. Das offene Hashing löst dieses Problem, nimmt aber Einbußen bei den Zugriffszeiten in Kauf. Das geschlossene Hashing ist hingegen auf explizite Strategien zur Kollisionsbehandlung angewiesen.
Vorsicht: Die Bezeichnungen offenes bzw. geschlossenes Hashing werden auch in genau umgekehrter Bedeutung verwendet.

Hashing mit Verkettung

Beim Hashing mit Verkettung (englisch separate chaining) ist die Hash-Tabelle so strukturiert, dass jeder Behälter eine dynamische Datenstruktur aufnehmen kann – beispielsweise eine Liste oder einen Baum. Jeder Schlüssel wird dann in dieser Datenstruktur eingetragen oder gesucht. So ist es problemlos möglich, mehrere Schlüssel in einem Behälter abzulegen, was allerdings zu mehr oder weniger verlängerten Zugriffszeiten führt. Die Effizienz des Zugriffs wird dabei davon bestimmt, wie schnell Datensätze in die gewählte Datenstruktur eingefügt und darin wiedergefunden werden können. Hashing mit Verkettung ist bei Datenbanken eine sehr gängige Indizierungsvariante, wobei sehr große Datenmengen mittels Hashtabellen indiziert werden. Die Größe der Buckets ist in Datenbanksystemen ein Vielfaches der Sektorengröße des Speichermediums. Der Grund dafür ist, dass die Datenmenge nicht mehr im Hauptspeicher gehalten werden kann. Bei einer Suchanfrage muss das Datenbanksystem die Buckets sektorenweise einlesen.

Hashing mit offener Adressierung

Dieses Verfahren wird abgekürzt auch offenes Hashing oder geschlossenes Hashing genannt. Der Name offenes Hashing bezieht sich auf die offene Adressierung, während der Name geschlossenes Hashing sich auf die begrenzte Anzahl möglicher Schlüssel im Behälter bezieht.

Beim Hashing mit offener Adressierung kann jedem Behälter nur eine feste Anzahl von Schlüsseln zugewiesen werden. Häufig wählt man einfach einen einzigen möglichen Schlüssel pro Behälter. Im Kollisionsfall muss dann nach einem alternativen Behälter gesucht werden. Dabei geht man so vor, dass man für m Behälter eine ganze Folge von m Hash-Funktionen definiert. Führt die Anwendung der ersten Hash-Funktion, nennen wir sie h₁, zu einer Kollision, so wendet man h₂ an. Führt diese ebenfalls zu einer Kollision (d.h. der entsprechende Behälter ist bereits belegt), so wendet man h₃ an, und so weiter, bis h_m bzw. bis ein leerer Behälter gefunden wird. Die Bezeichnung „offene Adressierung“ ergibt sich aus der Eigenschaft, dass durch Kollisionen gleiche Schlüssel unterschiedliche Adressen zugewiesen bekommen können.

Kuckucks-Hashing

Kuckucks-Hashing ist ein weiteres Verfahren, Kollisionen in einer Tabelle zu vermeiden. Der Name leitet sich vom Verhalten des Kuckucks ab, Eier aus einem Nest zu entfernen, um ein eigenes Ei hineinzulegen.

Das Prinzip ist, zwei Hash-Funktionen einzusetzen. Das ergibt zwei mögliche Speicherorte in einer Hashtabelle, was immer eine konstante Zugriffszeit garantiert. Ein neuer Schlüssel wird an einem der zwei möglichen Orte gespeichert. Sollte die erste Zielposition besetzt sein, wird der bereits vorhandene Schlüssel auf seine alternative Position versetzt und an seiner Stelle der neue Schlüssel gespeichert. Sollte die alternative Position besetzt sein, so wird wiederum der Schlüssel auf dieser Position auf seine alternative Position transferiert, und so fort. Wenn diese Prozedur zu einer unendlichen Schleife führt (üblicherweise bricht man nach $\log n$ Schritten ab), wird die Hashtabelle mit zwei neuen Hash-Funktionen neu aufgebaut. Die Wahrscheinlichkeit für ein solches Rehashing liegt in der Größenordnung von O(1/n) für jedes Einfügen.

Algorithmen

Lineares Sondieren

Die einfachste Möglichkeit zur Definition einer solchen Folge besteht darin, so lange den jeweils nächsten Behälter zu prüfen, bis man auf einen freien Behälter trifft. Die Definition der Folge von Hash-Funktionen sieht dann so aus:

$h_i(x) = (h(x) + i) \; \bmod~m$

Die Anwendung des Modulo hat mit der begrenzten Zahl von Behältern zu tun: Wurde der letzte Behälter geprüft, so beginnt man wieder beim ersten Behälter. Das Problem dieser Methode ist, dass sich so schnell Ketten oder Cluster bilden und die Zugriffszeiten im Bereich solcher Ketten schnell ansteigen. Das lineare Sondieren ist daher wenig effizient. Sein Vorteil ist jedoch, dass – im Gegensatz zu anderen Sondierungsverfahren – alle Behälter der Tabelle benutzt werden.

Quadratisches Sondieren

Wie beim linearen Sondieren wird nach einem neuen freien Speicher gesucht, allerdings nicht sequenziell, sondern mit stetig quadratisch wachsendem Abstand zur ursprünglichen Position und in beide Richtungen. Verursacht h(k) eine Kollision, so werden nacheinander h(k) + 1 , h(k) - 1 , h(k) + 4 , h(k) - 4 , h(k) + 9 usw. probiert. In Formeln ausgedrückt: $h_i(x) = \left(h(x) + (-1)^{i+1} \cdot \left\lceil\frac{i}{2}\right\rceil^2\right) \bmod~m$

Den ständigen Wechsel des Vorzeichens bei dieser Kollisionsstrategie nennt man auch „alternierendes quadratisches Sondieren“ oder „quadratisches Sondieren mit Verfeinerung“. Wählt man die Anzahl der Behälter geschickt (nämlich $m = 4 \cdot j + 3$ , ist Primzahl), so erzeugt jede Sondierungsfolge h_0(x) bis $h_{m-1}(x)$ eine Permutation der Zahlen 0 bis m-1 ; so wird also sichergestellt, dass jeder Behälter getroffen wird.

Quadratisches Sondieren ergibt keine Verbesserung für die Wahrscheinlichkeit eine Sondierung durchführen zu müssen ( h_0(x) = h_0(y) ), kann aber die Wahrscheinlichkeit von Kollisionen während der Sondierung ( h_0(x) = h_k(y) ) herabsetzen, d.h. Clusterbildung wird vermieden.

Doppel-Hashing

Beim Doppel-Hashing werden zwei unabhängige Hash-Funktionen und angewandt. Diese heißen unabhängig, wenn die Wahrscheinlichkeit für eine sogenannte Doppelkollision, d.h. $h(x)=h(y)\land h'(x)=h'(y)$ gleich 1/m^2 und damit minimal ist. Die Folge von Hash-Funktionen, die nun mittels und gebildet werden, sieht so aus:

$h_i(x) = (h(x)+h'(x)\cdot i) ~ \bmod ~ m$

Die Kosten für diese Methode sind nahe den Kosten für ein ideales Hashing.

Brent-Hashing

Beim Brent-Hashing wird geprüft, ob der Platz, an dem das Element eingefügt werden soll, frei ist. Ist das der Fall, dann wird das Element dort eingefügt. Ist der Platz jedoch belegt, dann wird anhand des gerade berechneten Platzes jeweils für das einzufügende Element und für das Element, das schon an dem Platz ist, ein neuer Platz in der Tabelle berechnet. Sind die beiden neu berechneten Plätze auch belegt, wiederholt sich die Prozedur für den neu berechneten belegten Platz des einzufügenden Elementes. Wird jedoch für das einzufügende Element ein Platz berechnet, der frei ist, wird das Element dort eingefügt. Ist der Platz jedoch belegt und der berechnete Platz frei für das Element, das im vorherigen Durchlauf den Platz für das einzufügende Element belegt hat, dann werden die beiden Plätze der Elemente vertauscht und damit konnte das einzufügende Element in der Tabelle untergebracht werden.

Dynamisches Hashing

Bei steigendem Füllgrad der Tabelle steigt die Wahrscheinlichkeit von Kollisionen deutlich an. Spätestens wenn die Anzahl der indizierten Datensätze größer ist, als die Kapazität der Tabelle, werden Kollisionen unvermeidbar. Das bedeutet, dass das Verfahren einen zunehmenden Aufwand zur Kollisionslösung aufwenden muss. Um dies zu vermeiden, wird beim Dynamischen Hashing die Hashtabelle bei Bedarf vergrößert. Dies hat jedoch zwangsläufig Auswirkungen auf den Wertebereich der Hash-Funktion, der nun ebenfalls erweitert werden muss. Eine Änderung der Hash-Funktion wiederum hat jedoch den nachteiligen Effekt, dass sich ebenfalls die Hash-Werte für bereits gespeicherte Daten ändern. Für das dynamische Hashing wurde dafür eigens eine Klasse von Hash-Funktionen entwickelt, deren Wertebereich vergrößert werden kann, ohne die bereits gespeicherten Hash-Werte zu verändern.

Vorteile

Es gibt keine obere Grenze für das Datenvolumen
Einträge können ohne Probleme gelöscht werden
Adresskollisionen führen nicht zur Clusterbildung.

Nachteile

Falls nicht eine ordnungserhaltende Hashfunktion zum Einsatz kam:

kein effizientes Durchlaufen der Einträge nach einer Ordnung
keine effiziente Suche nach dem Eintrag mit dem kleinsten oder größten Schlüssel

Anwendung

Hashtabellen finden Einsatz in praktisch jeder modernen Applikation, etwa zur Implementierung von Mengen (Sets) oder Caches. Ein typischer Anwendungsfall sind daneben sogenannte assoziative Arrays (auch bekannt als Map, Lookup Table, Dictionary oder Wörterbuch). Das Nachschlagen der mit einem Schlüssel assoziierten Daten kann mittels einer Hashtabelle schnell und elegant implementiert werden. Symboltabellen, die bei Compilern oder Interpretern Verwendung finden, werden meistens ebenfalls als Hashtabelle realisiert.

Wichtig sind Hashtabellen auch für Datenbanken zur Indizierung von Tabellen. Ein sogenannter Hashindex kann unter günstigen Bedingungen zu idealen Zugriffszeiten führen.

Einsatz in Datenbanken

Hashtabellen ermöglichen so eine sehr schnelle Suche in großen Datenmengen, da mit der Berechnung des Hashwertes in einem einzigen Schritt die Anzahl der möglichen Zielobjekte eingeschränkt wird. Damit gehören Hashtabellen zu den effizientesten Indexstrukturen. Ein großer Nachteil ist jedoch die Gefahr der Entartung durch Kollisionen, die bei einem stetigen Wachstum der Datenmenge unausweichlich sind (wenn die Tabelle nicht vergrößert und jedes darin enthaltene Element neu gehasht wird). Siehe dazu Kollision. Daher, wegen ungünstiger IO-Zugriffsmuster, wenn die Hashtabelle auf einem Datenträger gespeichert ist und der fehlenden Möglichkeit Intervalle gemäß einer Ordnungsrelation effizient zu iterieren, muss der Einsatz von Datenbanksystemen gegenüber alternativen Indexdatenstrukturen, wie z.B. B+-Bäumen, abgewogen werden.

Die meisten Hashfunktionen erlauben nicht die Bewegung zum nächsten oder vorherigen Datensatz gemäß einer Ordnungsrelation, da sie gezielt die Daten „mischen“, um sie gleichmäßig im Werteraum zu verteilen. Nur spezielle „ordnungserhaltende“ Hashfunktionen erlauben eine derartige Iteration gemäß ihrer Ordnungsrelation und damit die Abfrage mit Ungleichheitsverknüpfungen („größer als“, „kleiner als“) oder den sortierten Zugriff auf alle Werte. Um solche Verfahren effizient einsetzen zu können, ist meist eine vorherige Analyse der Datenverteilung notwendig. Sie finden daher meist nur in Datenbanksystemen Anwendung, die eine solche Analyse auch beispielsweise zur Anfrageoptimierung durchführen.

Siehe auch

B+-Baum, schnelles und sehr robustes Indexverfahren bei Datenbanken
R-Baum, effektives Indexverfahren für mehrdimensionale Daten

Basierend auf einem Artikel in:

Wikipedia.de