Comparación de HashSet y TreeSet

Programación

1. Introducción

En este artículo, vamos a comparar dos de las implementaciones Java más populares de la interfaz java.util.Set : HashSet y TreeSet .

2. Diferencias

HashSet y TreeSet son hojas de la misma rama, pero difieren en algunos aspectos importantes.

2.1. Ordenar

HashSet almacena los objetos en orden aleatorio, mientras que TreeSet aplica el orden natural de los elementos. Veamos el siguiente ejemplo:

@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")); }

Después de agregar los objetos String en TreeSet , vemos que el primero es "Awesome", aunque se agregó al final. Una operación similar realizada con HashSet no garantiza que el orden de los elementos se mantenga constante en el tiempo.

2.2. Objetos nulos

Otra diferencia es que HashSet puede almacenar objetos nulos , mientras que TreeSet no los permite :

@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 intentamos almacenar el objeto nulo en un TreeSet , la operación dará como resultado una NullPointerException lanzada . La única excepción fue en Java 7 cuando se le permitió tener exactamente un elemento nulo en el TreeSet .

2.3. Actuación

En pocas palabras, HashSet es más rápido que TreeSet .

HashSet proporciona un rendimiento de tiempo constante para la mayoría de las operaciones como add () , remove () y contains () , frente al tiempo log ( n ) ofrecido por TreeSet.

Por lo general, podemos ver que el tiempo de ejecución para agregar elementos en TreeSet es mucho mejor que para el HashSet .

Recuerde que es posible que la JVM no se haya calentado, por lo que los tiempos de ejecución pueden variar. Aquí se encuentra disponible una buena discusión sobre cómo diseñar y realizar micropruebas usando varias implementaciones de Set .

2.4. Métodos implementados

TreeSet es rico en funcionalidades , implementando métodos adicionales como:

  • pollFirst () - para devolver el primer elemento, o nulo si Set está vacío
  • pollLast () : para recuperar y eliminar el último elemento, o devolver nulo si Set está vacío
  • first () - para devolver el primer artículo
  • last () - para devolver el último artículo
  • techo () - para devolver el elemento menor mayor o igual que el elemento dado, o nulo si no existe tal elemento
  • lower () - para devolver el elemento más grande estrictamente menor que el elemento dado, o nulo si no existe tal elemento

Los métodos mencionados anteriormente hacen que TreeSet sea ​​mucho más fácil de usar y más poderoso que HashSet .

3. Similitudes

3.1. Elementos únicos

Tanto TreeSet como HashSet garantizan una colección de elementos libre de duplicados, ya que es parte de la interfaz genérica de Set :

@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. No sincronizado

Ninguna de las implementaciones de Set descritas está sincronizada . Esto significa que si varios subprocesos acceden a un conjunto al mismo tiempo y al menos uno de los subprocesos lo modifica, debe sincronizarse externamente.

3.3. Iteradores a prueba de fallos

Los iteradores devueltos por TreeSet y HashSet son rápidos en caso de fallas.

Eso significa que cualquier modificación del conjunto en cualquier momento después de la creación del iterador generará una 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. ¿Qué implementación usar?

Ambas implementaciones cumplen con el contrato de la idea de un conjunto, por lo que depende del contexto qué implementación podamos usar.

Here are few quick points to remember:

  • If we want to keep our entries sorted, we need to go for the TreeSet
  • If we value performance more than memory consumption, we should go for the HashSet
  • If we are short on memory, we should go for the TreeSet
  • If we want to access elements that are relatively close to each other according to their natural ordering, we might want to consider TreeSet because it has greater locality
  • HashSet‘s performance can be tuned using the initialCapacity and loadFactor, which is not possible for the TreeSet
  • If we want to preserve insertion order and benefit from constant time access, we can use the LinkedHashSet

5. Conclusion

En este artículo, cubrimos las diferencias y similitudes entre TreeSet y HashSet .

Como siempre, los ejemplos de código de este artículo están disponibles en GitHub.