Java TreeMap vs HashMap

1. Introduction

Dans cet article, nous allons comparer deux implémentations de Map : TreeMap et HashMap .

Les deux implémentations font partie intégrante de Java Collections Framework et stockent les données sous forme de paires clé-valeur .

2. Différences

2.1. la mise en oeuvre

Nous parlerons d'abord du HashMap qui est une implémentation basée sur une table de hachage. Il étend la classe AbstractMap et implémente l' interface Map . Un HashMap fonctionne sur le principe du hachage .

Cette implémentation de Map agit généralement comme une table de hachage compartimentée , mais lorsque les buckets deviennent trop volumineux, ils sont transformés en nœuds de TreeNodes , chacun structuré de manière similaire à ceux de java.util.TreeMap.

Vous pouvez en savoir plus sur les composants internes de HashMap dans l'article qui y est consacré.

D'autre part, TreeMap étend la classe AbstractMap et implémente l' interface NavigableMap . Un TreeMap stocke les éléments de la carte dans un arbre rouge-noir , qui est un arbre de recherche binaire à auto-équilibrage .

Et, vous pouvez également trouver plus d'informations sur les composants internes de TreeMap dans l'article qui s'y rapporte ici.

2.2. Ordre

HashMap ne fournit aucune garantie sur la façon dont les éléments sont organisés dans la carte .

Cela signifie que nous ne pouvons assumer aucun ordre lors de l'itération sur les clés et les valeurs d'un HashMap :

@Test public void whenInsertObjectsHashMap_thenRandomOrder() { Map hashmap = new HashMap(); hashmap.put(3, "TreeMap"); hashmap.put(2, "vs"); hashmap.put(1, "HashMap"); assertThat(hashmap.keySet(), containsInAnyOrder(1, 2, 3)); }

Cependant, les éléments d'un TreeMap sont triés selon leur ordre naturel .

Si les objets TreeMap ne peuvent pas être triés selon l'ordre naturel, nous pouvons utiliser un comparateur ou un comparable pour définir l'ordre dans lequel les éléments sont disposés dans la carte:

@Test public void whenInsertObjectsTreeMap_thenNaturalOrder() { Map treemap = new TreeMap(); treemap.put(3, "TreeMap"); treemap.put(2, "vs"); treemap.put(1, "HashMap"); assertThat(treemap.keySet(), contains(1, 2, 3)); }

2.3. Valeurs nulles

HashMap permet de stocker au plus une clé nulle et plusieurs valeurs nulles .

Voyons un exemple:

@Test public void whenInsertNullInHashMap_thenInsertsNull() { Map hashmap = new HashMap(); hashmap.put(null, null); assertNull(hashmap.get(null)); }

Cependant, TreeMap n'autorise pas une clé nulle mais peut contenir de nombreuses valeurs nulles .

Une clé nulle n'est pas autorisée car la méthode compareTo () ou compare () lève une exception NullPointerException:

@Test(expected = NullPointerException.class) public void whenInsertNullInTreeMap_thenException() { Map treemap = new TreeMap(); treemap.put(null, "NullPointerException"); }

Si nous utilisons un TreeMap avec un comparateur défini par l'utilisateur , cela dépend de l'implémentation de la méthode compare () comment les valeurs nulles sont gérées.

3. Analyse des performances

La performance est la métrique la plus critique qui nous aide à comprendre l'adéquation d'une structure de données dans un cas d'utilisation.

Dans cette section, nous fournirons une analyse complète des performances de HashMap et TreeMap.

3.1. HashMap

HashMap, étant une implémentation basée sur la table de hachage, utilise en interne une structure de données basée sur un tableau pour organiser ses éléments en fonction de la fonction de hachage .

HashMap fournit les performances attendues à temps constant O (1) pour la plupart des opérations telles que add () , remove () et contains (). Par conséquent, il est nettement plus rapide qu'un TreeMap .

Le temps moyen pour rechercher un élément sous l'hypothèse raisonnable, dans une table de hachage est O (1). Mais une implémentation incorrecte de la fonction de hachage peut conduire à une mauvaise distribution des valeurs dans les buckets, ce qui entraîne:

  • Mémoire supplémentaire - de nombreux compartiments restent inutilisés
  • Dégradation des performances - plus le nombre de collisions est élevé, plus les performances sont faibles

Avant Java 8, le chaînage séparé était le seul moyen préféré de gérer les collisions. Il est généralement implémenté à l'aide de listes liées, c'est -à- dire qu'en cas de collision ou si deux éléments différents ont la même valeur de hachage, stockez les deux éléments dans la même liste liée.

Par conséquent, la recherche d'un élément dans un HashMap, dans le pire des cas, aurait pu prendre aussi longtemps que la recherche d'un élément dans une liste chaînée, c'est-à-dire le temps O (n) .

Cependant, avec l'entrée en scène de JEP 180, il y a eu un changement subtil dans la mise en œuvre de la façon dont les éléments sont disposés dans un HashMap.

Selon la spécification, lorsque les compartiments deviennent trop grands et contiennent suffisamment de nœuds, ils sont transformés en modes de TreeNodes , chacun structuré de manière similaire à ceux de TreeMap .

Par conséquent, en cas de collisions de hachage élevées, les performances dans le pire des cas s'amélioreront de O (n) à O (log n).

Le code effectuant cette transformation a été illustré ci-dessous:

if(binCount >= TREEIFY_THRESHOLD - 1) { treeifyBin(tab, hash); }

La valeur de TREEIFY_THRESHOLD est de huit, ce qui indique effectivement le nombre de seuils d'utilisation d'un arbre plutôt que d'une liste liée pour un compartiment.

C'est évident que:

  • Un HashMap nécessite beaucoup plus de mémoire que nécessaire pour contenir ses données
  • Un HashMap ne doit pas être rempli à plus de 70% - 75%. S'il se rapproche, il est redimensionné et les entrées sont remaniées
  • Le rebasage nécessite n opérations coûteuses où notre insert à temps constant devient d'ordre O (n)
  • C'est l'algorithme de hachage qui détermine l'ordre d'insertion des objets dans le HashMap

The performance of a HashMap can be tuned by setting the custom initial capacity and the load factor, at the time of HashMap object creation itself.

However, we should choose a HashMap if:

  • we know approximately how many items to maintain in our collection
  • we don't want to extract items in a natural order

Under the above circumstances, HashMap is our best choice because it offers constant time insertion, search, and deletion.

3.2. TreeMap

A TreeMap stores its data in a hierarchical tree with the ability to sort the elements with the help of a custom Comparator.

A summary of its performance:

  • TreeMap provides a performance of O(log(n)) for most operations like add(), remove() and contains()
  • A Treemap can save memory (in comparison to HashMap) because it only uses the amount of memory needed to hold its items, unlike a HashMap which uses contiguous region of memory
  • A tree should maintain its balance in order to keep its intended performance, this requires a considerable amount of effort, hence complicates the implementation

We should go for a TreeMap whenever:

  • memory limitations have to be taken into consideration
  • we don't know how many items have to be stored in memory
  • we want to extract objects in a natural order
  • if items will be consistently added and removed
  • we're willing to accept O(log n) search time

4. Similarities

4.1. Unique Elements

Both TreeMap and HashMap don't support duplicate keys. If added, it overrides the previous element (without an error or an exception):

@Test public void givenHashMapAndTreeMap_whenputDuplicates_thenOnlyUnique() { Map treeMap = new HashMap(); treeMap.put(1, "Baeldung"); treeMap.put(1, "Baeldung"); assertTrue(treeMap.size() == 1); Map treeMap2 = new TreeMap(); treeMap2.put(1, "Baeldung"); treeMap2.put(1, "Baeldung"); assertTrue(treeMap2.size() == 1); }

4.2. Concurrent Access

Both Map implementations aren't synchronized and we need to manage concurrent access on our own.

Both must be synchronized externally whenever multiple threads access them concurrently and at least one of the threads modifies them.

We have to explicitly use Collections.synchronizedMap(mapName) to obtain a synchronized view of a provided map.

4.3. Fail-Fast Iterators

The Iterator throws a ConcurrentModificationException if the Map gets modified in any way and at any time once the iterator has been created.

Additionally, we can use the iterator’s remove method to alter the Map during iteration.

Let's see an example:

@Test public void whenModifyMapDuringIteration_thenThrowExecption() { Map hashmap = new HashMap(); hashmap.put(1, "One"); hashmap.put(2, "Two"); Executable executable = () -> hashmap .forEach((key,value) -> hashmap.remove(1)); assertThrows(ConcurrentModificationException.class, executable); }

5. Which Implementation to Use?

In general, both implementations have their respective pros and cons, however, it's about understanding the underlying expectation and requirement which must govern our choice regarding the same.

Summarizing:

  • We should use a TreeMap if we want to keep our entries sorted
  • We should use a HashMap if we prioritize performance over memory consumption
  • Puisqu'un TreeMap a une localité plus importante, nous pourrions l'envisager si nous voulons accéder à des objets relativement proches les uns des autres selon leur ordre naturel
  • HashMap peut être réglé en utilisant initialCapacity et loadFactor , ce qui n'est pas possible pour le TreeMap
  • On peut utiliser LinkedHashMap si l'on veut conserver l'ordre d'insertion tout en bénéficiant d'un accès en temps constant

6. Conclusion

Dans cet article, nous avons montré les différences et les similitudes entre TreeMap et HashMap .

Comme toujours, les exemples de code de cet article sont disponibles à l'adresse over sur GitHub.