Différence entre HashMap, LinkedHashMap et TreeMap

je préfère une présentation visuelle:

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
║   Property   ║       HashMap       ║      TreeMap      ║     LinkedHashMap   ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║ Iteration    ║  no guarantee order ║ sorted according  ║                     ║
║   Order      ║ will remain constant║ to the natural    ║    insertion-order  ║
║              ║      over time      ║    ordering       ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║  Get/put     ║                     ║                   ║                     ║
║   remove     ║         O(1)        ║      O(log(n))    ║         O(1)        ║
║ containsKey  ║                     ║                   ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║   NavigableMap    ║                     ║
║  Interfaces  ║         Map         ║       Map         ║         Map         ║
║              ║                     ║    SortedMap      ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║                   ║                     ║
║     Null     ║       allowed       ║    only values    ║       allowed       ║
║ values/keys  ║                     ║                   ║                     ║
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
║              ║   Fail-fast behavior of an iterator cannot be guaranteed      ║
║   Fail-fast  ║ impossible to make any hard guarantees in the presence of     ║
║   behavior   ║           unsynchronized concurrent modification              ║
╠══════════════╬═════════════════════╦═══════════════════╦═════════════════════╣
║              ║                     ║                   ║                     ║
║Implementation║      buckets        ║   Red-Black Tree  ║    double-linked    ║
║              ║                     ║                   ║       buckets       ║
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
║      Is      ║                                                               ║
║ synchronized ║              implementation is not synchronized               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

tous les trois représentent la cartographie à partir de clés uniques aux valeurs, et donc mettre en œuvre la carte interface.

1. HashMap est une carte basée sur hashing des clés. Il prend en charge O(1) get/put opérations. Les clés doivent avoir implémentations cohérentes de hashCode() et equals() pour que cela fonctionne.

2. LinkedHashMap is très similaire à HashMap, mais il ajoute une prise de conscience à l'ordre dans lequel les éléments sont ajoutés (ou consultés), de sorte que l'ordre d'itération est le même que l'ordre d'insertion (ou l'ordre d'accès, selon les paramètres de construction).

3. TreeMap est un arbre en fonction de la cartographie. Ses opérations put / get prennent du temps (log n). Il exige des articles d'avoir un certain mécanisme de comparaison, soit avec Comparable ou de comparaison. L'itération ordre est déterminé par ce mécanisme.

voir où chaque classe se trouve dans la hiérarchie des classes dans le diagramme suivant ( plus grand ). TreeMap met en œuvre SortedMap et NavigableMap tandis que HashMap ne le fait pas.

HashTable est obsolète et la classe correspondante ConcurrentHashMap doit être utilisée.

table de hachage

• Il a une paire de valeurs(clés,valeurs)
• PAS de duplication des valeurs de clé
• Non classé non trié
• permet une clé nulle et plus d'une valeur nulle

table de hachage

• identique à la carte de hachage
• il ne permet pas les clés nulles et les valeurs nulles

LinkedHashMap

• Il est ordonné à la version de la carte de mise en œuvre
• basé sur la liste liée et les structures de données de hachage

TreeMap

• version commandée et sortée
• basé sur des structures de données de hachage

encore quelques données de ma propre expérience avec les cartes, sur le moment où j'utiliserais chacune:

• HashMap - le plus utile dans la recherche d'une implémentation (rapide) de la meilleure performance.
• TreeMap (SortedMap interface) - le plus utile lorsque je suis concerné par la possibilité de trier ou itérer sur les touches dans un ordre particulier que je définit.
• LinkedHashMap-combine les avantages de la commande garantie de TreeMap sans l'augmentation du coût d'entretien de la rampe D'arbres. (Il est presque aussi rapide que le HashMap). En particulier, le LinkedHashMap fournit également un excellent point de départ pour créer un objet Cache en supplantant la méthode removeEldestEntry() . Cela vous permet de créer un objet Cache qui peut expirer des données en utilisant certains critères que vous définissez.

les trois classes HashMap , TreeMap et LinkedHashMap implémente java.util.Map interface, et représente la cartographie à partir de la clé unique aux valeurs.

table de hachage

1. Un HashMap contient des valeurs basées sur la touche.

2. il ne contient que des éléments uniques.

3. il peut y avoir une clé nulle et plusieurs valeurs nulles.

4. Il affirme aucune commande .

   public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

LinkedHashMap

1. Un LinkedHashMap contient des valeurs basées sur la touche.
2. Il ne contient que des éléments uniques.
3. il peut avoir une clé nulle et des valeurs nulles multiples.

4. C'est le même que HashMap affirme au contraire ordre d'insertion . / / voir décélération de classe au-dessous de

   public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

TreeMap

1. Un TreeMap contient des valeurs basées sur la touche. Il implémente L'interface NavigableMap et étend la classe AbstractMap.
2. Il ne contient que des éléments uniques.
3. il ne peut pas avoir la clé nulle mais peut avoir plusieurs valeurs nulles.

4. C'est le même que HashMap affirme au contraire ordre croissant (Triés en utilisant l'ordre naturel de sa clé.).

   public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable

Hashtable

1. un Hashtable est un tableau de liste. Chaque liste est appelée un seau. La position du seau est identifiée en appelant la méthode hashcode (). Un Hashtable contient des valeurs basées sur la clé.
2. Il ne contient que des éléments uniques.
3. il se peut qu'il n'ait pas de clé ou de valeur nulle.
4. Il est synchronisé .

5. il s'agit d'une classe de legs.

   public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, Serializable

Ref: http://javarevisited.blogspot.in/2015/08/difference-between-HashMap-vs-TreeMap-vs-LinkedHashMap-Java.html

HashMap ne garantit absolument pas l'ordre d'itération. Il peut (et va) même changer complètement lorsque de nouveaux éléments sont ajoutés. TreeMap itérera selon l '"ordre naturel" des touches selon leur méthode de compareTo () (ou une Comparateur.) De plus, il implémente L'interface SortedMap, qui contient des méthodes qui dépendent de cet ordre de tri. LinkedHashMap va se répéter dans l'ordre dans lequel les entrées ont été mis dans la carte

regardez comment la performance varie..

Tree map qui est une implémentation de tried map. La complexité de l'opération put, get et containsKey est O (log n) en raison de l'ordre naturel

@Amit: SortedMap est une interface alors que TreeMap est une classe qui implémente l'interface SortedMap . Cela signifie Si suit le protocole qui SortedMap demande à ses exécutants de faire. Un arbre à moins qu'il ne soit implémenté comme arbre de recherche, ne peut pas vous donner des données ordonnées parce que l'arbre peut être n'importe quel type d'arbre. Ainsi, pour faire fonctionner TreeMap comme tried order, il implémente SortedMap(E. G, L'Arbre de recherche binaire-BST, la BST équilibrée comme AVL et L'arbre R-B, Même L'Arbre de recherche ternaire-la plupart du temps utilisé pour les recherches itératives de manière ordonnée).

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements SortedMap<K,V>, Cloneable, Serializable

en coque HashMap : donne les données en O (1) , sans ordre

TreeMap : donne les données en o(log N), base 2. avec des clés commandées

LinkedHashMap : est une table de hachage avec liste liée (pensez à indexed-SkipList) la capacité de stocker des données dans la façon dont elle est insérée dans l'arbre. Le mieux adapté pour mettre en œuvre LRU ( le moins utilisé récemment ).

ce sont des implémentations différentes de la même interface. Chaque implémentation présente des avantages et des inconvénients (insertion rapide, recherche lente) ou vice versa.

Pour plus de détails regardez la javadoc de TreeMap , table de hachage , LinkedHashMap .

ci-dessous sont la différence majeure entre HashMap et TreeMap

1. HashMap ne maintient aucun ordre. En d'autres termes , HashMap ne fournit aucune garantie que l'élément inséré en premier sera imprimé en premier, alors que tout comme TreeSet, les éléments TreeMap sont également triés selon l'ordre naturel de ses éléments

2. mise en œuvre interne de HashMap utilisez le hachage et la chape d'arbre en interne utilise l'application d'Arbre Rouge-Noir.

3. HashMap peut stocker une clé nulle et de nombreuses valeurs nulles.TreeMap ne peut pas contenir de touches null mais peut contenir de nombreuses valeurs null.

4. HashMap constamment prendre le temps de la performance pour les opérations de base comme get et put j'.e O(1).Selon Oracle docs , TreeMap fournit log garanti (n) Le coût de temps pour la méthode get and put.

5. HashMap est beaucoup plus rapide que TreeMap, car le temps de performance de HashMap est constant par rapport au temps log TreeMap pour la plupart des opérations.

6. HashMap utilise la méthode equals() en comparaison tandis que TreeMap utilise la méthode compareTo() pour maintenir l'ordre.

7. HashMap implémente l'interface de Carte tout en TreeMap implémente NavigableMap interface.

ne préserve pas l'ordre d'insertion.

Exemple. Hashmap Si vous insérez des touches comme

1  3
5  9
4   6
7   15
3   10

Il peut le stocker en tant que

4  6
5  9
3  10
1  3
7  15

HashMap lié préserve l'ordre d'insertion.

exemple.

Si vous insérez des touches

1  3
5  9
4   6
7   15
3   10

Il va le stocker en tant que

1  3
5  9
4   6
7   15
3   10

comme nous insérer.

Tree map stocke les vales dans L'ordre croissant des clés. Exemple.

Si vous insérez des touches

1  3
5  9
4   6
7   15
3   10

Il va le stocker en tant que

1  3
3  10
4   6
5   9
7   15

tous offrent une clé->carte de valeur et une façon d'itérer à travers les clés. La distinction la plus importante entre ces classes sont les garanties de temps et l'ordre des clés.

1. HashMap propose 0(1) recherche et de l'insertion. Si vous itérez à travers les touches, cependant, l'ordre de la touches est essentiellement arbitraire. Il est implémenté par un tableau de listes liées.
2. TreeMap offre O(log N) de recherche et de l'insertion. Les clés sont commandées, donc, si vous devez parcourir les touches dans l'ordre de tri, vous pouvez. Cela signifie que keys doit implémenter L'interface Comparable.TreeMap est implémenté par un arbre rouge-noir.
3. LinkedHashMap propose 0(1) recherche et de l'insertion. Les clés sont ordonnées par ordre d'insertion. Il est mis en œuvre par des seaux doublement reliés.

Imaginez que vous avez passé un tapis roulant vide, HashMap, et LinkedHashMap dans la fonction suivante:

void insertAndPrint(AbstractMap<Integer, String> map) {
  int[] array= {1, -1, 0};
  for (int x : array) {
    map.put(x, Integer.toString(x));
  }
  for (int k: map.keySet()) {
   System.out.print(k + ", ");
  }
}

la sortie pour chacun ressemblera aux résultats ci-dessous.

pour HashMap, le résultat était, dans mes propres tests, { 0, 1, -1}, mais il pourrait être n'importe quel ordre. Il n'y a pas de garantie sur le commander.

Treemap, la sortie était,{ -1, 0, 1}

LinkedList, la sortie a été,{ 1, -1, 0}

• HashMap:

  • Afin de ne pas affirme
  • plus rapide que LinkedHashMap
  • Utilisé pour stocker des tas d'objets

• LinkedHashMap:

  • L'ordre D'insertion de LinkedHashMap sera maintenu
  • plus lent que HashMap et plus rapide que TreeMap
  • si vous voulez pour maintenir un ordre d'insertion de l'utiliser.

• TreeMap:

  • TreeMap est un arbre de cartographie sur
  • TreeMap suivra l'ordre naturel de la clé
  • plus lent que HashMap et LinkedHashMap
  • utilisez TreeMap lorsque vous devez maintenir l'ordre naturel(par défaut)

table de hachage

peut contenir une clé nulle.

HashMap ne maintient pas l'ordre.

TreeMap

TreeMap ne peut pas contenir de clé nulle.

TreeMap maintient l'ordre ascendant.

Linkedhamap

LinkedHashMap peut être utilisé pour maintenir l'ordre d'insertion, sur quelles clés sont insérées dans la carte ou il peut également être utilisé pour maintenir un ordre d'accès, sur lequel les clés sont accessibles.

exemples ::

1) HashMap map = new HashMap ();

    map.put(null, "Kamran");
    map.put(2, "Ali");
    map.put(5, "From");
    map.put(4, "Dir");`enter code here`
    map.put(3, "Lower");
    for (Map.Entry m : map.entrySet()) {
        System.out.println(m.getKey() + "  " + m.getValue());
    } 

2) TreeMap carte = new TreeMap();

    map.put(1, "Kamran");
    map.put(2, "Ali");
    map.put(5, "From");
    map.put(4, "Dir");
    map.put(3, "Lower");
    for (Map.Entry m : map.entrySet()) {
        System.out.println(m.getKey() + "  " + m.getValue());
    }

3) LinkedHashMap map = new LinkedHashMap ();

    map.put(1, "Kamran");
    map.put(2, "Ali");
    map.put(5, "From");
    map.put(4, "Dir");
    map.put(3, "Lower");
    for (Map.Entry m : map.entrySet()) {
        System.out.println(m.getKey() + "  " + m.getValue());
    }