hashmap-konzept

Hashmap (Dictionary)

Kurz: Eine Hashmap speichert Schlüssel-Wert-Paare und findet einen Wert über seinen Schlüssel im Durchschnitt in konstanter Zeit O(1) – ohne die ganze Sammlung zu durchsuchen.

Genauer: Hinter der schnellen Suche steckt eine Hashfunktion, die aus dem Schlüssel eine Zahl berechnet. Diese Zahl bestimmt, in welchem „Fach“ (Bucket) eines Arrays der Wert liegt. Sprachen nennen sie unterschiedlich: dict in Python, Map/Object in JavaScript, HashMap in Java, Dictionary in C#, map in Go.

Im Detail

alter = {"Mia": 17, "Tom": 25}
alter["Zoe"] = 31               # einfügen
print(alter["Tom"])             # 25  (Zugriff über den Schlüssel)
print("Ben" in alter)           # False
print(alter.get("Ben", 0))      # 0   (Standardwert)
for name, a in alter.items():
    print(name, a)

Kollisionen

Zwei verschiedene Schlüssel können denselben Bucket ergeben (Kollision). Üblich sind Verkettung (jeder Bucket enthält eine kleine Liste) oder offene Adressierung (nächstes freies Fach suchen). Wird die Tabelle zu voll, vergrößert sie sich automatisch (Rehashing).

Eigenschaften

Operation	Durchschnitt	Schlechtester Fall
Einfügen	O(1)	O(n)
Suchen	O(1)	O(n)
Löschen	O(1)	O(n)

Schlüssel müssen unveränderlich (hashbar) sein: In Python sind Strings, Zahlen und Tupel erlaubt, Listen nicht. Die Reihenfolge ist nicht immer garantiert; manche Varianten merken sich die Einfügereihenfolge (siehe geordnete Hashmap). Für Mengen ohne Werte gibt es die hash-basierte Menge.

Typische Einsatzzwecke

Zählen (Häufigkeiten), Gruppieren, Zwischenspeichern von Ergebnissen (Memoization), Konfigurationen, Indexe und schnelle Zuordnungen wie „Benutzer-ID → Benutzer“.

Siehe auch: Hash-basierte Menge, Geordnete Hashmap, Datenstrukturen, Big-O-Notation