iter - new map java




Considérations de performance pour keySet() et entrySet() de Map (2)

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 qui seraient nécessaires lors de l'utilisation de keySet () et get (). Mais ce serait génial 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.


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

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 jeu de clés, la méthode map.get() est appelée, ce qui - dans le cas d'un HashMap - nécessite que les méthodes hashCode() et equals() de l'objet clé soient évaluées pour 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 à obtenir est O (log2 (n)), ie le comparateur de will peut avoir besoin de lancer 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 que les hashCode() et equals() soient appelées.


Tout d'abord, cela dépend entièrement du type de carte que vous utilisez. Mais puisque le fil 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 d'API standard de Sun / Oracle.

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

L'itération sur les vues de collection d'un LinkedHashMap nécessite un temps proportionnel à la taille de la carte, quelle que soit sa capacité. L'itération sur une HashMap est susceptible d'être plus coûteuse, nécessitant 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;
    }

    // ...
}

Donc là vous l'avez ... C'est le code qui dicte ce qui va se passer quand vous itérez à travers un entrySet. Il parcourt tout le tableau qui est aussi long que la capacité des cartes.

HashMap.keySet () et .get ()

Ici, vous devez d'abord vous procurer l'ensemble des clés. Cela prend du temps proportionnel à la capacité de la carte (par opposition à la taille de la 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 du temps constant. Cependant, il faudra inévitablement beaucoup d' .hashCode et .equals , ce qui prendra évidemment plus de temps que de simplement faire un appel entry.value() .







collections