Java: Itération à travers un HashMap, qui est plus efficace?

Question

Étant donné le code suivant, avec deux façons de le parcourir,
existe-t-il une différence de performance entre ces deux méthodes?

 Map<String, Integer> map = new HashMap<String, Integer>(); 
     //populate map 

     //alt. #1 
     for (String key : map.keySet()) 
     { 
      Integer value = map.get(key); 
      //use key and value 
     } 

     //alt. #2 
     for (Map.Entry<String, Integer> entry : map.entrySet()) 
     { 
      String key = entry.getKey(); 
      Integer value = entry.getValue(); 
      //use key and value 
     } 

Je suis enclin à penser que alt. #2 est le plus efficace des moyens de itérer à travers l'ensemble map (mais je peux me tromper)

Answer 1

Vos secondes options sont nettement plus efficaces puisque vous ne faites qu'une recherche par rapport à n nombre de fois dans la première option.

Mais, rien ne vaut mieux que de l'essayer quand vous le pouvez.Voici donc ce qu'il -

(Pas assez parfait, mais bon de vérifier les hypothèses et sur ma machine de toute façon)

public static void main(String args[]) { 

    Map<String, Integer> map = new HashMap<String, Integer>(); 
    // populate map 

    int mapSize = 500000; 
    int strLength = 5; 
    for(int i=0;i<mapSize;i++) 
     map.put(RandomStringUtils.random(strLength), RandomUtils.nextInt()); 

    long start = System.currentTimeMillis(); 
    // alt. #1 
    for (String key : map.keySet()) { 
     Integer value = map.get(key); 
     // use key and value 
    } 
    System.out.println("Alt #1 took "+(System.currentTimeMillis()-start)+" ms"); 

    start = System.currentTimeMillis(); 
    // alt. #2 
    for (Map.Entry<String, Integer> entry : map.entrySet()) { 
     String key = entry.getKey(); 
     Integer value = entry.getValue(); 
     // use key and value 
    } 
    System.out.println("Alt #2 took "+(System.currentTimeMillis()-start)+" ms"); 
} 

RÉSULTATS (Des quelques intéressants)

Avec int mapSize = 5000; int strLength = 5;
Alt # 1 a pris 26 ms
L'Alt n ° 2 a pris 20 ms

Avec int mapSize = 50000; int strLength = 5;
Alt # 1 a 32 ms
Alt # 2 a pris 20 ms

Avec int mapSize = 50000; int strLength = 50;
Alt # 1 a eu 22 ms
Alt # 2 a 21 ms

Avec int mapSize = 50000; int strLength = 500;
Alt # 1 a pris 28 ms
Alt # 2 a 23 ms

Avec int mapSize = 500000; int strLength = 5;
Alt # 1 a pris 92 ms
Alt # 2 a 57 ms

... et ainsi de suite

Answer 2

Le deuxième extrait sera un peu plus rapide, car il ne besoin de re-rechercher les clés.

Tous les itérateurs HashMap appellent le nextEntry method, ce qui renvoie un Entry<K,V>.

Votre premier extrait supprime la valeur de l'entrée (dans KeyIterator), puis la recherche à nouveau dans le dictionnaire.

Votre deuxième extrait utilise la clé et la valeur directement (à partir EntryIterator)

(Les deux keySet() et entrySet() sont des appels bon marché)

Answer 3

Ce dernier est plus efficace que l'ancien. Un outil comme FindBugs marquera le premier et vous suggérera de faire le dernier.

Answer 4

bguiz,

Je pense (je ne sais pas) que l'itérer entrySet (variante 2) est légèrement plus efficace, tout simplement parce qu'il ne hachage pas chaque clé afin d'obtenir sa valeur ... Cela dit, le calcul du hachage est une opération O (1) par entrée, et donc nous ne parlons que de O (n) sur l'ensemble HashMap ... mais notez que tout cela s'applique à HashMap seulement ... autres implémentations de Map peut avoir des caractéristiques de performance TRES différentes.

Je pense que vous seriez en train de "pousser" pour réellement AVISER la différence de performance. Si vous êtes concerné alors pourquoi ne pas configurer un test-case pour chronométrer les deux techniques d'itération?

Si vous n'avez pas de problèmes de performance REAL, vous vous inquiétez pas vraiment ... Quelques pas d'horloge ici et là n'affecteront pas la convivialité globale de votre programme. Je crois que beaucoup, beaucoup d'autres aspects du code sont typiquement plus importants que la performance pure et simple. Bien sûr, certains blocs sont "critiques de performance", et ceci est connu AVANT que cela ne soit écrit, seul test de performance a été fait ... mais de tels cas sont assez rares. En règle générale, il est préférable de se concentrer sur l'écriture de codes complets, corrects, flexibles, testables, réutilisables, lisibles et maintenables. La performance peut être intégrée plus tard, selon les besoins.

La version 0 doit être aussi simple que possible, sans aucune "optimisation".

Answer 5

En général, le second serait un peu plus rapide pour un HashMap. L'appel get(key) devient plus lent que O(1) - il obtient O(k) avec k étant le nombre d'entrées dans le même compartiment (ie le nombre de clés avec le même code de hachage ou un autre code de hachage qui est toujours mappé sur le même seau - cela dépend aussi de la capacité, de la taille et du facteur de charge de la carte).

La variante Entry-itération n'a pas à effectuer la recherche, elle est donc un peu plus rapide ici.

Une autre remarque: Si la capacité de votre carte est beaucoup plus grande que la taille réelle et que vous utilisez beaucoup d'itérations, vous pouvez utiliser LinkedHashMap à la place. Il fournit O(size) à la place O(size+capacity) complexité pour une itération complète (ainsi qu'un ordre d'itération prévisible). (Vous devriez toujours mesurer si cela donne vraiment une amélioration, puisque les facteurs peuvent varier LinkedHashMap a un plus grand frais généraux pour la création de la carte..)

Answer 6

Carte:

Map<String, Integer> map = new HashMap<String, Integer>();

Outre les 2 options, il est un de plus.

1) keySet() - l'utiliser si vous avez besoin d'utiliser uniquement les clés

for (String k : map.keySet()) { 
    ... 
} 

2) entrySet() - l'utiliser si vous avez besoin des deux: clés & valeurs

for (Map.Entry<String, Integer> entry : map.entrySet()) { 
    String k = entry.getKey(); 
    Integer v = entry.getValue(); 
    ... 
} 

3) valeurs() - l'utiliser si vous avez besoin seulement les valeurs

for (Integer v : map.values()) { 
    ... 
}