Hashtabelle

aus Wikipedia, der freien Enzyklopädie

In der Informatik bezeichnet man als Hashtabelle bzw. Streuwerttabelle eine spezielle Indexstruktur zur Abbildung einer Hash-Funktion. Hashtabellen eignen sich also vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen stehen dabei in Konkurrenz zu Baumstrukturen (wie etwa ein B*-Baum) und der Skip-List, die ebenfalls als Indexstruktur dienen können. Beim Einsatz einer Hashtabelle zur Suche in Datenmengen spricht man auch von einem Hashverfahren oder Streuspeicherverfahren.

Inhaltsverzeichnis 1 Hashverfahren 1.1 Kollisionen 1.2 Vorteile 1.3 Nachteile 1.4 Komplexität 2 Varianten des Hashverfahrens 2.1 Hashing mit Verkettung 2.2 Hashing mit offener Adressierung 2.2.1 Lineares Sondieren 2.2.2 Quadratisches Sondieren 2.2.3 Doppel-Hashing 2.3 Dynamisches Hashing 2.3.1 Vorteile 2.3.2 Probleme 3 Anwendung 4 Beispiel 5 Siehe auch 6 Literatur

[Bearbeiten] Hashverfahren

Beim Hashverfahren werden die Zieldaten in einer Tabelle gespeichert. Diese Tabelle wird als die Hashtabelle bezeichnet. Das wesentliche Prinzip des Verfahrens beruht auf dem Einsatz einer Hash-Funktion. Diese Funktion berechnet aus einem Suchschlüssel einen Index auf die Hashtabelle. Dieser Index stellt im Idealfall die genaue Position des gesuchten Elementes in der Tabelle dar. Dieser Idealfall ist nicht immer gegeben. Es besteht die Möglichkeit, daß zwei Datenobjekte den gleichen Hashwert besitzen, also auf die gleiche Position in der Tabelle zeigen. Diesen Fall nennt man Kollision und muss separat behandelt werden.

In der Praxis wird die Tabelle als ein Array implementiert. Wegen der möglichen Kollisionen werden die Daten aber nicht direkt im Array gespeichert, sondern in Behältern (Buckets), die mehrere Datenelemente mit dem gleichen Hash-Wert aufnehmen können. Das Array selbst enthält nur noch einen Verweis auf einen Bucket, der zu diesem Hash-Wert gehört. Um das gesuchte Element zu finden, muss gegebenenfalls eine weitere Suche über die Elemente im Bucket durchgeführt werden. Ist die Hashtabelle ausgewogen, befinden sich nur wenige Datensätze in einem Bucket und der letzte Schritt hat einen geringen Aufwand.

Im Worst-Case können Kollisionen zu einer Entartung der Hashtabelle führen, wenn wenige Buckets sehr viele Datenelemente enthalten, während andere Buckets leer bleiben.

[Bearbeiten] Kollisionen

Da Hash-Funktionen im Allgemeinen nicht ein-eindeutig (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 der selben Stelle aufnehmen. Um dieses Problem zu handhaben, gibt es diverse Kollisionsauflösungsstrategien.

Eine Möglichkeit wird offenes Hashing 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:

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

Eine weitere Möglichkeit ist Kollisionsauflösung durch Verkettung. Anstelle der gesuchten Daten enthält die Hashtabelle hier Behälter (Buckets), die alle Daten mit gleichem Hash-Wert aufnehmen. Bei einer Suche wird also zunächst der richtige Zielbehälter gesucht. 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 (Worst Case) kann es passieren, daß alle Elemente gleiche Hash-Werte haben und damit in den gleichen Buckets 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.

[Bearbeiten] Vorteile

Trotz der Schwierigkeiten, die sich beispielsweise aus der Kollisionsbehandlung ergeben, bieten Hashtabellen wegen der Vorzüge beim sofortigen Zugriff durch den Hash-Wert auf die Inhalte in einer Tabelle im Vergleich zu der Suche nach dem Schlüssel und wegen der im Idealfall fehlenden Beziehung zweier Hash-Werte, die aus ähnlichen Schlüsseln berechnet wurden, oft Vorteile in der Zugriffszeit als auch im benötigten Speicherplatz gegenüber gewöhnlichen Arrays.

[Bearbeiten] Nachteile

Nachteilig ist dagegen der Umstand, dass die Hashtabelle wegen der Nicht-Injektivität in der Rückrichtung keine Möglichkeiten bietet schnell, d.h. vom Hash-Wert zum Schlüssel (z.B. von der Telefonnummer zum Namen), zu suchen. In diesem Fall ist es sogar möglich, wenn der Schlüssel nicht auch in der Tabelle gespeichert ist, dass man diesen überhaupt nicht ermitteln kann. Aber auch wenn der Schlüssel gespeichert sein sollte, so müssen immer noch üblicherweise im Durchschnitt die Hälfte der Tabelleneinträge durchsucht werden, um den Schlüssel zu finden, was einen Aufwand von O(n) bedeutet.

Außerdem sind die Daten in einer Hashtabelle im Allgemeinem nicht sortiert, womit die sequentielle Ausgabe eines Teils der Einträge oder aller Einträge erheblich erschwert wird.

Hat die Tabelle einen gewissen Füllgrad überschritten, wird sie zwangsläufig entarten. Dann kann nur eine Vergrößerung der Tabelle mit nachfolgender Restrukturierung wieder zu akzeptablem Laufzeitverhalten führen.

Um den Nachteil den Nicht-Injektivität zu konterkarieren, bietet sich an, die Funktion für den Schlüsselgenerator ein weiteres Mal aufzurufen. Schlüsselgeneratorfunktionen sind höchst performant.

[Bearbeiten] Komplexität

Wurden Hash-Funktion und Größe der Hashtabelle geeignet gewählt, ist der Aufwand für die Suche in der Tabelle (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.

[Bearbeiten] Varianten des Hashverfahrens

Es gibt eine Reihe Varianten an Hashverfahren, 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.

[Bearbeiten] Hashing mit Verkettung

Beim Hashing mit Verkettung ist die Hash-Tabelle so strukturiert, dass jeder Behälter eine dynamische Datenstruktur aufnehmen kann - beispielsweise auf 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. Das Datenbanksystem muss bei Suchanfragen die Buckets sektorenweise einlesen.

[Bearbeiten] Hashing mit offener Adressierung

Dieses Verfahren wird abgekürzt auch offenes Hashing, bezogen auf die offene Adressierung, aber auch geschlossenes Hashing, bezogen auf die begrenzte Anzahl möglicher Schlüssel im Behälter, genannt.

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 − 1}. Die Bezeichnung: offene Adressierung, ergibt sich, da durch Kollisionen gleiche Schlüssel unterschiedliche Adressen zugewiesen bekommen können.

[Bearbeiten] 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)mod 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.

[Bearbeiten] Quadratisches Sondieren

Wie beim linearen Sondieren wird nach einem neuen freien Speicher gesucht, allerdings nicht sequenziell, sondern mit stetig quadratisch wachsender Schrittweite 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:

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·j+3, m ist Primzahl), so erzeugt jede Sondierungsfolge h₀(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 bei Primärkollisionen h₀(x) = h₀(y), kann aber die Wahrscheinlichkeit der Bildung von längeren Ketten bei Sekundärkollisionen h₀(x) = h_k(y) herabsetzen, d.h. Clusterbildung wird vermieden.

[Bearbeiten] Doppel-Hashing

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

h_i(x) = (h(x) + h'(x) * i)mod m

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

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] Probleme

• effektives Durchlaufen der Einträge nach einer Ordnung
• effektive Suche nach dem Eintrag mit dem kleinsten oder größten Schlüssel

[Bearbeiten] Anwendung

Ein Anwendungsfall ist das Assoziative Array (auch 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.

Wichtig sind Hashtabellen auch für Datenbanken. Hier werden sie als Index für Tabellen verwendet. Ein sogenannter Hashindex kann unter günstigen Bedingungen zu idealen Zugriffszeiten führen.

Des Weiteren finden Hashtabellen Einsatz in praktisch jeder modernen Applikation. Hier werden sie zur Implementierung von Mengen (Sets) oder eines Caches verwendet. Symboltabellen, die bei Compilern oder Interpretern Verwendung finden, werden meistens auch als Hashtabelle realisiert.

[Bearbeiten] Beispiel

Bildlich kann eine Hashtabelle als ein Telefonbuch betrachtet werden. Suchschlüssel sind die Namen, nach denen gesucht werden soll. Als Hash-Funktion wird die Abbildung des Namens auf seinen Anfangsbuchstaben verwendet. Daraus leitet sich im Idealfall genau die Seite des Namens im Telefonbuch ab. Der Idealfall ist aber nur dann gegeben, wenn es zu jedem Anfangsbuchstaben genau einen Namen geben würde. Dies ist offensichtlich falsch und die Folge sind Kollisionen. Als Ausweg kann man versuchen eine geeignetere Hash-Funktion zu finden.

[Bearbeiten] Siehe auch

• B*-Baum - Schnelles und sehr robustes Indexverfahren bei Datenbanken.
• R*-Baum - Effektives Indexverfahren für mehrdimensionale Daten.
• Verteilte Hashtabelle

[Bearbeiten] Literatur

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest - Introduction to Algorithms. 1184 Seiten; The MIT Press 2001, ISBN 0-262-53196-8
• Christian Ullenboom - Java ist auch eine Insel, 1416 Seiten; Galileo Press 2004, ISBN 3-898-42526-6; online als Openbook verfügbar.