Comparaison HashSet et TreeSet

1. Introduction

Dans cet article, nous allons comparer deux des implémentations Java les plus populaires de l' interface java.util.Set - HashSet et TreeSet .

2. Différences

HashSet et TreeSet sont des feuilles de la même branche, mais ils diffèrent sur quelques points importants.

2.1. Commande

HashSet stocke les objets dans un ordre aléatoire, tandis que TreeSet applique l'ordre naturel des éléments. Voyons l'exemple suivant:

@Test public void givenTreeSet_whenRetrievesObjects_thenNaturalOrder() { Set set = new TreeSet(); set.add("Baeldung"); set.add("is"); set.add("Awesome"); assertEquals(3, set.size()); assertTrue(set.iterator().next().equals("Awesome")); }

Après avoir ajouté les objets String dans TreeSet , nous voyons que le premier est «Génial», même s'il a été ajouté à la toute fin. Une opération similaire effectuée avec HashSet ne garantit pas que l'ordre des éléments restera constant dans le temps.

2.2. Objets nuls

Une autre différence est que HashSet peut stocker des objets nuls , alors que TreeSet ne les autorise pas :

@Test(expected = NullPointerException.class) public void givenTreeSet_whenAddNullObject_thenNullPointer() { Set set = new TreeSet(); set.add("Baeldung"); set.add("is"); set.add(null); } @Test public void givenHashSet_whenAddNullObject_thenOK() { Set set = new HashSet(); set.add("Baeldung"); set.add("is"); set.add(null); assertEquals(3, set.size()); }

Si nous essayons de stocker l' objet null dans un TreeSet , l'opération entraînera une NullPointerException levée . La seule exception était dans Java 7 quand il était autorisé à avoir exactement un élément nul dans le TreeSet .

2.3. Performance

En termes simples, HashSet est plus rapide que TreeSet .

HashSet fournit des performances à temps constant pour la plupart des opérations telles que add () , remove () et contains () , par rapport au temps log ( n ) offert par TreeSet.

Habituellement, nous pouvons voir que le temps d'exécution pour ajouter des éléments dans TreeSet est bien meilleur que pour le HashSet .

N'oubliez pas que la JVM n'est peut-être pas préchauffée, de sorte que les temps d'exécution peuvent différer. Une bonne discussion sur la conception et la réalisation de micro-tests à l'aide de diverses implémentations Set est disponible ici.

2.4. Méthodes implémentées

TreeSet est riche en fonctionnalités , implémentant des méthodes supplémentaires telles que:

  • pollFirst () - pour retourner le premier élément, ou null si Set est vide
  • pollLast () - pour récupérer et supprimer le dernier élément, ou retourner null si Set est vide
  • first () - pour retourner le premier élément
  • last () - pour retourner le dernier élément
  • plafond () - pour renvoyer le plus petit élément supérieur ou égal à l'élément donné, ou nul s'il n'y en a pas
  • lower () - pour renvoyer le plus grand élément strictement inférieur à l'élément donné, ou null s'il n'y a pas un tel élément

Les méthodes mentionnées ci-dessus rendent TreeSet beaucoup plus facile à utiliser et plus puissant que HashSet .

3. Similitudes

3.1. Éléments uniques

Les deux TreeSet et HashSet garantissent une collection sans double d'éléments, car il est une partie du générique Set interface:

@Test public void givenHashSetAndTreeSet_whenAddDuplicates_thenOnlyUnique() { Set set = new HashSet(); set.add("Baeldung"); set.add("Baeldung"); assertTrue(set.size() == 1); Set set2 = new TreeSet(); set2.add("Baeldung"); set2.add("Baeldung"); assertTrue(set2.size() == 1); }

3.2. Non synchronisé

Aucune des implémentations Set décrites n'est synchronisée . Cela signifie que si plusieurs threads accèdent à un ensemble simultanément et qu'au moins un des threads le modifie, il doit être synchronisé en externe.

3.3. Itérateurs rapides

Les Iterator renvoyés par TreeSet et HashSet sont rapides.

Cela signifie que toute modification de l' ensemble à tout moment après la création de l' itérateur lèvera une ConcurrentModificationException:

@Test(expected = ConcurrentModificationException.class) public void givenHashSet_whenModifyWhenIterator_thenFailFast() { Set set = new HashSet(); set.add("Baeldung"); Iterator it = set.iterator(); while (it.hasNext()) { set.add("Awesome"); it.next(); } }

4. Quelle implémentation utiliser?

Les deux implémentations remplissent le contrat de l'idée d'un ensemble, c'est donc au contexte quelle implémentation nous pouvons utiliser.

Voici quelques points rapides à retenir:

  • Si nous voulons garder nos entrées triées, nous devons opter pour le TreeSet
  • Si nous accordons plus d'importance aux performances qu'à la consommation de mémoire, nous devrions opter pour le HashSet
  • Si nous manquons de mémoire, nous devrions opter pour le TreeSet
  • Si nous voulons accéder à des éléments qui sont relativement proches les uns des autres selon leur ordre naturel, nous pourrions vouloir considérer TreeSet car il a une plus grande localité
  • Les performances de HashSet peuvent être ajustées en utilisant initialCapacity et loadFactor , ce qui n'est pas possible pour le TreeSet
  • Si nous voulons conserver l'ordre d'insertion et bénéficier d'un accès à temps constant, nous pouvons utiliser le LinkedHashSet

5. Conclusion

Dans cet article, nous avons couvert les différences et les similitudes entre TreeSet et HashSet .

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