HashMap ou TreeMap ou LinkedHashMap lequel est plus rapide à parcourir?

J'ai un Map qui est rempli jusqu'au démarrage de l'application. Il ne change plus tard au cours de l'exécution de l'application. Plus tard, cette carte est uniquement utilisé pour itérer sur tous les éléments. Concrètes de mise en œuvre de Map devrais-je choisir? HashMap ou TreeMap ou LinkedHashMap ?
Mise à JOUR
Ordre d'Insertion n'a pas d'importance. La seule chose qui importe, c'est rapide itération de tous les éléments (disons 6000 éléments).

source d'informationauteur Mac | 2013-07-28

  1. 5

    Aucune des autres réponses ici de prendre en considération les effets de cache du PROCESSEUR, ce qui peut être énorme lors de l'itération.

    Un moyen de l'améliorer est d'utiliser un unique tableau de entrelacés de clés et de valeurs (clés à même les indices, les valeurs à impairs). Ce sera étroitement groupe ensemble de ces éléments de données et de maximiser l'effet de levier le cache, au moins pour les références.

    Mais de la vraie, de crier, d'amélioration qui serait obtenu si vous pouviez éviter de créer des objets dont la conservation de vos données et de les utiliser seulement des tableaux de valeurs primitives. C'est, naturellement, dépend fortement de votre cas d'utilisation.

  2. 9

    HashMap sera généralement plus rapide, puisqu'il a le meilleur comportement du cache (HashMap itère directement sur le support de tableau, alors que TreeMap et LinkedHashMap parcourir liés à des structures de données).

    Vous souhaiterez peut-être utiliser un ImmutableMap ou UnmodifiableMap si la carte ne va pas changer une fois qu'il est initialisé

  3. 3

    Si votre carte est utilisée que pour effectuer une itération sur les éléments et la vitesse de répétition est importante, puis de convertir la carte dans une liste de tableaux et d'itérer sur elle, ce sera le moyen le plus rapide.

  4. 3

    Je ne voudrais pas utiliser la carte. Si tout ce que vous voulez, c'est de parcourir les entrées de faire une nouvelle ArrayList de ce que vous avez besoin et que vous ne pouvez pas obtenir plus vite qu'un ArrayList pour l'itération.

    //Which map you use only chooses the order of the list.
Map<Key,Value> map = new HashMap<>();
//The list to iterate for maximum speed.
List<Map.Entry<Key,Value>> list = new ArrayList<>(map.entrySet());

    De cette façon, vous itérer à travers l'entrée de la valeur juste une fois pour créer la liste. À partir de là que vous itération à travers la liste encore et encore - qui devrait certainement être proche de l'optimal.

    Note Changé de LinkedList à ArrayList sur Marko suggestion.

  5. 1

    Je suis d'accord avec Zim-Zam réponse, et d'ajouter quelque chose: si vous avez besoin d'accéder à la fois le clés et la valeurs cours de l'itération, le moyen le plus rapide est d'utiliser le entrySet() méthode, tel que discuté ici.

    Maintenant, si vous êtes sûr que la carte n'est jamais va changer, pourquoi ne pas utiliser une structure de données distincte pour l'itération? par exemple: itérer une fois sur la carte et de le remplir avec le contenu d'un couple de tableaux, l'un avec les touches et l'autre avec les valeurs, dans les mêmes positions correspondantes. Puis traversée de ces tableaux sera aussi vite qu'elle peut obtenir.

  6. -2

    La Carte.forEach(BiConsumer) est presque toujours plus rapide que les Itérateurs, parfois, par une grande marge. Si vous avez été en additionnant les valeurs par exemple:

    public class TestForStackOverflow {
    int sum = 0;

    //Or whatever Map you are using
    Map<Object, Integer> map = new HashMap();

    static class C implements BiConsumer<Object, Integer> {
        int sum = 0;

        @Override
        public void accept(Object k, Integer v) {
            sum += v;
        }
    }

    public int getSum(Map map) {
        C c = new C();
        map.forEach(c);
        return c.sum;
    }

    public int getSum2(Map map) {
        map.forEach((k, v) -> sum += v);
        return sum;
    }
}