Was ist Hashtabelle (Hash Table)?
Datenstruktur, die mit einer Hashfunktion aus einem Schlüssel eine Speicherposition berechnet und so Suchen, Einfügen und Löschen im Mittel in O(1) ermöglicht. Kollisionen, bei denen verschiedene Schlüssel auf dieselbe Position fallen, werden durch Verkettung (Chaining) oder offene Adressierung behandelt.
Japanische Bezeichnung: ハッシュテーブル
„Hashtabelle (Hash Table)“ kommt in 5 Übungsfragen aus 3 Themen vor, z. B. Datenstrukturen und Algorithmen, Wahrscheinlichkeitsrechnung, Statistik und Warteschlangen, Multicore und Synchronisation.
Fachgebiet: Datenstrukturen und Algorithmen
Funktionsweise und Behandlung von Kollisionen
Eine Hashtabelle wandelt einen Schlüssel mit einer Hashfunktion in eine ganze Zahl um und verwendet zum Beispiel deren Rest bei Division durch die Tabellengröße als Speicherposition. Es gibt weit mehr mögliche Schlüssel als Positionen, daher sind Kollisionen, bei denen verschiedene Schlüssel auf dieselbe Position fallen, unvermeidlich. Die Verkettung (Chaining) verbindet die Elemente derselben Position, zum Beispiel in einer verketteten Liste. Die offene Adressierung sucht eine andere freie Position innerhalb der Tabelle, etwa mit linearem Sondieren, das die Nachbarpositionen der Reihe nach prüft, oder mit doppeltem Hashing, das die Schrittweite mit einer zweiten Hashfunktion bestimmt.
Belegungsfaktor und Rehashing
Die Zahl der gespeicherten Elemente geteilt durch die Tabellengröße heißt Belegungsfaktor (Load Factor). Bei Verkettung ist die mittlere Listenlänge proportional zum Belegungsfaktor; bei offener Adressierung steigt die Zahl der Sondierschritte bis zu einem freien Platz stark an, wenn sich der Belegungsfaktor 1 nähert. Überschreitet der Belegungsfaktor einen gewählten Grenzwert, wird die Tabelle daher vergrößert, typischerweise auf etwa das Doppelte, und alle Elemente werden neu eingefügt (Rehashing). Ein Rehashing kostet O(n), doch da sich die Abstände zwischen den Vergrößerungen immer wieder verdoppeln, bleibt der Aufwand pro Einfügung bei amortisiert O(1).
Leistung und Fallstricke
Das mittlere O(1) setzt voraus, dass die Hashfunktion die Schlüssel gleichmäßig über die Tabelle verteilt. Eine schlechte Hashfunktion oder Eingaben, die gezielt Kollisionen erzeugen (ein Hash-Flooding-Angriff), können sie im schlechtesten Fall auf O(n) verlangsamen; Webserver und ähnliche Software verwenden daher Hashfunktionen, in die ein zufälliger Startwert einfließt. Eine Hashtabelle hält ihre Elemente außerdem nicht in sortierter Reihenfolge, daher eignen sich für Bereichssuchen und sortierte Auflistungen binäre Suchbäume oder B-Bäume besser. Die tatsächliche Geschwindigkeit hängt auch vom Cache-Verhalten ab: Verfahren, die benachbarte Plätze prüfen, wie das lineare Sondieren, sind oft schneller als die Verkettung, die Zeigern folgt.
Häufige Fragen
Wie hängen Hashtabellen und Hashfunktionen zusammen?
Eine Hashfunktion berechnet aus einem Schlüssel einen Wert in einem festen Bereich, und eine Hashtabelle ist eine Datenstruktur, die damit Speicherpositionen berechnet. Hashfunktionen für Hashtabellen legen Wert auf Geschwindigkeit und gleichmäßige Verteilung und brauchen üblicherweise keine Einwegeigenschaft wie kryptografische Hashfunktionen.
Wo werden Hashtabellen verwendet?
Überall dort, wo Werte schnell über einen Schlüssel nachgeschlagen werden müssen, etwa für Dictionaries (assoziative Arrays) und Sets in Programmiersprachen, Symboltabellen in Compilern, Hash-Joins und Hash-Indizes in Datenbanken sowie die Verwaltung von Caches.