Una guía de TreeSet en Java

Programación

1. Información general

En este artículo, veremos una parte integral del marco de colecciones de Java y una de las implementaciones de conjuntos más populares : el TreeSet .

2. Introducción a TreeSet

En pocas palabras, TreeSet es una colección ordenada que extiende la clase AbstractSet e implementa la interfaz NavigableSet .

Aquí hay un resumen rápido de los aspectos más importantes de esta implementación:

  • Almacena elementos únicos
  • No conserva el orden de inserción de los elementos.
  • Ordena los elementos en orden ascendente
  • No es seguro para subprocesos

En esta implementación, los objetos se clasifican y almacenan en orden ascendente según su orden natural . El TreeSet utiliza un árbol de búsqueda binario autoequilibrado, más específicamente un árbol Rojo-Negro .

En pocas palabras, al ser un árbol de búsqueda binario autoequilibrado, cada nodo del árbol binario consta de un bit adicional, que se utiliza para identificar el color del nodo, que es rojo o negro. Durante las inserciones y eliminaciones posteriores, estos bits de "color" ayudan a garantizar que el árbol permanezca más o menos equilibrado.

Entonces, creemos una instancia de un TreeSet :

Set treeSet = new TreeSet();

2.1. TreeSet con un parámetro de comparador de constructor

Opcionalmente, podemos construir un TreeSet con un constructor que nos permita definir el orden en el que se ordenan los elementos usando un Comparable o Comparator:

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

Aunque TreeSet no es seguro para subprocesos, se puede sincronizar externamente mediante el contenedor Collections.synchronizedSet () :

Set syncTreeSet = Collections.synchronizedSet(treeSet);

Muy bien, ahora que tenemos una idea clara de cómo crear una instancia de TreeSet , echemos un vistazo a las operaciones comunes que tenemos disponibles.

3. TreeSet add ()

El método add () , como se esperaba, se puede usar para agregar elementos a un TreeSet . Si se agregó un elemento, el método devuelve verdadero; de lo contrario, falso.

El contrato del método establece que se agregará un elemento solo cuando el mismo no esté ya presente en el conjunto .

Agreguemos un elemento a un TreeSet :

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

El método add es extremadamente importante ya que los detalles de implementación del método ilustran cómo funciona el TreeSet internamente , cómo aprovecha el método put del TreeMap para almacenar los elementos:

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

La variable m se refiere a un TreeMap de respaldo interno (tenga en cuenta que TreeMap implementa NavigateableMap ):

private transient NavigableMap m;

Por lo tanto, la TreeSet depende internamente sobre un soporte NavigableMap que consigue inicializa con una instancia de TreeMap cuando una instancia de la TreeSet se crea:

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

Se puede encontrar más sobre esto en este artículo.

4. TreeSet contiene ()

El método contains () se usa para verificar si un elemento dado está presente en un TreeSet dado . Si se encuentra el elemento, devuelve verdadero; de lo contrario, falso.

Veamos el contains () en acción:

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

5. TreeSet remove ()

El método remove () se usa para eliminar el elemento especificado del conjunto si está presente.

If a set contained the specified element, this method returns true.

Let's see it in action:

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

6. TreeSet clear()

If we want to remove all the items from a set, we can use the clear() method:

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

7. TreeSet size()

The size() method is used to identify the number of elements present in the TreeSet. It's one of the fundamental methods in the API:

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

8. TreeSet isEmpty()

The isEmpty() method can be used to figure out if a given TreeSet instance is empty or not:

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

9. TreeSet iterator()

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.

En caso de que sea necesario leer datos del disco duro (que tiene una mayor latencia que los datos leídos de la memoria caché o la memoria), prefiera TreeSet ya que tiene una mayor ubicación

17. Conclusión

En este artículo, nos enfocamos en comprender cómo usar la implementación estándar de TreeSet en Java. Vimos su propósito y cuán eficiente es en usabilidad dada su capacidad para evitar duplicados y ordenar elementos.

Como siempre, los fragmentos de código se pueden encontrar en GitHub.