Considérations sur les performances de keySet() et entrySet() de Map

Question

Tous,

Quelqu'un peut-il me dire exactement quels sont les problèmes de performance entre les deux ? Le site : CodeRanch donne un bref aperçu des appels internes qui seraient nécessaires lors de l'utilisation de keySet() et get(). Mais ce serait formidable si quelqu'un pouvait fournir des détails exacts sur le flux lorsque les méthodes keySet() et get() sont utilisées. Cela m'aiderait à mieux comprendre les problèmes de performance.

Answer 1

Le cas le plus courant où il est préférable d'utiliser entrySet plutôt que keySet est celui où vous parcourez par itération toutes les paires clé/valeur d'une Map.

C'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, l'élément map.get() est appelée, ce qui - dans le cas d'un HashMap - nécessite que la méthode hashCode() y equals() les méthodes de l'objet clé sont évaluées afin de trouver la valeur associée*. Dans le premier cas, ce travail supplémentaire est éliminé.

Edit : C'est encore pire si vous considérez un TreeMap, où un appel à get est O(log2(n)), c'est-à-dire que le comparateur pour will peut avoir besoin de s'exécuter log2(n) fois (n = taille de la Map) avant de trouver la valeur associée.

*Certaines implémentations de Map ont des optimisations internes qui vérifient l'identité des objets avant l'exécution de l'opération. hashCode() y equals() sont appelés.

Answer 2

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

Deuxièmement, si vous êtes préoccupé par les performances lors de l'itération dans votre carte de hachage, je vous suggère de jeter un coup d'oeil à LinkedHashMap . Dans la documentation :

L'itération sur les vues de la collection d'une LinkedHashMap nécessite un temps proportionnel à la taille de la carte, quelle que soit sa capacité. L'itération sur une HashMap sera probablement plus coûteuse et nécessitera un temps proportionnel à sa capacité.

HashMap.entrySet()

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

private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return newEntryIterator(); // returns a HashIterator...
    }
    // ...
}

et un HashIterator ressemble à

private abstract class HashIterator<E> implements Iterator<E> {
    Entry<K,V> next;    // next entry to return
    int expectedModCount;   // For fast-fail
    int index;      // current slot
    Entry<K,V> 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<K,V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Entry<K,V> 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;
    }

    // ...
}

Et voilà... C'est le code qui dicte ce qui va se passer lorsque vous itérez dans un entrySet. Il parcourt le tableau entier qui est aussi long que la capacité des cartes.

HashMap.keySet() et .get()

Ici, vous devez d'abord vous procurer le jeu de clés. Cela prend un temps proportionnel à la capacité de la carte (par opposition à taille pour le LinkedHashMap). Une fois cette opération effectuée, 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 de temps d'exécution. .hashCode y .equals ce qui prendra évidemment plus de temps que de simplement faire un entry.value() appeler.

Answer 3

Voici le lien vers un article comparer les performances de entrySet() , keySet() y values() et des conseils pour savoir quand utiliser 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.