Java LinkedHashMap

LinkedHashMap<K, V> ist eine HashMap<K, V> mit einer doppelt verketteten Liste, die durch jeden Eintrag verläuft. Die Hashtabelle übernimmt ihre übliche Aufgabe — O(1) put, get, remove — und die verkettete Liste liefert eine garantierte, vorhersehbare Iterationsreihenfolge. Standardmäßig ist diese Reihenfolge die Einfügereihenfolge; mit einem einzigen Konstruktor-Flag wird sie zur Zugriffsreihenfolge, dem Grundbaustein eines Least-Recently-Used-(LRU-)Caches.

Zwei Ordnungen, eine Klasse

Die Konstruktoren spiegeln HashMap, plus einem weiteren:

new LinkedHashMap<>();                              // insertion order
new LinkedHashMap<>(16, 0.75f, false);              // insertion order, explicit
new LinkedHashMap<>(16, 0.75f, true);               // ACCESS order

Das dritte boolean ist das accessOrder-Flag. Wenn es auf false gesetzt ist (Standard), hängt jedes put eines neuen Schlüssels den Eintrag ans Ende der verketteten Liste; ein erneutes put eines vorhandenen Schlüssels lässt seine Position unverändert. Ist es auf true gesetzt, verschiebt jedes get, put oder getOrDefault, das einen Schlüssel berührt, diesen Eintrag ans Ende der Liste — der zuletzt zugegriffene Eintrag ist immer letzter; der am längsten nicht zugegriffene ist immer erster.

Dieser zweite Modus ist im Anwendungscode selten, und der einzige Ort, an dem man ihn sieht, ist genau dort, wo man ihn am meisten braucht: beim Implementieren eines Caches.

Iteration in Einfügereihenfolge ist der häufigste Anwendungsfall

In 90 % der Fälle greift man zu LinkedHashMap, weil man eine stabile Ausgabe möchte. Beispiele:

• Rückgabe einer Map<String, Object> von einem JSON-serialisierenden Endpunkt, bei dem die Felder in der Einfügereihenfolge erscheinen sollen.
• Protokollierung des Inhalts einer Map in deterministischer Reihenfolge für Diffs.
• Aufbau einer Konfiguration, bei der die Reihenfolge wichtig ist (z. B. Middleware-Kette, Header-Reihenfolge, Validierungs-Pipeline).
• Rückgabe einer Map aus einer öffentlichen API, ohne dass Aufrufer von der beliebigen Reihenfolge einer HashMap abhängig werden sollen.

Der Mehraufwand gegenüber HashMap besteht aus zwei zusätzlichen Referenzen pro Eintrag (den before- und after-Zeigern). Für konfigurationsgroße Maps spielt das keine Rolle; bei engen Schleifen über sehr große Maps könnte man HashMap bevorzugen, wenn man kann.

Iteration ist proportional zur Größe

Ein Nebeneffekt: Das Iterieren einer LinkedHashMap durchläuft die verkettete Liste, die genau size Einträge enthält. Das Iterieren einer HashMap durchläuft alle Bucket-Slots — einschließlich leerer. Bei einer dünn besetzten Map ist der Unterschied spürbar.

Aufbau eines LRU-Caches

Das Killer-Feature der Zugriffsreihenfolge ist der geschützte removeEldestEntry-Hook. Er wird nach jedem put aufgerufen, und wenn er true zurückgibt, entfernt die Map ihren ersten (ältesten) Eintrag. Beides kombiniert:

class LruCache<K, V> extends LinkedHashMap<K, V> {
  private final int max;
  LruCache(int max) { super(16, 0.75f, true); this.max = max; }
  @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > max;
  }
}

Zwölf Zeilen für einen thread-unsicheren, aber voll funktionsfähigen LRU-Cache. Jedes get ordnet den Eintrag ans Ende; jedes put ruft removeEldestEntry auf; sobald die Größe max überschreitet, wird der Eintrag vorne (der am längsten nicht zugegriffene) entfernt.

Für thread-sicheres LRU umschließt man es mit Collections.synchronizedMap oder — besser — verwendet eine echte Cache-Bibliothek (Caffeine), da die Zugriffsreihenfolge-Updates jeden get zu einem Schreibvorgang machen und der einfache synchronisierte Wrapper alle Lesevorgänge serialisiert. Für Single-Thread-Code ist dies jedoch der klassische Trick und es lohnt sich, ihn zu kennen.

Nulls und die übrigen Regeln

Wie bei HashMap: ein null-Schlüssel, beliebig viele null-Werte. Nicht thread-sicher. Gleichheit ist die strukturelle Gleichheit, die Map definiert — eine LinkedHashMap und eine HashMap mit denselben Einträgen sind equals. Die Iterationsreihenfolge ist nicht Teil der Gleichheit; sie ist nur das, was man beim Iterieren erhält.

Ein ausgearbeitetes Beispiel: Einfügereihenfolge, Zugriffsreihenfolge und ein LRU-Cache

Das folgende Programm baut eine kleine Middleware-Kette in Einfügereihenfolge auf, vergleicht die Iteration von HashMap vs. LinkedHashMap mit denselben Daten und implementiert dann einen kleinen LRU-Cache und beobachtet seine Verdrängung.

Was man aus dem Durchlauf mitnehmen kann:

• Die Pipeline iteriert in der Reihenfolge log → auth → rateLimit → handler — genau der Reihenfolge, in der sie eingefügt wurde. Eine einfache HashMap hätte immer noch alle vier Einträge, aber die Reihenfolge wäre beliebig.
• HashMap und LinkedHashMap mit denselben Daten geben in unterschiedlicher Reihenfolge aus; die LinkedHashMap entspricht keys, die HashMap nicht.
• Der LRU-Cache hat sich neu geordnet, als get("a") aufgerufen wurde — a ging ans Ende der Liste, sodass b der neue älteste Eintrag wurde. Das nächste put("d", "D") löste die Verdrängung von b aus, nicht von a. Das ist die Zugriffsreihenfolge-Regel in Aktion.

Wie es weitergeht

Die dritte Standard-Map-Implementierung bietet etwas, das keine der hashbasierten kann: sortierte Iteration nach Schlüssel und Bereichsabfragen (subMap, headMap, tailMap, firstKey, lastKey). TreeMap kommt als nächstes; die Struktur ist identisch mit TreeSet darunter — sie verwenden buchstäblich denselben Rot-Schwarz-Baum-Code.

Übungen