Datenstrukturen: Hashmap / Hashtabelle

Eine Hashmap (deutsch: Hashtabelle) ist eine weitere wichtige Datenstruktur und etwas komplizierter als Listen und Sets. Das Prinzip einer Map besteht darin, einem Wert X einen anderen Wert Y zuzuordnen. Dieser Wert X wird als Key und der zugeordnete Wert Y als Value bezeichnet.

Die Keys einer Map enthalten, wie bei den Sets, keine Duplikate. Allerdings gilt dies nicht für die dazugehörigen Values.
Man kann sich die Objekte bei dieser Datenstruktur als ein Paar vorstellen: (key,value).

Möchte man ein Objekt einfügen, so sollte der Key einen dazugehörigen Value haben. Gibt man keinen Value an, so ist dieser NULL. Eine nachträgliche Manipulation eines Values ist möglich.
Neben dem Einfügen kann man Objekte auch wieder entfernen. Dabei sollte man beachten, dass das Entfernen eines Keys automatisch den dazugehörigen Value mit entfernt. Ist man nur daran interessiert den Value eines Keys zu entfernen, so ist dies auch möglich. Der Key bleibt bestehen und der dazugehörige Value wird zu NULL.

Die Iteration einer Map funktioniert ähnlich wie die eines Sets. Der unterschied ist, dass der Iterator bei einem Set stets das direkte Objekt liefert. Bei einer Map wird das sogenannte KeySet (Alle Keys einer Map) durchlaufen, um an die Keys zu kommen. Um nun einen zugehörigen Value auszulesen oder zu manipulieren, bietet die Map eine entsprechende Funktion an. Diese Funktion wird auf den Key des KeySets angewendet.

Beispiel: Hauptstadt - Land

Angenommen man möchte zu einer Hauptstadt das jeweilige Land zuordnen. Dafür benötigt man einmal die Hauptstadt als Key und das dazugehörige Land als Value. (Man könnte es auch umgekehrt machen).

Beim einfügen wird eine Funktion Map.add(key,value) aufgerufen. Zum Beispiel: Map.add("Rom","Italien"). Dasselbe gilt für die restlichen Einträge. Dadurch entsteht folgende Map.

Abbildung: Eine Hashmap

Genauso wie bei einem Set wird bei einer Map zu jedem einzufügenden Objekt eine Hashfunktion aufgerufen. Diese sorgt für die Identifikation des Keys und dafür, dass es keine Duplikate gibt.

Ich möchte gerne wissen: Tokyo ist die Hauptstadt von welchem Land? Dazu benutzen wir einen Iterator.

Pseudocode

for key in Map.Iterator.keySet()
    Durchsuche alle Keys in der Map und finde den key, wo Tokyo drin steht
    if key == "Tokyo" then
        Das Land zu der Hauptstadt Tokyo lautet
        value = key.value()
    else
        suche weiter

Anwendungsbeispiel

Eine Map ist immer dann geeignet, wenn man unbedingt eine Zuordnung benötigt. Sollte dies nicht der Fall sein, dann wären Listen oder Sets zu bevorzugen.
Es sind durchaus kompliziertere Varianten einer Map vorstellbar. Ein englisches Wort könnte mehrere deutsche Bedeutungen haben. In diesem Beispiel müssten die Values aus einer Liste oder einem Set bestehen. Das heißt, die Keys bleiben Strings (Zeichenketten) aber die dazugehörigen Values wären nun eine Liste aus Strings Map<String, List> .

• Vokabeltrainer (Key=englisches Wort, Value=deutsches Wort)
• Wertetabelle (Key=eine Zahl, Value=Funktionswert einer Zahl -> f(x)=x)
• Kreuzworträtsel (Key=Lösungswort, Value=Liste von Wortbeschreibungen)

Quelle:
https://www2.cs.arizona.edu/~mercer/Presentations/HashTables.pdf