Quelle est la différence entre un HashMap et un TreeMap ?

Question

J'ai commencé à apprendre Java. Quand devrais-je utiliser un HashMap plutôt qu'un TreeMap ?

Answer 1

TreeMap est un exemple de SortedMap ce qui signifie que l'ordre des clés peut être trié, et que lorsque vous itérez sur les clés, vous pouvez vous attendre à ce qu'elles soient dans l'ordre.

HashMap d'autre part, n'offre pas une telle garantie. Par conséquent, lorsque l'on itère sur les clés d'un fichier HashMap vous ne pouvez pas être sûr de leur ordre.

HashMap sera plus efficace en général, donc utilisez-la quand vous ne vous souciez pas de l'ordre des clés.

Answer 2

HashMap est mis en œuvre par une table de hachage tandis que TreeMap est mis en œuvre par Red-Black tree . La principale différence entre HashMap et TreeMap reflètent en fait la principale différence entre un Hash et un Binary Tree En d'autres termes, lors de l'itération, le TreeMap peut garantir l'ordre des clés déterminé par la méthode compareTo() de l'élément ou par un comparateur défini dans le constructeur du TreeMap.

Jetez un coup d'œil à schéma suivant .

Answer 3

Pour résumer :

• HashMap : Structure de tableau de consultation, basée sur les implémentations hashCode(), equals(), complexité d'exécution O(1) pour l'insertion et la recherche, non triée.
• TreeMap : Structure arborescente, basée sur l'implémentation de compareTo(), complexité d'exécution O(log(N)) pour l'insertion et la recherche, triée.

Tiré de : HashMap et TreeMap

Answer 4

Utilisez HashMap la plupart du temps, mais utiliser TreeMap lorsque vous avez besoin que la clé soit triée (lorsque vous devez itérer les clés).

Answer 5

Je vais parler de la HashMap et TreeMap en Java :

• HashMap -- implémente l'interface de base des cartes

  1. mis en œuvre par un tableau de seaux, chaque seau est une liste d'entrées (LinkedList).
  2. temps de fonctionnement des opérations de base : put(), moyenne O(1), pire cas O(n), se produit lorsque la table est redimensionnée ; get(), remove(), moyenne O(1)
  3. non synchronisé, pour le synchroniser : Map m = Collections.synchronizedMap(new HashMap(...));
  4. L'ordre d'itération de la carte est imprévisible.

• TreeMap -- implémente l'interface de carte navigable

  1. mis en œuvre par un arbre rouge-noir
  2. temps d'exécution des opérations de base : put(), get(), remove(), pire cas O(lgn)
  3. non synchronisé, pour le synchroniser : SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
  4. fournissent une itération ordonnée. higherKey(), lowerKey() peuvent être utilisés pour obtenir le successeur et le prédécesseur d'une clé donnée.

En résumé, la plus grande différence entre HashMap et TreeMap est que TreeMap implémente NavigableMap<K,V> qui offrent la fonctionnalité d'itération ordonnée. En outre, HashMap et TreeMap sont tous deux membres du cadre Java Collection. Vous pouvez étudier les code source de Java pour en savoir plus sur leurs mises en œuvre.