Un guide sur TreeSet en Java

1. Vue d'ensemble

Dans cet article, nous examinerons une partie intégrante de Java Collections Framework et l' une des implémentations de Set les plus populaires - le TreeSet .

2. Introduction à TreeSet

En termes simples, le TreeSet est une collection triée qui étend la classe AbstractSet et implémente l' interface NavigableSet .

Voici un bref résumé des aspects les plus importants de cette implémentation:

  • Il stocke des éléments uniques
  • Il ne préserve pas l'ordre d'insertion des éléments
  • Il trie les éléments par ordre croissant
  • Ce n'est pas thread-safe

Dans cette implémentation, les objets sont triés et stockés par ordre croissant selon leur ordre naturel . Le TreeSet utilise un arbre de recherche binaire auto-équilibré, plus spécifiquement un arbre rouge-noir .

En termes simples, étant un arbre de recherche binaire auto-équilibré, chaque nœud de l'arbre binaire comprend un bit supplémentaire, qui est utilisé pour identifier la couleur du nœud qui est soit rouge soit noir. Lors des insertions et suppressions ultérieures, ces bits de «couleur» permettent de s'assurer que l'arbre reste plus ou moins équilibré.

Alors, créons une instance d'un TreeSet :

Set treeSet = new TreeSet();

2.1. TreeSet avec un paramètre de comparateur de constructeur

En option, nous pouvons construire un TreeSet avec un constructeur qui nous permet de définir l'ordre dans lequel les éléments sont triés en utilisant un Comparable ou un Comparator:

Set treeSet = new TreeSet(Comparator.comparing(String::length));

Bien que TreeSet ne soit pas thread-safe, il peut être synchronisé en externe à l'aide du wrapper Collections.synchronizedSet () :

Set syncTreeSet = Collections.synchronizedSet(treeSet);

Très bien, maintenant que nous avons une idée claire de la façon de créer une instance TreeSet , examinons les opérations courantes dont nous disposons.

3. TreeSet ajouter ()

La méthode add () , comme prévu, peut être utilisée pour ajouter des éléments à un TreeSet . Si un élément a été ajouté, la méthode renvoie true, sinon - false.

Le contrat de la méthode stipule qu'un élément ne sera ajouté que lorsque celui-ci n'est pas déjà présent dans l' ensemble .

Ajoutons un élément à un TreeSet :

@Test public void whenAddingElement_shouldAddElement() { Set treeSet = new TreeSet(); assertTrue(treeSet.add("String Added")); }

La méthode add est extrêmement importante car les détails d'implémentation de la méthode illustrent comment le TreeSet fonctionne en interne , comment il exploite la méthode put de TreeMap pour stocker les éléments:

public boolean add(E e) { return m.put(e, PRESENT) == null; }

La variable m fait référence à un support interne TreeMap (notez que TreeMap implémente NavigateableMap ):

private transient NavigableMap m;

Par conséquent, le TreeSet dépend en interne d'un NavigableMap de support qui est initialisé avec une instance de TreeMap lorsqu'une instance de TreeSet est créée:

public TreeSet() { this(new TreeMap()); }

Vous trouverez plus d'informations à ce sujet dans cet article.

4. TreeSet contient ()

La méthode contains () est utilisée pour vérifier si un élément donné est présent dans un TreeSet donné . Si l'élément est trouvé, il renvoie vrai, sinon faux.

Voyons le contains () en action:

@Test public void whenCheckingForElement_shouldSearchForElement() { Set treeSetContains = new TreeSet(); treeSetContains.add("String Added"); assertTrue(treeSetContains.contains("String Added")); }

5. TreeSet remove ()

La méthode remove () est utilisée pour supprimer l'élément spécifié de l'ensemble s'il est présent.

Si un ensemble contenait l'élément spécifié, cette méthode renvoie true.

Voyons cela en action:

@Test public void whenRemovingElement_shouldRemoveElement() { Set removeFromTreeSet = new TreeSet(); removeFromTreeSet.add("String Added"); assertTrue(removeFromTreeSet.remove("String Added")); }

6. TreeSet clear ()

Si nous voulons supprimer tous les éléments d'un ensemble, nous pouvons utiliser la méthode clear () :

@Test public void whenClearingTreeSet_shouldClearTreeSet() { Set clearTreeSet = new TreeSet(); clearTreeSet.add("String Added"); clearTreeSet.clear(); assertTrue(clearTreeSet.isEmpty()); }

7. Taille de TreeSet ()

La méthode size () est utilisée pour identifier le nombre d'éléments présents dans le TreeSet . C'est l'une des méthodes fondamentales de l'API:

@Test public void whenCheckingTheSizeOfTreeSet_shouldReturnThesize() { Set treeSetSize = new TreeSet(); treeSetSize.add("String Added"); assertEquals(1, treeSetSize.size()); }

8. TreeSet isEmpty ()

La méthode isEmpty () peut être utilisée pour déterminer si une instance TreeSet donnée est vide ou non:

@Test public void whenCheckingForEmptyTreeSet_shouldCheckForEmpty() { Set emptyTreeSet = new TreeSet(); assertTrue(emptyTreeSet.isEmpty()); }

9. Itérateur TreeSet ()

The iterator() method returns an iterator iterating in the ascending order over the elements in the Set. Those iterators are fail-fast.

We can observe the ascending iteration order here:

@Test public void whenIteratingTreeSet_shouldIterateTreeSetInAscendingOrder() { Set treeSet = new TreeSet(); treeSet.add("First"); treeSet.add("Second"); treeSet.add("Third"); Iterator itr = treeSet.iterator(); while (itr.hasNext()) { System.out.println(itr.next()); } }

Additionally, TreeSet enables us to iterate through the Set in descending order.

Let's see that in action:

@Test public void whenIteratingTreeSet_shouldIterateTreeSetInDescendingOrder() { TreeSet treeSet = new TreeSet(); treeSet.add("First"); treeSet.add("Second"); treeSet.add("Third"); Iterator itr = treeSet.descendingIterator(); while (itr.hasNext()) { System.out.println(itr.next()); } }

The Iterator throws a ConcurrentModificationException if the set is modified at any time after the iterator is created in any way except through the iterator's remove() method.

Let's create a test for this:

@Test(expected = ConcurrentModificationException.class) public void whenModifyingTreeSetWhileIterating_shouldThrowException() { Set treeSet = new TreeSet(); treeSet.add("First"); treeSet.add("Second"); treeSet.add("Third"); Iterator itr = treeSet.iterator(); while (itr.hasNext()) { itr.next(); treeSet.remove("Second"); } } 

Alternatively, if we had used the iterator's remove method, then we wouldn't have encountered the exception:

@Test public void whenRemovingElementUsingIterator_shouldRemoveElement() { Set treeSet = new TreeSet(); treeSet.add("First"); treeSet.add("Second"); treeSet.add("Third"); Iterator itr = treeSet.iterator(); while (itr.hasNext()) { String element = itr.next(); if (element.equals("Second")) itr.remove(); } assertEquals(2, treeSet.size()); }

There's no guarantee on the fail-fast behavior of an iterator as it's impossible to make any hard guarantees in the presence of unsynchronized concurrent modification.

More about this can be found here.

10. TreeSet first()

This method returns the first element from a TreeSet if it's not empty. Otherwise, it throws a NoSuchElementException.

Let's see an example:

@Test public void whenCheckingFirstElement_shouldReturnFirstElement() { TreeSet treeSet = new TreeSet(); treeSet.add("First"); assertEquals("First", treeSet.first()); }

11. TreeSet last()

Analogously to the above example, this method will return the last element if the set is not empty:

@Test public void whenCheckingLastElement_shouldReturnLastElement() { TreeSet treeSet = new TreeSet(); treeSet.add("First"); treeSet.add("Last"); assertEquals("Last", treeSet.last()); }

12. TreeSet subSet()

This method will return the elements ranging from fromElement to toElement. Note that fromElement is inclusive and toElement is exclusive:

@Test public void whenUsingSubSet_shouldReturnSubSetElements() { SortedSet treeSet = new TreeSet(); treeSet.add(1); treeSet.add(2); treeSet.add(3); treeSet.add(4); treeSet.add(5); treeSet.add(6); Set expectedSet = new TreeSet(); expectedSet.add(2); expectedSet.add(3); expectedSet.add(4); expectedSet.add(5); Set subSet = treeSet.subSet(2, 6); assertEquals(expectedSet, subSet); }

13. TreeSet headSet()

This method will return elements of TreeSet which are smaller than the specified element:

@Test public void whenUsingHeadSet_shouldReturnHeadSetElements() { SortedSet treeSet = new TreeSet(); treeSet.add(1); treeSet.add(2); treeSet.add(3); treeSet.add(4); treeSet.add(5); treeSet.add(6); Set subSet = treeSet.headSet(6); assertEquals(subSet, treeSet.subSet(1, 6)); }

14. TreeSet tailSet()

This method will return the elements of a TreeSet which are greater than or equal to the specified element:

@Test public void whenUsingTailSet_shouldReturnTailSetElements() { NavigableSet treeSet = new TreeSet(); treeSet.add(1); treeSet.add(2); treeSet.add(3); treeSet.add(4); treeSet.add(5); treeSet.add(6); Set subSet = treeSet.tailSet(3); assertEquals(subSet, treeSet.subSet(3, true, 6, true)); }

15. Storing Null Elements

Before Java 7, it was possible to add null elements to an empty TreeSet.

However, that was considered a bug. Therefore, TreeSet no longer supports the addition of null.

When we add elements to the TreeSet, the elements get sorted according to their natural order or as specified by the comparator. Hence adding a null, when compared to existing elements, results in a NullPointerException since null cannot be compared to any value:

@Test(expected = NullPointerException.class) public void whenAddingNullToNonEmptyTreeSet_shouldThrowException() { Set treeSet = new TreeSet(); treeSet.add("First"); treeSet.add(null); }

Elements inserted into the TreeSet must either implement the Comparable interface or at least be accepted by the specified comparator. All such elements must be mutually comparable,i.e.e1.compareTo(e2) or comparator.compare(e1, e2)mustn't throw a ClassCastException.

Let's see an example:

class Element { private Integer id; // Other methods... } Comparator comparator = (ele1, ele2) -> { return ele1.getId().compareTo(ele2.getId()); }; @Test public void whenUsingComparator_shouldSortAndInsertElements() { Set treeSet = new TreeSet(comparator); Element ele1 = new Element(); ele1.setId(100); Element ele2 = new Element(); ele2.setId(200); treeSet.add(ele1); treeSet.add(ele2); System.out.println(treeSet); }

16. Performance of TreeSet

When compared to a HashSet the performance of a TreeSet is on the lower side. Operations like add, remove and search take O(log n) time while operations like printing n elements in sorted order require O(n) time.

A TreeSet should be our primary choice if we want to keep our entries sorted as a TreeSet may be accessed and traversed in either ascending or descending order, and the performance of ascending operations and views is likely to be faster than that of descending ones.

The Principle of Locality – is a term for the phenomenon in which the same values, or related storage locations, are frequently accessed, depending on the memory access pattern.

When we say locality:

  • Similar data is often accessed by an application with similar frequency
  • If two entries are nearby given an ordering, a TreeSet places them near each other in the data structure, and hence in memory

A TreeSet being a data-structure with greater locality we can, therefore, conclude in accordance to the Principle of Locality, that we should give preference to a TreeSet if we're short on memory and if we want to access elements that are relatively close to each other according to their natural ordering.

Dans le cas où les données doivent être lues à partir du disque dur (qui a une latence plus grande que les données lues à partir du cache ou de la mémoire), préférez TreeSet car il a une plus grande localité

17. Conclusion

Dans cet article, nous nous concentrons sur la manière d'utiliser l' implémentation standard de TreeSet en Java. Nous avons vu son objectif et son efficacité en termes de convivialité étant donné sa capacité à éviter les doublons et à trier les éléments.

Comme toujours, des extraits de code peuvent être trouvés sur GitHub.