Sucht man nun das zu einem Schlüssel gehörige Element, so berechnet man wieder den Hash des Schlüssels und durchsucht den entsprechenden Bucket.

Die beiden wichtigen Kriterien für die Performance einer speziellen Implementierung ist die Qualität der Hashfunktion und die Anzahl der Buckets. Bei einer schlechten Hashfunktion wird ein Teil der Buckets leer gelassen oder nur schlecht ausgenutzt. Ist die Anzahl der Buckets im Verhältnis zu den eingefügten Werten zu gering, kommt es selbst bei einer optimalen Hashfunktion zu

Anzahl Werte/Anzahl Buckets

Werten pro Bucket. Durch beide Degenerationen wird die Suchzeit für einen gegebenen Schlüssel unnötig verlängert, da die (linear) durchsuchten Listen länger werden. Meist wird daher die Hashtabelle dynamisch vergrößert, wenn der oben definierte Befüllungsgrad einen bestimmten Wert (typischer Bereich 0.5-0.8) übersteigt. Das garantiert, dass bei einer guten Hashfunktion die meisten Elemente auf Anhieb gefunden werden.

In einer guten Implementation kann das Einfügen, Löschen und Auffinden von Schlüsseln immer in asymtotisch konstanter Zeit erledigt werden.

Im Gegensatz zu baumartigen Strukturen ist die Implementierung einer Hashtabelle einfacher und flexibler, da beliebige Schlüssel verwendet werden können. Dafür müssen die Buckets vorab schon alloziert werden und die Performance der Tabelle ist stark von der Qualität der Hashfunktion, sowie von den auftretenden Schlüsseln abhängig.

HashTabellen sind eine häufige Implementierung von Mappings (kurz "Maps" auch Dictionaries oder assoziatives Array genannt) und Sets.

Perl-Beispiel

Die assoziativen Arrays in perl werden mittels einer Hashtabelle verwaltet. Daher werden sie im Jargon als "hashes" bezeichnet.

my (%alter, $key); $alter{'Peter'}=25; $alter{'Jana'}=13; $alter{'Alex'}=51; foreach $key (sort keys %alter) { print "Alter($key): $alter{$key}\n"; }

Die Initialisierung des assoziativen Arrays könnte auch vereinfacht als

my %alter = ('Peter', 25, 'Jana', 13, 'Alex', 51);

oder besser (lesbarer; "=>" ist semantisch equivalent zu ",") als

my %alter = ('Peter' => 25, 'Jana' => 13, 'Alex' => 51);

geschrieben werden.

D. h. oben wird die Hashtabelle aus einer Liste (Perl-Bezeichnung für einen Array befüllt. Diese Transformation geht jederzeit in jede Richtung:

my @array = ('Peter', 25, 'Jana', 13, 'Alex', 51); my %alter=@array; @array=%alter;

Nachdem die Inhalte von Arrays und Hashes nicht nur Einzelwerte (Skalare= Strings oder Zahlen), sondern wiederum auch Arrays und Hashes sein können, stehen hier Strukturierungssysteme zur Verfügung, die mindestens so universell, aber leichter zu handhaben sind wie die klassischen LISP-Listen.

Optimierungsmöglichkeiten

In manchen Situationen kann die Implementierung eines LRU-Algorithmus auf die Link-Listen etwas Performance bringen.

Wenn die Keys statisch bekannt sind (z. B. die keywords einer Programmiersprache), dann kann man eine perfekte HashFunktion suchen, die keine Kollisionen erzeugt und im Idealfall 100% Befüllungsgrad aufweist. Es gibt Programme, die dabei helfen (z. B. gperf).

Allgemeines

HashTabellen haben sich als so flexible und praktische Datenstrukturen herausgestellt, dass viele moderne Sprachen (Perl, PHP, Python, Ruby, D, ...) sie als Primitives in ihren Sprachumfang integrieren. Das vereinfacht die Handhabung, erhöht die Performance und lässt auch eine einfache statische Initialisierung zu.

• Linux Kernel Hash Table Behaviour, http://www.citi.umich.edu/projects/linux-scalability/reports/hash.html
• DDJ Hashing Rehashed, http://www.ddj.com/articles/1996/9604/9604b/9604b.htm
• http://lists.bikeworld.com/pipermail/thttpd/2000-October/000240.html
• http://burtleburtle.net/bob/hash/doobs.html
• http://gisp.jxta.org/servlets/ProjectHome GISP (Global Inforatio Sharing Protocoll) Verteilte HashTabellen mit Java und JXTA