Hashset vs Treeset

497

Siempre me han gustado los árboles, que bonito O(n*log(n))y el orden de ellos. Sin embargo, todos los ingenieros de software que he conocido me han preguntado claramente por qué usaría a TreeSet. Desde un entorno de CS, no creo que importe tanto lo que uses, y no me importa perder el tiempo con funciones hash y cubos (en el caso de Java).

¿En qué casos debo usar un HashSetsobre a TreeSet?

heythethew
fuente

Respuestas:

861

HashSet es mucho más rápido que TreeSet (tiempo constante versus tiempo de registro para la mayoría de las operaciones como agregar, eliminar y contiene) pero no ofrece garantías de pedido como TreeSet.

HashSet

  • La clase ofrece un rendimiento de tiempo constante para las operaciones básicas (agregar, eliminar, contiene y tamaño).
  • no garantiza que el orden de los elementos se mantenga constante en el tiempo
  • El rendimiento de la iteración depende de la capacidad inicial y del factor de carga del HashSet.
    • Es bastante seguro aceptar el factor de carga predeterminado, pero es posible que desee especificar una capacidad inicial que sea aproximadamente el doble del tamaño que espera que crezca el conjunto.

TreeSet

  • garantiza el costo de tiempo de registro (n) para las operaciones básicas (agregar, eliminar y contiene)
  • garantiza que los elementos del conjunto se ordenarán (ascendente, natural o el especificado por usted a través de su constructor) (implementos SortedSet)
  • no ofrece ningún parámetro de ajuste para el rendimiento de la iteración
  • ofrece algunos métodos prácticos para hacer frente al conjunto ordenado como first(), last(), headSet(), y tailSet()etc.

Puntos importantes:

  • Ambos garantizan una colección de elementos sin duplicados
  • Generalmente es más rápido agregar elementos al HashSet y luego convertir la colección a un TreeSet para un recorrido ordenado sin duplicados.
  • Ninguna de estas implementaciones está sincronizada. Es decir, si varios subprocesos acceden a un conjunto al mismo tiempo, y al menos uno de los subprocesos modifica el conjunto, debe sincronizarse externamente.
  • LinkedHashSet es en cierto sentido intermedio entre HashSety TreeSet. Implementado como una tabla hash con una lista vinculada que lo ejecuta, sin embargo, proporciona una iteración ordenada por inserción que no es lo mismo que el recorrido ordenado garantizado por TreeSet .

Por lo tanto, una elección de uso depende completamente de sus necesidades, pero creo que incluso si necesita una colección ordenada, debería preferir HashSet para crear el Set y luego convertirlo en TreeSet.

  • p.ej SortedSet<String> s = new TreeSet<String>(hashSet);
sactiw
fuente
38
Solo soy yo quien encuentra la afirmación "¿HashSet es mucho más rápido que TreeSet (tiempo constante versus tiempo de registro ...)"? Primero, se trata de la complejidad del tiempo, no del tiempo absoluto, y O (1) puede ser en muchos casos más lento que O (f (N)). Segundo, que O (logN) es "casi" O (1). No me sorprendería si en muchos casos comunes un TreeSet superara a un HashSet.
lvella
22
Solo quiero secundar el comentario de Ivella. la complejidad del tiempo NO es lo mismo que el tiempo de ejecución, y O (1) no siempre es mejor que O (2 ^ n). Un ejemplo perverso ilustra el punto: considere un conjunto de hash usando un algoritmo de hash que tomó 1 billón de instrucciones de máquina para ejecutar (O (1)) frente a cualquier implementación común de clasificación de burbujas (O (N ^ 2) promedio / peor) para 10 elementos . El tipo de burbuja ganará cada vez. El punto es que las clases de algoritmos de enseñar a todos a pensar en aproximaciones utilizando el tiempo-complejidad, pero en el mundo real los factores constantes IMPORTA frecuencia.
Peter Oehlert
17
Tal vez soy solo yo, pero ¿no es el consejo agregar primero todo a un hashset y luego convertirlo en un conjunto de árboles horrible? 1) La inserción en un hashset solo es rápida si conoce de antemano el tamaño de su conjunto de datos; de lo contrario, paga un reescalonamiento O (n), posiblemente varias veces. y 2) Usted paga por la inserción de TreeSet de todos modos al convertir el conjunto. (con venganza, porque la iteración a través de un hashset no es terriblemente eficiente)
TinkerTank
55
Este consejo se basa en el hecho de que, para un conjunto, debe verificar si un elemento es un duplicado antes de agregarlo; por lo tanto, ahorrará tiempo eliminando los duplicados si está utilizando un hashset sobre un conjunto de árboles. Sin embargo, teniendo en cuenta el precio a pagar por crear un segundo conjunto para los no duplicados, el porcentaje de duplicados debería ser realmente excelente para superar este precio y hacer que ahorre tiempo. Y, por supuesto, esto es para conjuntos medianos y grandes porque para un conjunto pequeño, el conjunto de árboles es posiblemente más rápido que un hashset.
SylvainL
55
@PeterOehlert: proporcione un punto de referencia para eso. Entiendo su punto, pero la diferencia entre ambos conjuntos apenas importa con tamaños de colección pequeños. Y tan pronto como el conjunto crece hasta un punto, donde la implementación es importante, log (n) se está convirtiendo en un problema. En general, las magnitudes de orden de las funciones hash (incluso las complejas) son más rápidas que varios errores de caché (que tiene en árboles enormes para casi todos los niveles accedidos) para encontrar / acceder / agregar / modificar la hoja. Al menos esa es mi experiencia con estos dos conjuntos en Java.
Bouncner el
38

Una ventaja aún no mencionada de a TreeSetes que tiene una mayor "localidad", que es la abreviatura de decir (1) si dos entradas están cercanas en el orden, a las TreeSetubican cerca una de la otra en la estructura de datos y, por lo tanto, en la memoria; y (2) esta ubicación aprovecha el principio de localidad, que dice que una aplicación con frecuencia similar accede a datos similares.

Esto contrasta con a HashSet, que extiende las entradas por toda la memoria, sin importar cuáles sean sus claves.

Cuando el costo de latencia de la lectura desde un disco duro es miles de veces el costo de la lectura desde la memoria caché o RAM, y cuando los datos realmente se acceden con la localidad, TreeSetpuede ser una opción mucho mejor.

Carl Andersen
fuente
3
¿Puede demostrar que si hay dos entradas cercanas en el orden, un TreeSet las coloca cerca una de la otra en la estructura de datos y, por lo tanto, en la memoria ?
David Soroko
66
Muy irrelevante para Java. Los elementos del conjunto son Objetos de todos modos y apuntan a otro lugar, por lo que no está ahorrando mucho de nada.
Andrew Gallasch
Además de los otros comentarios realizados sobre la falta de localidad en Java en general, la implementación de OpenJDK de TreeSet/ TreeMapno está optimizada para la localidad. Si bien es posible usar un árbol b de orden 4 para representar un árbol rojo-negro y así mejorar la localidad y el rendimiento de la memoria caché, la implementación no es así. En cambio, cada nodo almacena un puntero a su propia clave, su propio valor, su padre y sus nodos secundarios izquierdo y derecho, evidentes en el código fuente JDK 8 para TreeMap.Entry .
kbolino
25

HashSetes O (1) para acceder a elementos, por lo que ciertamente importa. Pero no es posible mantener el orden de los objetos en el conjunto.

TreeSetes útil si le importa mantener un orden (en términos de valores y no el orden de inserción). Pero, como ha notado, está haciendo una orden de negociación por un tiempo más lento para acceder a un elemento: O (log n) para operaciones básicas.

De los javadocs paraTreeSet :

Esta implementación proporciona un costo de tiempo de registro (n) garantizado para las operaciones básicas ( add, removey contains).

duffymo
fuente
22

1.HashSet permite objetos nulos.

2.TreeSet no permitirá objetos nulos. Si intenta agregar un valor nulo, arrojará una NullPointerException.

3.HashSet es mucho más rápido que TreeSet.

p.ej

 TreeSet<String> ts = new TreeSet<String>();
 ts.add(null); // throws NullPointerException

 HashSet<String> hs = new HashSet<String>();
 hs.add(null); // runs fine
SuReN
fuente
3
ts.add (nulo) funcionará bien en el caso de TreeSet si se agrega nulo como primer objeto en TreeSet. Y cualquier objeto agregado después de eso dará NullPointerException en el método compareTo de Comparator.
Shoaib Chikate
2
Realmente no deberías agregar nada nulla tu conjunto de ninguna manera.
esponjoso
TreeSet<String> badassTreeSet = new TreeSet<String>(new Comparator<String>() { public int compare(String string1, String string2) { if (string1 == null) { return (string2 == null) ? 0 : -1; } else if (string2 == null) { return 1; } else { return string1.compareTo(string2); } } }); badassTreeSet.add("tree"); badassTreeSet.add("asdf"); badassTreeSet.add(null); badassTreeSet.add(null); badassTreeSet.add("set"); badassTreeSet.add("tree"); System.out.println(badassTreeSet);
Dávid Horváth
21

Basándome en una respuesta visual encantadora en Maps by @shevchyk, aquí está mi opinión:

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
   Property          HashSet             TreeSet           LinkedHashSet   
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
                no guarantee order  sorted according                       
   Order       will remain constant to the natural        insertion-order  
                    over time          ordering                            
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
 Add/remove           O(1)              O(log(n))             O(1)         
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
                                      NavigableSet                         
  Interfaces           Set                Set                  Set         
                                       SortedSet                           
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
                                       not allowed                         
  Null values        allowed        1st element only        allowed        
                                        in Java 7                          
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
                 Fail-fast behavior of an iterator cannot be guaranteed      
   Fail-fast   impossible to make any hard guarantees in the presence of     
   behavior              unsynchronized concurrent modification              
╠══════════════╬═══════════════════════════════════════════════════════════════╣
      Is                                                                     
 synchronized               implementation is not synchronized               
╚══════════════╩═══════════════════════════════════════════════════════════════╝
kiedysktos
fuente
13

La razón por la cual la mayoría de los usos HashSetes que las operaciones son (en promedio) O (1) en lugar de O (log n). Si el conjunto contiene elementos estándar, no estará "jugando con las funciones hash" como se ha hecho por usted. Si el conjunto contiene clases personalizadas, debe implementarlo hashCodepara usarlo HashSet(aunque Effective Java muestra cómo), pero si usa a TreeSet, debe hacerlo Comparableo proporcionar a Comparator. Esto puede ser un problema si la clase no tiene un orden particular.

A veces he usado TreeSet(o en realidad TreeMap) para conjuntos / mapas muy pequeños (<10 elementos) aunque no he verificado si hay alguna ganancia real al hacerlo. Para conjuntos grandes, la diferencia puede ser considerable.

Ahora, si necesita ordenarlos, entonces TreeSetes apropiado, aunque incluso entonces si las actualizaciones son frecuentes y la necesidad de un resultado ordenado es poco frecuente, a veces copiar los contenidos a una lista o matriz y ordenarlos puede ser más rápido.

Kathy Van Stone
fuente
cualquier punto de datos para estos elementos grandes como 10K o más
kuhajeyan
11

Si no está insertando suficientes elementos para producir repeticiones frecuentes (o colisiones, si su HashSet no puede cambiar el tamaño), un HashSet ciertamente le brinda el beneficio del acceso de tiempo constante. Pero en conjuntos con mucho crecimiento o contracción, en realidad puede obtener un mejor rendimiento con Treesets, dependiendo de la implementación.

El tiempo amortizado puede estar cerca de O (1) con un árbol rojo-negro funcional, si la memoria me sirve. El libro de Okasaki tendría una mejor explicación de la que puedo lograr. (O vea su lista de publicaciones )

JasonTrue
fuente
7

Las implementaciones de HashSet son, por supuesto, mucho más rápidas, menos gastos generales porque no hay pedidos. Se proporciona un buen análisis de las diversas implementaciones de Set en Java en http://java.sun.com/docs/books/tutorial/collections/implementations/set.html .

La discusión allí también señala un interesante enfoque de 'punto medio' para la pregunta de Tree vs Hash. Java proporciona un LinkedHashSet, que es un HashSet con una lista vinculada "orientada a la inserción" que se ejecuta a través de él, es decir, el último elemento de la lista vinculada también es el más recientemente insertado en el Hash. Esto le permite evitar el desorden de un hash desordenado sin incurrir en el aumento del costo de un TreeSet.

Joseph Weissman
fuente
4

El TreeSet es uno de dos colecciones ordenados (el otro es TreeMap). Utiliza una estructura de árbol Rojo-Negra (pero lo sabías), y garantiza que los elementos estarán en orden ascendente, de acuerdo con el orden natural. Opcionalmente, puede construir un TreeSet con un constructor que le permita dar a la colección sus propias reglas sobre cuál debería ser el orden (en lugar de depender del orden definido por la clase de elementos) mediante el uso de un Comparable o Comparator

y Un LinkedHashSet es una versión ordenada de HashSet que mantiene una Lista doblemente vinculada en todos los elementos. Use esta clase en lugar de HashSet cuando le importe el orden de iteración. Cuando itera a través de un HashSet, el orden es impredecible, mientras que LinkedHashSet le permite recorrer los elementos en el orden en que se insertaron.

subhash laghate
fuente
3

Se han dado muchas respuestas, basadas en consideraciones técnicas, especialmente en torno al rendimiento. Según yo, la elección entre TreeSety HashSetasuntos.

Pero preferiría decir que la elección debería basarse primero en consideraciones conceptuales .

Si, para los objetos que necesita manipular, un orden natural no tiene sentido, entonces no lo use TreeSet.
Es un conjunto ordenado, ya que se implementa SortedSet. Por lo tanto, significa que debe anular la función compareTo, que debe ser coherente con lo que devuelve la función equals. Por ejemplo, si tiene un conjunto de objetos de una clase llamada Estudiante, entonces no creo queTreeSettendría sentido, ya que no existe un orden natural entre los estudiantes. Puede ordenarlos por su calificación promedio, está bien, pero este no es un "orden natural". La función compareTodevolvería 0 no solo cuando dos objetos representan al mismo alumno, sino también cuando dos alumnos diferentes tienen la misma calificación. Para el segundo caso, equalsdevolvería falso (a menos que decida hacer que el último devuelva verdadero cuando dos estudiantes diferentes tienen la misma calificación, lo que haría que la equalsfunción tenga un significado engañoso, por no decir un significado incorrecto).
Tenga en cuenta esta coherencia entre equalsy compareToEs opcional, pero muy recomendable. De lo contrario, el contrato de interfaz Setse rompe, lo que hace que su código sea engañoso para otras personas, lo que posiblemente también conduzca a un comportamiento inesperado.

Este enlace podría ser una buena fuente de información sobre esta pregunta.

Marek Stanley
fuente
3

¿Por qué tener manzanas cuando puedes tener naranjas?

En serio, muchachos y chicas: si su colección es grande, leída y escrita en miles de millones de veces, y está pagando por ciclos de CPU, entonces la elección de la colección es relevante SOLO si NECESITA que funcione mejor. Sin embargo, en la mayoría de los casos, esto realmente no importa: unos pocos milisegundos aquí y allá pasan desapercibidos en términos humanos. Si realmente importaba tanto, ¿por qué no escribes código en ensamblador o C? [señal otra discusión]. Entonces, el punto es que si estás contento de usar la colección que elijas, y resuelve tu problema [incluso si no es específicamente el mejor tipo de colección para la tarea]. El software es maleable. Optimice su código cuando sea necesario. El tío Bob dice que la optimización prematura es la raíz de todo mal. Tío Bob lo dice

usuario924272
fuente
1

Edición de mensajes ( reescritura completa ) Cuando el orden no importa, es cuando. Ambos deberían dar Log (n): sería útil ver si alguno es más del cinco por ciento más rápido que el otro. HashSet puede proporcionar pruebas de O (1) en un bucle que debe revelar si es así.

Nicholas Jordan
fuente
-3
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class HashTreeSetCompare {

    //It is generally faster to add elements to the HashSet and then
    //convert the collection to a TreeSet for a duplicate-free sorted
    //Traversal.

    //really? 
    O(Hash + tree set) > O(tree set) ??
    Really???? Why?



    public static void main(String args[]) {

        int size = 80000;
        useHashThenTreeSet(size);
        useTreeSetOnly(size);

    }

    private static void useTreeSetOnly(int size) {

        System.out.println("useTreeSetOnly: ");
        long start = System.currentTimeMillis();
        Set<String> sortedSet = new TreeSet<String>();

        for (int i = 0; i < size; i++) {
            sortedSet.add(i + "");
        }

        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useTreeSetOnly: " + (end - start));
    }

    private static void useHashThenTreeSet(int size) {

        System.out.println("useHashThenTreeSet: ");
        long start = System.currentTimeMillis();
        Set<String> set = new HashSet<String>();

        for (int i = 0; i < size; i++) {
            set.add(i + "");
        }

        Set<String> sortedSet = new TreeSet<String>(set);
        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useHashThenTreeSet: " + (end - start));
    }
}
gli00001
fuente
1
La publicación decía que generalmente es más rápido agregar elementos al HashSet y luego convertir la colección a un TreeSet para un recorrido ordenado sin duplicados. Establezca <String> s = new TreeSet <String> (hashSet); Me pregunto por qué no establecer <String> s = new TreeSet <String> () directamente si sabemos que se usará para la iteración ordenada, así que hice esta comparación y el resultado mostró cuál es más rápido.
gli00001
"¿En qué casos me gustaría usar un HashSet sobre un TreeSet?"
Austin Henley
1
mi punto es, si necesita ordenar, usar TreeSet solo es mejor que poner todo en HashSet y luego crear un TreeSet basado en ese HashSet. No veo el valor de HashSet + TreeSet en absoluto de la publicación original.
gli00001
@ gli00001: te perdiste el punto. Si no siempre necesita ordenar su conjunto de elementos, pero va a manipularlo con bastante frecuencia, entonces valdrá la pena que use un hashset para beneficiarse de las operaciones más rápidas la mayor parte del tiempo. Para los momentos ocasionales en los que necesita procesar los elementos en orden, simplemente envuelva con un conjunto de árboles. Depende de su caso de uso, pero ese no es un caso de uso poco común (y eso probablemente asume un conjunto que no contiene demasiados elementos y con reglas de orden complejas).
haylem