Hashtabelle

Die Hashtabelle (hashing: zerhacken) ist eine Datenstruktur, die für schnelle Zugriffe konzipiert wurde. Mit Hilfe einer mathematischen Funktion - der Hashfunktion - wird die Position berechnet, an der die Elemente gespeichert werden. Die Hashfunktion ist eine Abbildung der natürlichen Zahlen auf den Elementebereich (0 ... Tabellenlänge-1), die den sogenannten Schlüssel in eine Adresse der Tabelle abbildet. Diese Berechnung ist schnell und erlaubt somit auch einen schnellen Zugriff auf das Element. Dazu wird für ein Element ein Hashcode berechnet, der nur vom Zustand des Elements abhängt und nicht von anderen Objekten, wie Vorgänger oder Nachfolger. Der Nachteil von Hashtabellen ist, dass die Reihenfolge der Elemente nicht erhalten bleibt.

Bei größeren Datenmengen, die in Form von Arrays oder verketteten Listen gespeichert sind, ist die Suche nach einem Element, dessen Position nicht bekannt ist, oft zeitaufwändig. Die Suche wird sequentiell Element für Element durchgeführt, bis das betreffende Element gefunden wurde. Zur Lösung dieses Problems sind die beiden Datenstrukturen Hashtabelle und Baumstruktur entwickelt worden.

Die Hashtabelle als Array von Listen

Eine Hashtabelle ist ein Array von verketteten Listen, so dass die Suche nach einem Element letztendlich ein indizierter Zugriff auf ein Feld ist. Die Listen werden auch als Bucket bezeichnet. Die Anzahl der verketteten Listen ist von der Anzahl der zu speichernden Elemente abhängig. In eine verkettete Liste werden jeweils die Elemente mit dem gleichen Hashcode aufgenommen. Die genaue Position eines Elementes berechnet sich aus dessen Hashcode modulo der Gesamtzahl der verketteten Listen.

Eine Hashtabelle wird von zwei Merkmalen beeinflusst, der Kapazität und dem Ladefaktor. Die Kapazität sollte aber um den Faktor 1,5 bis 2 größer gewählt werden als die zu erwartende Anzahl der Elemente. Sonst ist die Wahrscheinlichkeit zu groß, dass mehrere Elemente in einer verketteten Liste gespeichert werden und so die Effizienz abnimmt.

Hashtabelle und verkettete Listen

Hashtabelle und verkettete Listen

Bei der Abbildung des Schlüsselbegriffs auf die Adressen des Arrays kann es zu sogenannten Kollisionen kommen; d.h. zwei oder mehr Elemente sollen auf den gleichen Index abgebildet werden. Hierzu wurden verschiedene Kollisionsstrategien wie die Direkte Verkettung oder das Hashing mit offener Adressierung entwickelt. Hierbei ist beim Löschen von Elementen besonders sorgsam vorzugehen, da belegte Tabellenpositionen nicht ohne zusätzliche Vorkehrungen freigegeben werden dürfen.

Ist eine Hashtabelle vollständig gefüllt, wird sie in eine neue Hashtabelle mit doppelt so vielen Buckets umgespeichert. Der Ladefaktor gibt an, bei welchem Füllstand dieses Umspeichern durchgeführt werden soll. Der Standardwert dafür beträgt beispielsweise in den implementierten Java-Klassen 75%.

Die Qualität der Hashtabelle

Die Qualität der Implementierung einer Hashtabelle ist generell abhängig von der Wahl der Hashfunktion. Dabei sollte eine gute Hashfunktion alle Werte des Elementbereichs gleichwahrscheinlich abdecken, um auch die Kollisionswahrscheinlichkeit für alle Tabellen-Adressen gleichwahrscheinlich zu machen.

Die Möglichkeit des schnellen Suchens von Elementen ist sicherlich als Vorteil von Hashing anzusehen. Nach-teilig gegenüber dynamischen Verfahren ist die Zuweisung einer statischen Tabellenlänge. Dies bedingt vorab eine gute Abschätzung der Zahl der zu ordnenden Elemente, um so Nachteile wie die schlechte Speicherausnutzung oder mangelnde Leistung zu vermeiden.

Um die Performance einer Hashtabelle zu steigern, gibt es die folgenden Möglichkeiten: Erhöhung der Tabellengröße, die Behandlung von Kollisionen durch eine bessere Methode - z.B. die Methode der direkten Verkettung und die Anwendung einer Hashfunktion höherer Güte.

Informationen zum Artikel
Deutsch: Hashtabelle
Englisch: hash table
Veröffentlicht: 01.11.2013
Wörter: 557
Tags: IT-Grundlagen
Links: Datenstruktur, Hashfunktion, Abbildung, Schlüssel, Adresse
Übersetzung: EN
Sharing: