Considérations de performances pour keySet () et entrySet () de Map

Tout,

Quelqu’un peut-il s’il vous plaît laissez-moi savoir exactement quels sont les problèmes de performance entre les 2? Le site: CodeRanch fournit un bref aperçu des appels internes nécessaires pour utiliser keySet () et get (). Mais ce serait bien si quelqu’un pouvait fournir des détails exacts sur le stream lorsque les méthodes keySet () et get () sont utilisées. Cela m’aiderait à mieux comprendre les problèmes de performance.

Tout d’abord, cela dépend entièrement du type de carte que vous utilisez. Mais puisque le thread JavaRanch parle de HashMap, je suppose que c’est l’implémentation à laquelle vous faites référence. Et supposons également que vous parlez de l’implémentation standard de l’API de Sun / Oracle.

Deuxièmement, si vous êtes préoccupé par les performances lors d’une itération sur votre carte de hachage, je vous suggère de regarder LinkedHashMap . De la documentation:

L’itération sur les vues de collection d’un LinkedHashMap nécessite du temps proportionnel à la taille de la carte, quelle que soit sa capacité. L’itération sur un HashMap risque d’être plus coûteuse, nécessitant du temps proportionnel à sa capacité.

HashMap.entrySet ()

Le code source de cette implémentation est disponible. L’implémentation renvoie simplement un nouveau HashMap.EntrySet . Une classe qui ressemble à ceci:

 private final class EntrySet extends AbstractSet> { public Iterator> iterator() { return newEntryIterator(); // returns a HashIterator... } // ... } 

et un HashIterator ressemble à

 private abstract class HashIterator implements Iterator { Entry next; // next entry to return int expectedModCount; // For fast-fail int index; // current slot Entry current; // current entry HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } } final Entry nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry e = next; if (e == null) throw new NoSuchElementException(); if ((next = e.next) == null) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } current = e; return e; } // ... } 

Donc voilà, c'est le code qui dicte ce qui va se passer lorsque vous parcourez un entrySet. Il parcourt tout le tableau aussi longtemps que la capacité des cartes.

HashMap.keySet () et .get ()

Ici, vous devez d'abord saisir l'ensemble des clés. Cela prend du temps proportionnel à la capacité de la carte (par opposition à la taille de LinkedHashMap). Après cela, vous appelez get() une fois pour chaque clé. Bien sûr, dans le cas moyen, avec une bonne implémentation de hashCode, cela prend un temps constant. Cependant, cela nécessitera inévitablement beaucoup d' .hashCode et .equals , ce qui prendra évidemment plus de temps que de faire un appel entry.value() .

Le cas le plus courant où l’utilisation de entrySet est préférable à keySet est lorsque vous parcourez toutes les paires clé / valeur dans une map.

Ceci est plus efficace:

 for (Map.Entry entry : map.entrySet()) { Object key = entry.getKey(); Object value = entry.getValue(); } 

que:

 for (Object key : map.keySet()) { Object value = map.get(key); } 

Parce que dans le second cas, pour chaque clé du keySet, la méthode map.get() est appelée, ce qui – dans le cas d’un HashMap – exige que les méthodes hashCode() et equals() de l’object clé soient évaluées dans l’ordre pour trouver la valeur associée *. Dans le premier cas, le travail supplémentaire est éliminé.

Edit: Cela est encore pire si vous considérez un TreeMap, où un appel à obtenir est O (log2 (n)), c.-à-d. Que le comparateur pour will peut avoir besoin d’exécuter log2 (n) fois (n = taille de la carte) avant de trouver la valeur associée.

* Certaines implémentations Map ont des optimisations internes qui vérifient l’identité des objects avant que les hashCode() et equals() soient appelés.

Voici le lien vers un article comparant les performances de entrySet() , keySet() et values() , et des conseils concernant l’utilisation de chaque approche.

Apparemment, l’utilisation de keySet() est plus rapide (en plus d’être plus pratique) que entrySet() tant que vous n’avez pas besoin de Map.get() les valeurs.