geordnete-hashmap

LinkedHashMap (Geordnete Hash-Zuordnung)

Kurz: Eine Schlüssel-Wert-Zuordnung (Map), die die schnelle Hash-basierte Suche eines HashSet-artigen Zugriffs mit einer vorhersagbaren Reihenfolge kombiniert — Elemente werden in der Reihenfolge durchlaufen, in der sie eingefügt wurden.

Genauer: Eine normale, rein Hash-basierte Map garantiert keine bestimmte Durchlaufreihenfolge; LinkedHashMap merkt sich zusätzlich intern eine verkettete Liste der Einfügereihenfolge, ohne dabei die Geschwindigkeit des Hash-Zugriffs für einzelne Lese-/Schreibzugriffe zu verlieren. Nützlich, wenn sowohl schneller Zugriff über einen Schlüssel als auch eine konsistente Reihenfolge beim Durchlaufen wichtig sind.

Im Detail

Eine gewöhnliche Hash-Map (bzw. HashMap in Java, ein normales dict in älteren Python-Versionen) organisiert ihre Einträge intern rein nach dem berechneten Hash-Wert der Schlüssel — das ist optimal für schnelle Einzelzugriffe (map.get(schluessel)), macht aber die Reihenfolge beim Durchlaufen praktisch zufällig und implementierungsabhängig, weil sie nichts mit der tatsächlichen Einfügereihenfolge zu tun hat.

Map<String, Integer> normal = new HashMap<>();
normal.put("erste", 1);
normal.put("zweite", 2);
normal.put("dritte", 3);
// Durchlauf-Reihenfolge nicht garantiert - könnte "zweite, dritte, erste" sein
 
Map<String, Integer> geordnet = new LinkedHashMap<>();
geordnet.put("erste", 1);
geordnet.put("zweite", 2);
geordnet.put("dritte", 3);
// Durchlauf-Reihenfolge IMMER: erste, zweite, dritte

Technisch erreicht eine LinkedHashMap das, indem sie zusätzlich zur normalen Hash-Tabellen-Struktur eine doppelt verkettete Liste über alle Einträge führt, die die Einfügereihenfolge nachverfolgt — jeder Eintrag “weiß”, welcher davor und danach eingefügt wurde. Das kostet etwas zusätzlichen Speicher gegenüber einer reinen HashMap, ändert aber nichts an der Geschwindigkeit einzelner Lese-/Schreibzugriffe (weiterhin nahezu O(1) dank Hashing).

Ein typischer Einsatzzweck ist ein einfacher LRU-Cache (Least Recently Used) — eine begrenzte Zwischenspeicherstruktur, die die am längsten nicht genutzten Einträge zuerst entfernt, wenn die Kapazität erreicht ist. Die geordnete Struktur einer LinkedHashMap eignet sich dafür besonders gut, weil sich Java-Implementierungen davon sogar so konfigurieren lassen, dass sie die Zugriffsreihenfolge (statt nur Einfügereihenfolge) verfolgen.

Zu unterscheiden von einer TreeMap/sortierten Struktur: LinkedHashMap bewahrt die EINFÜGEREIHENFOLGE, nicht eine SORTIERTE Reihenfolge nach dem Wert der Schlüssel. Wer die Einträge stattdessen z. B. alphabetisch sortiert durchlaufen möchte, braucht eine baumbasierte Struktur statt einer Hash-basierten.

Siehe auch: HashSet, Collections