Un guide de LinkedHashMap en Java

1. Vue d'ensemble

Dans cet article, nous allons explorer l'implémentation interne de la classe LinkedHashMap . LinkedHashMap est une implémentation courante de l' interface Map .

Cette implémentation particulière est une sous-classe de HashMap et partage donc les blocs de construction de base de l' implémentation de HashMap . Par conséquent, il est fortement recommandé de réviser cela avant de poursuivre cet article.

2. LinkedHashMap vs HashMap

La classe LinkedHashMap est très similaire à HashMap dans la plupart des aspects. Cependant, la carte de hachage liée est basée à la fois sur la table de hachage et la liste liée pour améliorer les fonctionnalités de la carte de hachage.

Il maintient une liste à double lien parcourant toutes ses entrées en plus d'un tableau sous-jacent de taille par défaut 16.

Pour maintenir l'ordre des éléments, les modifie HashMap liés à la Map.Entry classe de HashMap en ajoutant des pointeurs vers les entrées suivantes et précédentes:

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

Notez que la classe Entry ajoute simplement deux pointeurs; avant et après, lui permettre de se connecter à la liste chaînée. En dehors de cela, il utilise l' implémentation de la classe Entry d'un HashMap.

Enfin, rappelez-vous que cette liste chaînée définit l'ordre d'itération, qui par défaut est l'ordre d'insertion des éléments (ordre d'insertion).

3. LinkedHashMap d' ordre d' insertion

Jetons un coup d'œil à une instance de carte de hachage liée qui classe ses entrées en fonction de la manière dont elles sont insérées dans la carte. Il garantit également que cet ordre sera maintenu tout au long du cycle de vie de la carte:

@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]); } }

Ici, nous faisons simplement un test rudimentaire et non concluant sur l'ordre des entrées dans la carte de hachage liée.

Nous pouvons garantir que ce test réussira toujours car l'ordre d'insertion sera toujours maintenu. Nous ne pouvons pas faire la même garantie pour un HashMap.

Cet attribut peut être d'un grand avantage dans une API qui reçoit n'importe quelle carte, fait une copie à manipuler et la renvoie au code appelant. Si le client a besoin que la carte retournée soit ordonnée de la même manière avant d'appeler l'API, une carte de hachage liée est la solution.

L'ordre d'insertion n'est pas affecté si une clé est réinsérée dans la carte.

4. LinkedHashMap d' ordre d' accès

LinkedHashMap fournit un constructeur spécial qui nous permet de spécifier, parmi le facteur de charge personnalisé (LF) et la capacité initiale, un mécanisme / stratégie de commande différent appelé ordre d'accès :

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

Le premier paramètre est la capacité initiale, suivie du facteur de charge et le dernier paramètre est le mode de commande . Donc, en passant true , nous avons activé l'ordre d'accès, alors que la valeur par défaut était l'ordre d'insertion.

Ce mécanisme garantit que l'ordre d'itération des éléments est l'ordre dans lequel les éléments ont été accédés pour la dernière fois, du moins récemment accédé au plus récemment accédé.

Et donc, créer un cache LRU (Least Recent Used) est assez simple et pratique avec ce type de carte. Une opération put ou get réussie entraîne un accès pour l'entrée:

@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()); }

Remarquez comment l'ordre des éléments dans le jeu de clés est transformé lorsque nous effectuons des opérations d'accès sur la carte.

En termes simples, toute opération d'accès sur la carte se traduit par un ordre tel que l'élément auquel on accède apparaîtrait en dernier si une itération devait être effectuée immédiatement.

Après les exemples ci-dessus, il devrait être évident qu'une opération putAll génère un accès d'entrée pour chacun des mappages dans la carte spécifiée.

Naturellement, l'itération sur une vue de la carte n'affecte pas l'ordre d'itération de la carte de support; seules les opérations d'accès explicites sur la carte affecteront l'ordre .

LinkedHashMap fournit également un mécanisme pour maintenir un nombre fixe de mappages et pour continuer à déposer les entrées les plus anciennes au cas où une nouvelle devrait être ajoutée.

The removeEldestEntry method may be overridden to enforce this policy for removing stale mappings automatically.

To see this in practice, let us create our own linked hash map class, for the sole purpose of enforcing the removal of stale mappings by extending LinkedHashMap:

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; } }

Our override above will allow the map to grow to a maximum size of 5 entries. When the size exceeds that, each new entry will be inserted at the cost of losing the eldest entry in the map i.e. the entry whose last-access time precedes all the other entries:

@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()); }

Notice how oldest entries at the start of the key set keep dropping off as we add new ones to the map.

5. Performance Considerations

Just like HashMap, LinkedHashMap performs the basic Map operations of add, remove and contains in constant-time, as long as the hash function is well-dimensioned. It also accepts a null key as well as null values.

However, this constant-time performance of LinkedHashMap is likely to be a little worse than the constant-time of HashMap due to the added overhead of maintaining a doubly-linked list.

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.

Le code source complet de tous les exemples utilisés dans cet article se trouve dans le projet GitHub.