Eine Anleitung zu LinkedHashMap in Java

1. Übersicht

In diesem Artikel werden wir die interne Implementierung der LinkedHashMap- Klasse untersuchen. LinkedHashMap ist eine gängige Implementierung der Map- Schnittstelle.

Diese spezielle Implementierung ist eine Unterklasse von HashMap und teilt daher die Kernbausteine ​​der HashMap- Implementierung. Aus diesem Grund wird dringend empfohlen, dies aufzufrischen, bevor Sie mit diesem Artikel fortfahren.

2. LinkedHashMap vs HashMap

Die LinkedHashMap- Klasse ist HashMap in den meisten Aspekten sehr ähnlich . Die verknüpfte Hash-Map basiert jedoch sowohl auf der Hash-Tabelle als auch auf der verknüpften Liste, um die Funktionalität der Hash-Map zu verbessern.

Zusätzlich zu einem zugrunde liegenden Array mit der Standardgröße 16 wird eine doppelt verknüpfte Liste verwaltet, die alle Einträge durchläuft.

Um die Reihenfolge der Elemente beizubehalten, ändert die verknüpfte Hashmap die Map.Entry- Klasse von HashMap, indem Zeiger auf den nächsten und vorherigen Eintrag hinzugefügt werden:

static class Entry extends HashMap.Node { Entry before, after; Entry(int hash, K key, V value, Node next) { super(hash, key, value, next); } }

Beachten Sie, dass die Entry- Klasse einfach zwei Zeiger hinzufügt. davor und danach kann es sich an die verknüpfte Liste binden. Abgesehen davon wird die Entry- Klassenimplementierung einer HashMap verwendet.

Denken Sie schließlich daran, dass diese verknüpfte Liste die Reihenfolge der Iteration definiert, die standardmäßig die Reihenfolge des Einfügens von Elementen ist (Einfügereihenfolge).

3. Einfügereihenfolge LinkedHashMap

Schauen wir uns eine verknüpfte Hash-Map-Instanz an, die ihre Einträge nach ihrer Einfügung in die Map ordnet. Es garantiert auch, dass diese Reihenfolge während des gesamten Lebenszyklus der Karte beibehalten wird:

@Test public void givenLinkedHashMap_whenGetsOrderedKeyset_thenCorrect() { LinkedHashMap map = new LinkedHashMap(); map.put(1, null); map.put(2, null); map.put(3, null); map.put(4, null); map.put(5, null); Set keys = map.keySet(); Integer[] arr = keys.toArray(new Integer[0]); for (int i = 0; i < arr.length; i++) { assertEquals(new Integer(i + 1), arr[i]); } }

Hier machen wir einfach einen rudimentären, nicht abschließenden Test zur Reihenfolge der Einträge in der verknüpften Hash-Map.

Wir können garantieren, dass dieser Test immer bestanden wird, da die Einfügereihenfolge immer beibehalten wird. Wir können nicht die gleiche Garantie für eine HashMap übernehmen.

Dieses Attribut kann in einer API von großem Vorteil sein, die eine beliebige Karte empfängt, eine Kopie zum Bearbeiten erstellt und diese an den aufrufenden Code zurückgibt. Wenn der Client die zurückgegebene Karte vor dem Aufrufen der API auf dieselbe Weise bestellen muss, ist eine verknüpfte Hashmap der richtige Weg.

Die Einfügereihenfolge wird nicht beeinflusst, wenn ein Schlüssel erneut in die Karte eingefügt wird.

4. Access-Order LinkedHashMap

LinkedHashMap bietet einen speziellen Konstruktor, mit dem wir unter dem benutzerdefinierten Auslastungsfaktor (LF) und der Anfangskapazität einen anderen Bestellmechanismus / eine andere Bestellstrategie angeben können, die als Zugriffsreihenfolge bezeichnet wird :

LinkedHashMap map = new LinkedHashMap(16, .75f, true);

Der erste Parameter ist die Anfangskapazität, gefolgt vom Lastfaktor, und der letzte Parameter ist der Bestellmodus . Durch die Übergabe von true haben wir die Zugriffsreihenfolge aktiviert, während die Standardeinstellung die Einfügereihenfolge war.

Dieser Mechanismus stellt sicher, dass die Reihenfolge der Iteration von Elementen die Reihenfolge ist, in der zuletzt auf die Elemente zugegriffen wurde, vom zuletzt aufgerufenen bis zum zuletzt aufgerufenen.

Das Erstellen eines LRU-Caches (Least Recent Used) ist mit dieser Art von Karte recht einfach und praktisch. Eine erfolgreiche Put- oder Get- Operation führt zu einem Zugriff auf den Eintrag:

@Test public void givenLinkedHashMap_whenAccessOrderWorks_thenCorrect() { LinkedHashMap map = new LinkedHashMap(16, .75f, true); map.put(1, null); map.put(2, null); map.put(3, null); map.put(4, null); map.put(5, null); Set keys = map.keySet(); assertEquals("[1, 2, 3, 4, 5]", keys.toString()); map.get(4); assertEquals("[1, 2, 3, 5, 4]", keys.toString()); map.get(1); assertEquals("[2, 3, 5, 4, 1]", keys.toString()); map.get(3); assertEquals("[2, 5, 4, 1, 3]", keys.toString()); }

Beachten Sie, wie sich die Reihenfolge der Elemente im Schlüsselsatz ändert, wenn wir Zugriffsoperationen auf der Karte ausführen.

Einfach ausgedrückt führt jede Zugriffsoperation auf der Karte zu einer Reihenfolge, in der das Element, auf das zugegriffen wurde, als letztes angezeigt wird, wenn eine Iteration sofort ausgeführt wird.

Nach den obigen Beispielen sollte es offensichtlich sein, dass eine putAll- Operation einen Eintragszugriff für jede der Zuordnungen in der angegebenen Zuordnung generiert.

Natürlich hat die Iteration über eine Ansicht der Karte keinen Einfluss auf die Reihenfolge der Iteration der Hintergrundkarte. Nur explizite Zugriffsvorgänge auf der Karte wirken sich auf die Reihenfolge aus .

LinkedHashMap bietet auch einen Mechanismus zum Verwalten einer festen Anzahl von Zuordnungen und zum Löschen der ältesten Einträge, falls neue hinzugefügt werden müssen.

Die removeEldestEntry- Methode wird möglicherweise überschrieben, um diese Richtlinie zum automatischen Entfernen veralteter Zuordnungen durchzusetzen.

Um dies in der Praxis zu sehen, erstellen wir unsere eigene verknüpfte Hash-Map-Klasse, um das Entfernen veralteter Zuordnungen durch Erweitern von LinkedHashMap zu erzwingen :

public class MyLinkedHashMap extends LinkedHashMap { private static final int MAX_ENTRIES = 5; public MyLinkedHashMap( int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor, accessOrder); } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > MAX_ENTRIES; } }

Unsere obige Überschreibung ermöglicht es der Karte, auf eine maximale Größe von 5 Einträgen zu wachsen. Wenn die Größe diesen Wert überschreitet, wird jeder neue Eintrag auf Kosten des Verlusts des ältesten Eintrags in der Karte eingefügt, dh des Eintrags, dessen letzte Zugriffszeit vor allen anderen Einträgen liegt:

@Test public void givenLinkedHashMap_whenRemovesEldestEntry_thenCorrect() { LinkedHashMap map = new MyLinkedHashMap(16, .75f, true); map.put(1, null); map.put(2, null); map.put(3, null); map.put(4, null); map.put(5, null); Set keys = map.keySet(); assertEquals("[1, 2, 3, 4, 5]", keys.toString()); map.put(6, null); assertEquals("[2, 3, 4, 5, 6]", keys.toString()); map.put(7, null); assertEquals("[3, 4, 5, 6, 7]", keys.toString()); map.put(8, null); assertEquals("[4, 5, 6, 7, 8]", keys.toString()); }

Beachten Sie, dass die ältesten Einträge am Anfang des Schlüsselsatzes immer wieder abfallen, wenn wir der Karte neue hinzufügen.

5. Überlegungen zur Leistung

Genau wie HashMap führt LinkedHashMap die grundlegenden Map- Operationen zum Hinzufügen, Entfernen und Enthalten in konstanter Zeit aus, solange die Hash-Funktion gut dimensioniert ist. Es werden auch ein Nullschlüssel sowie Nullwerte akzeptiert.

Diese zeitkonstante Leistung von LinkedHashMap ist jedoch wahrscheinlich etwas schlechter als die zeitkonstante Leistung von HashMap, da die Verwaltung einer doppelt verknüpften Liste zusätzlichen Aufwand bedeutet.

Iteration over collection views of LinkedHashMap also takes linear time O(n) similar to that of HashMap. On the flip side,LinkedHashMap‘s linear time performance during iteration is better than HashMap‘s linear time.

This is because, for LinkedHashMap, n in O(n) is only the number of entries in the map regardless of the capacity. Whereas, for HashMap, n is capacity and the size summed up, O(size+capacity).

Load Factor and Initial Capacity are defined precisely as for HashMap. Note, however, that the penalty for choosing an excessively high value for initial capacity is less severe for LinkedHashMap than for HashMap, as iteration times for this class are unaffected by capacity.

6. Concurrency

Just like HashMap, LinkedHashMap implementation is not synchronized. So if you are going to access it from multiple threads and at least one of these threads is likely to change it structurally, then it must be externally synchronized.

It's best to do this at creation:

Map m = Collections.synchronizedMap(new LinkedHashMap());

The difference with HashMap lies in what entails a structural modification. In access-ordered linked hash maps, merely calling the get API results in a structural modification. Alongside this, are operations like put and remove.

7. Conclusion

In this article, we have explored Java LinkedHashMap class as one of the foremost implementations of Map interface in terms of usage. We have also explored its internal workings in terms of the difference from HashMap which is its superclass.

Hopefully, after having read this post, you can make more informed and effective decisions as to which Map implementation to employ in your use case.

Der vollständige Quellcode für alle in diesem Artikel verwendeten Beispiele befindet sich im GitHub-Projekt.