Java: Itération via une carte de hachage, qui est plus efficace?

Question

Étant donné le code suivant, avec deux manières alternatives 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 moyen le plus efficace de parcourir tout le map (mais je peux me tromper)

Answer 1

Vos options de seconde est nettement plus efficace puisque vous faites une recherche qu'une seule fois par rapport à un nombre n de fois dans la première option.

Mais, rien ne colle mieux que de l'essayer quand vous le pouvez. Donc, ici, va -

(Pas parfait mais assez bonne pour 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");
}

Les RÉSULTATS (Certains intéressantes)

Avec int mapSize = 5000; int strLength = 5;
Alt #1 a eu 26 ms
Alt #2 a pris 20 ms

Avec int mapSize = 50000; int strLength = 5;
Alt #1 a eu 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 eu 28 ms
Alt #2 a 23 ms

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

...et ainsi de suite

Answer 2

Le deuxième extrait sera légèrement plus rapide, car il n'a pas besoin de re-regarder les touches.

Tous HashMap des itérateurs d'appel de l' nextEntry méthode, qui renvoie un Entry<K,V>.

Votre premier extrait de rejet de la valeur de l'entrée (en KeyIterator), puis regarde de nouveau dans le dictionnaire.

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

(Les deux keySet() et entrySet() sont des appels à bas prix)

Answer 3

Totalement prématuré de l'optimisation mais alt #2 est probablement plus efficace que se cache une étape supplémentaire dans alt n ° 1 de la récupération de la liste de clés.

EDIT:

En fait, en regardant la source de l' HashMap d'une classe, il semble que alt #2 devrait être un peu plus rapide (quand on parle de nano secondes).

Avec #alt 1 vous d'abord récupérer la clé O(1) et ensuite une boucle sur chaque clé et récupérer la valeur de la Carte qui est "O(1)" aussi, mais il y a une table de hachage calcul effectué pour chaque clé.

Avec #alt 2 vous récupérer à l'entrée de la valeur O(1) et ensuite une boucle sur chaque entrée et récupérer la valeur de chaque Entrée qui est O(1) aussi, sans le calcul de hachage sur chaque boucle.

Answer 4

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

Answer 5

bguiz,

Je pense (je ne sais pas) que l'itération de la EntrySet (variante 2) est légèrement plus efficace, tout simplement parce qu'il n'a pas de hachage de chaque clé pour obtenir sa valeur... cela dit, le calcul de la valeur de hachage est un O(1) opération par entrée, et donc nous ne sommes qu'à parler O(n) sur l'ensemble de l' HashMap... mais notez que tout cela s'applique à l' HashMap seulement... d'autres implémentations de Map peuvent être TRÈS différentes caractéristiques de performance.

Je ne pense que vous auriez du être "poussant" à fait de l'AVIS de l'écart de performance. Si vous êtes intéressé, alors pourquoi ne pas l'installation d'un test à la fois itération techniques?

Si vous n'avez pas un RÉEL, a rapporté problème de performances, alors vous êtes vraiment se soucier de ne pas très bien... Un peu de tops d'horloge ici et il n'y aura pas d'impact sur la facilité d'utilisation de votre programme.

Je crois que beaucoup, beaucoup d'autres aspects du code sont généralement plus importants que simplement la performance. Bien sûr, certains de ces blocs sont "critique pour les performances", et ceci est connu AVANT, il est même écrit, laissez-le seul de la performance à l'épreuve..., mais ces cas sont assez rares. Comme approche générale, il est préférable de se concentrer sur l'écriture complète, correcte, flexible, testable, réutilisable, lisible, maintenable code... de la performance PEUT être construit un peu plus tard, en tant que de besoin.

Version 0 devrait être aussi SIMPLE QUE POSSIBLE, sans aucune "optimisations".