Una guida a TreeSet in Java

1. Panoramica

In questo articolo daremo uno sguardo a una parte integrante del Java Collections Framework e ad una delle implementazioni di Set più popolari : il TreeSet .

2. Introduzione a TreeSet

In poche parole, TreeSet è una raccolta ordinata che estende la classe AbstractSet e implementa l' interfaccia NavigableSet .

Ecco un breve riepilogo degli aspetti più importanti di questa implementazione:

  • Memorizza elementi unici
  • Non preserva l'ordine di inserimento degli elementi
  • Ordina gli elementi in ordine crescente
  • Non è thread-safe

In questa implementazione, gli oggetti vengono ordinati e archiviati in ordine crescente in base al loro ordine naturale . Il TreeSet utilizza un albero di ricerca binario autobilanciato , più specificamente un albero rosso-nero .

In poche parole, essendo un albero di ricerca binario autobilanciato, ogni nodo dell'albero binario comprende un bit extra, che viene utilizzato per identificare il colore del nodo che è rosso o nero. Durante le successive inserzioni e cancellazioni, questi bit "colorati" aiutano a garantire che l'albero rimanga più o meno bilanciato.

Quindi, creiamo un'istanza di un TreeSet :

Set treeSet = new TreeSet();

2.1. TreeSet con un parametro di confronto del costruttore

Facoltativamente, possiamo costruire un TreeSet con un costruttore che ci consente di definire l'ordine in cui gli elementi vengono ordinati utilizzando un Comparable o Comparator:

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

Sebbene TreeSet non sia thread-safe, può essere sincronizzato esternamente utilizzando il wrapper Collections.synchronizedSet () :

Set syncTreeSet = Collections.synchronizedSet(treeSet);

Bene, ora che abbiamo un'idea chiara di come creare un'istanza di TreeSet , diamo un'occhiata alle operazioni comuni che abbiamo a disposizione.

3. TreeSet add ()

Il metodo add () , come previsto, può essere utilizzato per aggiungere elementi a un TreeSet . Se è stato aggiunto un elemento, il metodo restituisce true, altrimenti false.

Il contratto del metodo afferma che un elemento verrà aggiunto solo quando lo stesso non è già presente nel Set .

Aggiungiamo un elemento a un TreeSet :

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

Il metodo add è estremamente importante in quanto i dettagli di implementazione del metodo illustrano come funziona il TreeSet internamente , come sfrutta il metodo put di TreeMap per memorizzare gli elementi:

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

La variabile m si riferisce a una TreeMap di supporto interna (notare che TreeMap implementa NavigateableMap ):

private transient NavigableMap m;

Pertanto, il TreeSet dipende internamente su supporto NavigableMap che viene inizializzato con un'istanza di TreeMap quando un'istanza della TreeSet viene creato:

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

Maggiori informazioni su questo possono essere trovate in questo articolo.

4. TreeSet contiene ()

Il metodo contains () viene utilizzato per verificare se un dato elemento è presente in un determinato TreeSet . Se l'elemento viene trovato, restituisce true, altrimenti false.

Vediamo il contains () in azione:

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

5. TreeSet remove ()

Il metodo remove () viene utilizzato per rimuovere l'elemento specificato dall'insieme, se presente.

Se un insieme conteneva l'elemento specificato, questo metodo restituisce true.

Vediamolo in azione:

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

6. TreeSet clear ()

Se vogliamo rimuovere tutti gli elementi da un set, possiamo usare il metodo clear () :

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

7. Dimensione TreeSet ()

Il metodo size () viene utilizzato per identificare il numero di elementi presenti nel TreeSet . È uno dei metodi fondamentali nell'API:

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

8. TreeSet isEmpty ()

Il metodo isEmpty () può essere utilizzato per capire se una data istanza di TreeSet è vuota o meno:

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

9. TreeSet iteratore ()

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.

Nel caso in cui i dati debbano essere letti dal disco rigido (che ha una latenza maggiore rispetto ai dati letti dalla cache o dalla memoria), preferisci TreeSet in quanto ha una maggiore località

17. Conclusione

In questo articolo, ci concentriamo sulla comprensione di come utilizzare l' implementazione TreeSet standard in Java. Abbiamo visto il suo scopo e quanto sia efficiente per quanto riguarda l'usabilità data la sua capacità di evitare duplicati e ordinare elementi.

Come sempre, gli snippet di codice possono essere trovati su GitHub.