Sinn und Zweck
Speichern von Schlüssel-Wert-Paaren
Eine HashMap ist eine Speicherstruktur, in der sogenannte Schlüssel-Wert-Paare gespeichert werden können – also beispielsweise Name-Telefonnummer, Name-Adresse, Kundennummer-Name, Artikelnummer-Artikel und so weiter, um nur ein paar Beispiele zu nennen.
Jeder Schlüssel ist dabei genau einem Wert zugeordnet, und man kann die Werte über die Schlüssel wieder abrufen.
Warum speichert man solche Schlüssel-Wert-Paare nicht einfach in einer ArrayList oder sogar in einem Array von solchen Paaren?
Die Antwort lautet: Weil eine HashMap unschlagbar schnell ist, was das Suchen und Finden betrifft.
Die Paare werden intern in einem Array gespeichert, allerdings ist dieser Array nicht sortiert – weder auf- noch absteigend.
Der Fachmann (und natürlich auch die Fachfrau) mag sich wundern, denn in einem sortierten Array könnte man mittels binärer Suche die Schlüssel und die zugehörigen Werte doch recht schnell finden.
Es geht aber noch schneller:
In einer HashMap werden die Indizes des Arrays aus den Schlüsseln berechnet – mithilfe einer sogenannten Hash-Funktion. Wie diese genau funktioniert, soll hier nicht näher behandelt werden. Wichtig ist: Diese Hash-Funktion erzeugt aus einem Schlüssel einen ganzzahligen Hash-Wert, und aus diesem wird dann der Index im Array bestimmt.
Sucht man nun nach einem bestimmten Element, so wird der Suchbegriff erneut durch die Hash-Funktion in einen Index umgewandelt – und man findet in quasi Nullzeit die zugehörige Position im Array.
Während in einer sortierten Liste die Suche im schlimmsten Fall eine O(n)-Funktion ist, ermöglicht eine HashMap das Einfügen und Suchen im Durchschnitt in konstanter Zeit: O(1). [4, 5] Und das ist unschlagbar kurz!
Interne Implementierung
Eine HashMap verwendet intern eine Kombination aus einem "normalen" Array und mehreren einfach verketteten Listen. Das Array ist quasi das Rückgrat der HashMap, die Listen können als "Rippen" betrachtet werden, die von diesem Rückgrat ausgehen.
Betrachten wir ein konkretes Beispiel. In einer HashMap sollen die Noten von 10 Schülern und Schülerinnen gespeichert werden, und zwar für je 11 Fächer. Auf die Einzelheiten der Implementation wollen wir hier nicht eingehen.
Betrachten wir nun die erzeugte HashMap mit dem BlueJ-Objektinspektor.
Die Instanzvariablen einer HashMap
Die HashMap klassenNoten im BlueJ-Objektinspektor
Dieses Bild zeigt acht Instanzvariablen des HashMap-Objektes klassenNoten.
Gehen wir diese acht Variablen einmal durch.
table
- Diese Instanzvariable verkörpert den zentralen Array der HashMap, das "Rückgrat" sozusagen. Jedes Arrayelement wird als Bucket (Eimer) bezeichnet, in dem die Schlüssel-Wert-Paare gespeichert sind. Einzelheiten dazu siehe weiter unten.
entrySet
- Eine Art Zwischenspeicher, der bei Bedarf angelegt wird.
size
- Die aktuelle Anzahl der in der HashMap gespeicherten Schlüssel-Wert-Paare.
modCount
- Die Anzahl der Veränderungen, denen die HashMap unterzogen wurde. Jedes Hinzufügen oder Löschen eines Elementes gilt zum Beispiel als Veränderung.
threshold
- Sobald die Größe (size) der HashMap größer ist als dieser Wert (size >= threshold), wird die Kapazität der HashMap verdoppelt. Dabei werden die Einträge in die Sammlung neu verteilt. In diesem Punkt unterscheidet sich eine HashMap also ganz wesentlich von einer ArrayList.
loadFactor
- Mit diesem Wert wird festgelegt, ab welcher Größe die HashMap erweitert wird. Ein loadFactor von 0,75 (Standardwert) besagt also, dass die Map erweitert wird, sobald 75% bzw. 3/4 der Elemente belegt sind.
- loadFactor ist das Verhältnis (z. B. 75 %), threshold dagegen ist die konkrete Anzahl (z. B. 12 Einträge), ab der die HashMap vergrößert wird."
keySet
- Eine Sicht auf alle aktuell in der Map gespeicherten Schlüssel. Wird wie entrySet nur bei Bedarf erzeugt (lazy Initialization) und zwischengespeichert.
values
- Eine Sicht auf alle aktuell gespeicherten Werte in der Map. Auch hier nur Lazy Initialization, also Erzeugung bei Bedarf.
Das Rückgrat der HashMap
Wenn wir nun auf den Pfeil doppelklicken, der die Instanzvariable table verkörpert, erhalten wir folgendes Bild:
Der Bucket-Array einer HashMap
Hier sehen wir ein Array aus 16 Buckets. In dem Testprogramm, mit dem die Notenliste überprüft wurde, haben wir der HashMap sieben Schlüssel-Werte-Paare (Name, Notenliste) hinzugefügt. In diesem Bild sehen wir aber nur fünf Buckets, die einen Pfeil enthalten, also eine Referenz auf ein solches Paar. Wie kann das sein? Sind zwei der Werte-Paare "verschluckt" worden?
Die Buckets der HashMap
Wir doppelklicken nun auf den ersten Pfeil:
Der Inhalt des ersten Buckets
Die erste Instanzvariable dieses Buckets ist der Hash-Wert. Dieser Wert wird nach einem bestimmten Algorithmus aus dem Schlüsselwert des Schlüssel-Wert-Paares berechnet, in unserem Fall also aus dem Namen des Schülers, der aus zwei String-Werten (Name, Vornamspan class="variable"e) besteht.
Die Instanzvariable key ist eine Referenz auf den Schlüsselwert (Name, Vorname), und die Instanzvariable value ist eine Referenz auf den eigentlichen Wert (hier die Notenliste).
Die Referenzvariable key zeigt auf einen Record (nachname,vorname) aus zwei Strings
Hier sehen wir den ersten Schlüsselwert.
Interessant ist die vierte Instanzvariable next. Sie hat hier den Wert null. Zur Bedeutung dieser Instanzvariable kommen wir jetzt gleich.
Wir doppelklicken nun auf den zweiten Eintrag in dem Bucket-Array. Auch dort hat die Instanzvariable next den Wert null.
Dasselbe wiederholen wir mit dem dritten Eintrag. Und jetzt wird es interessant:
Die Referenzvariable key zeigt auf einen Record (nachname,vorname) aus zwei Strings
Hier taucht plötzlich ein Pfeil in dem weißen Kasten auf. Wenn wir auf diesen doppelklicken, erhalten wir:
Die Referenzvariable key zeigt auf einen Record (nachname,vorname) aus zwei Strings
Der erste Eintrag verweist also auf einen folgenden zweiten Eintrag. Dieser zweite Eintrag hat dann aber keinen Nachfolger mehr.
Auf die gleiche Weise hat auch der fünfte Eintrag in dem Bucket-Array noch einen Nachfolger. Insgesamt sind also sieben Einträge in der HashMap untergebracht. Das stimmt dann mit dem Wert von size überein.
Kollisionsbehandlung
Es kann vorkommen, dass verschiedene Schlüssel den gleichen Array-Index ergeben. Dies wird als Hash-Kollision bezeichnet. Um dieses Problem zu lösen, geht die HashMap folgendermaßen vor:
Zunächst wird an dem entsprechenden Array-Index eine einfach verkettete Liste von Einträgen gespeichert. Jeder Knoten in der Liste enthält den Schlüssel, den Wert, den Hashcode und einen Verweis auf den nächsten Knoten. Wenn ein neues Element in einen bereits belegten Bucket eingefügt wird, wird es am Ende der Liste angehängt.
Wenn diese Liste zu groß wird, wird die Liste in einen ausgeglichenen binären Suchbaumumgewandelt. Dadurch wird die Suchzeit erheblich verkürzt: In der linearen Liste findet ein lineares Suchen statt (O(n)), während der Binärbaum logarithmisch durchsucht werden kann (O(log n)).
Berechnung des Hash-Wertes bzw. des Index im Bucket-Array
1. Hash-Wert berechnen
Aus dem Wert des Schlüssels wird zunächst ein Hash-Wert berechnet. Auf den genauen Algorithmus wollen wir hier nicht eingehen. Wir können aber festhalten, dass der Schlüsselwert in eine ganze Zahl umgewandelt wird bzw. auf eine ganze Zahl abgebildet wird - mathematisch gesprochen. Interessanterweise hat jedes Java-Objekt eine Methode hashCode(), die für das Objekt einen solchen Hash-Wert liefert. Diese Methode wird von der HashMap jetzt einfach für jeden Schlüssel aufgerufen.
2. Hash-Spreading
Als Nächstes findet ein sogenanntes Hash-Spreading statt. Dazu wird der Hash-Wert intern weiterverarbeitet, um eine bessere Verteilung der Elemente im Bucket-Array zu erreichen.
3. Index-Berechnung
Sobald der optimierte Hash-Wert feststeht, wird daraus der Index im Bucket-Array table[] berechnet. Das geschieht mit folgender Anweisung:
int index = (n - 1) & hash;
Dabei ist n die aktuelle Länge des Arrays (also beispielsweise 16, 32, 64 etc., immer eine Zweierpotenz).
Der Operator & steht für eine Bitmaske, bei einer Arraygröße von 16 hat n-1 den Binärwert 0000 1111. Aus dem optimierten Hash-Wert werden also - in Binärdarstellung - nur die untersten vier Bit berücksichtigt, damit wird der Hash-Wert auf die Zahlen 0 bis 15 abgebildet.
Titel
Merke:
HashMap
-
Eine HashMap speichert Schlüssel-Wert-Paare, z. B. Name → Telefonnummer.
-
Jeder Schlüssel ist eindeutig und genau einem Wert zugeordnet.
-
Der Zugriff erfolgt über den Schlüssel, nicht über Positionen.
-
Im Gegensatz zu sortierten Listen ist die HashMap extrem schnell beim Suchen.
-
Intern verwendet sie ein Array von Buckets (Fächern).
-
Der Index im Array wird aus dem Schlüssel mit einer Hash-Funktion berechnet.
-
Diese erzeugt aus dem Schlüssel einen ganzzahligen Hash-Wert, aus dem dann der Bucket-Index abgeleitet wird.
-
Dadurch ist der Zugriff im Durchschnitt in O(1) möglich, das ist schneller als bei Listen (O(n) oder O(log n)).
-
Kollisionen (gleicher Index für verschiedene Schlüssel) werden intern gelöst, z. B. durch Verkettung oder Bildung von Binärbäumen.
-
Eine HashMap ist ideal für große Mengen schnell zugreifbarer Daten.
Quellen:
- Lahres et al.: Objektorientierte Programmierung, Rheinwerk Computing 2021.
- Barnes, Kölling: Java lernen mit BlueJ - Objects first. Pearson-Verlag 2019.
- Ullenboom: Java ist auch eine Insel, Rheinwerk Computing 2023.
- Oracle Dokumentation zur Klasse HashMap.
- "A Guide to Java HashMap" auf www.baeldung.com
- "The Java HashMap Under the Hood" auf www.baeldung.com, 2023