Programmierung · Konzepte · Datenstrukturen
Was ist eine Hash Table?
Eine Hash Table (auch Hash Map genannt) ist eine Datenstruktur, die Key-Value-Paare speichert und Sie jeden Wert anhand seines Schlüssels im Durchschnitt in konstanter Zeit finden lässt - egal, wie viele Daten sie enthält. Sie ist eine der nützlichsten Strukturen in der gesamten Programmierung und bildet die Grundlage für die Dictionaries und Maps, die in nahezu jeder Sprache eingebaut sind. Sobald Sie verstehen, wie sie funktioniert, ergeben viele "Wie kann das so schnell sein?"-Momente plötzlich einen Sinn.
Das Problem, das sie löst
Stellen Sie sich vor, Sie speichern ein Telefonbuch als einfache Liste. Um eine Person zu finden, müssten Sie womöglich jeden Eintrag durchsuchen - eine langsame Arbeit, die immer langsamer wird, je größer das Buch wird, eine O(n)-Operation. Das Versprechen einer Hash Table ist ein anderes: Geben Sie ihr den Schlüssel, und sie springt mehr oder weniger direkt zum Wert, ohne zu durchsuchen. Das ist der Unterschied zwischen dem Prüfen jedes einzelnen Eintrags und dem genauen Wissen, wo man nachschauen muss.
Wie sie funktioniert: die Hash-Funktion und Buckets
Im Kern wird eine Hash Table von einem Array aus Slots getragen, die man Buckets nennt. Die magische Zutat ist die Hash-Funktion: Sie nimmt Ihren Schlüssel und verwandelt ihn in eine Zahl, die auf einen Index in diesem Array abgebildet wird.
index = hash(key) % number_of_bucketsUm einen Wert zu speichern, hashen Sie den Schlüssel, um einen Index zu erhalten, und legen den Wert in diesem Bucket ab. Um ihn wieder auszulesen, hashen Sie denselben Schlüssel erneut, landen auf demselben Index und holen den Wert ab. Weil das Berechnen des Hashs und das Indizieren eines Arrays beide schnelle Schritte mit festen Kosten sind, werden Lookups nicht langsamer, wenn die Table wächst. Das ist der ganze Trick.
Kollisionen und wie sie behandelt werden
Zwei verschiedene Schlüssel können zum selben Bucket hashen. Das nennt man eine Kollision, und jede echte Hash Table muss damit umgehen. Es gibt zwei gängige Strategien:
- Chaining: Jeder Bucket enthält eine kleine Liste, und kollidierende Einträge werden gemeinsam in dieser Liste gespeichert. Lookups prüfen dann die (meist sehr kurze) Liste im richtigen Bucket.
- Open addressing: Ist ein Bucket belegt, sucht die Table nach einer festen Regel den nächsten freien Slot, und Suchvorgänge folgen derselben Regel.
Mit einer guten Hash-Funktion und genügend Buckets bleiben Kollisionen selten und diese Listen winzig, sodass Lookups schnell bleiben.
Wie steht es um die Performance?
Hier glänzen Hash Tables, und hier liegt auch der ehrliche Vorbehalt. Im Durchschnitt sind Einfügen, Lookup und Löschen allesamt O(1) - konstante Zeit. Im schlimmsten Fall, wenn eine schlechte Hash-Funktion oder feindliche Eingaben jeden Schlüssel in einen einzigen Bucket kippen, verschlechtern sich diese Operationen auf O(n), weil Sie wieder eine einzelne lange Liste durchsuchen. Gute Implementierungen vermeiden das durch solide Hash-Funktionen und durch Resizing (Rehashing in ein größeres Array), wenn die Table zu voll wird, was die Performance bei amortisiert O(1) hält. Wenn Sie eine Auffrischung zu dieser Notation möchten, lesen Sie unseren Ratgeber zur Big O notation.
Wo Sie bereits eine nutzen
Sie nutzen Hash Tables ständig, oft ohne sie zu benennen. Die Dictionary- und Map-Typen in den meisten Sprachen sind unter der Haube Hash Tables: Python dict, Java HashMap, JavaScript Map und Objekte, Ruby Hash, Go map. Sie sind außerdem das Mittel der Wahl für Caches, das Entfernen von Duplikaten und das Zählen von Vorkommen. Die klassische Optimierung, eine langsame Suche mit verschachtelten Schleifen in eine schnelle zu verwandeln - von O(n²) auf O(n) herunter -, wird fast immer erreicht, indem wiederholte Durchsuchungen durch einen Hash-Table-Lookup ersetzt werden.
Die Kompromisse
- Schnell, aber ungeordnet. Eine grundlegende Hash Table hält die Schlüssel in keiner sortierten oder Einfügereihenfolge (obwohl einige Sprachversionen eine Ordnung obendrauf ergänzen).
- Benötigt zusätzlichen Speicher. Kollisionen selten zu halten bedeutet, freie Buckets vorzuhalten, sodass eine Hash Table etwas Speicher gegen ihre Geschwindigkeit eintauscht.
- Der schlimmste Fall ist real. Das O(1) ist ein Durchschnitt; feindliche Eingaben können den langsamen Pfad erzwingen, was für sicherheitskritischen Code eine Rolle spielt.
FAQ
Ist eine Hash Table dasselbe wie ein Dictionary? Im Alltagssinn ja - ein Dictionary oder eine Map ist die allgemeine Idee (Schlüssel zu Wert), und eine Hash Table ist die häufigste Art, sie umzusetzen. Wenn jemand von Python "dict" oder Java "HashMap" spricht, verwendet er eine Hash Table.
Warum ist Lookup im Durchschnitt O(1)? Weil Sie den Hash des Schlüssels berechnen und direkt in ein Array indizieren, anstatt Einträge zu durchsuchen. Beide Schritte brauchen konstante Zeit, unabhängig davon, wie viele Elemente gespeichert sind, sodass die durchschnittlichen Kosten nicht mit den Daten wachsen.
Was ist eine Kollision? Wenn zwei verschiedene Schlüssel zum selben Bucket hashen. Das ist normal und zu erwarten; Hash Tables behandeln es mit Chaining oder Open addressing und halten es mit einer guten Hash-Funktion und Resizing selten.
Wann sollte ich keine Hash Table verwenden? Wenn Sie Schlüssel in sortierter Reihenfolge oder geordnete Bereichsabfragen benötigen - eine baumbasierte Struktur passt dann besser. Auch wenn der Speicher extrem knapp ist, da Hash Tables freien Platz vorhalten, um schnell zu bleiben.