java - Hashset vs Treeset

Question

Siempre me han encantado los árboles, esa bonita O(n*log(n)) y la limpieza de los árboles. Sin embargo, todos los ingenieros de software que he conocido me han preguntado claramente por qué usaría un TreeSet . Desde un fondo de CS, no creo que importe tanto lo que use, y no me importa perder el tiempo con funciones hash y depósitos (en el caso de Java ).

¿En qué casos debo usar un HashSet sobre un TreeSet ?

Answer 1

¿Por qué tener manzanas cuando puedes tener naranjas?

En serio, chicos y chicas: si tu colección es grande, lee y escribe cientos de veces, y estás pagando por ciclos de CPU, entonces la elección de la colección SÓLO es relevante si la NECESITA para que tenga un mejor desempeño. Sin embargo, en la mayoría de los casos, esto no importa realmente: unos pocos milisegundos aquí y allá pasan desapercibidos en términos humanos. Si realmente importó mucho, ¿por qué no escribes código en ensamblador o C? [Cue otra discusión]. Entonces, el punto es si estás contento con 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. El tio bob lo dice

Answer 2

1.HashSet permite el objeto nulo.

2.TreeSet no permitirá el objeto nulo. Si intenta agregar un valor nulo, se lanzará 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

Answer 3

Basándome en la encantadora respuesta visual 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               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

Answer 4

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

Answer 5

El TreeSet es una de las dos colecciones ordenadas (la otra es TreeMap). Utiliza una estructura de árbol rojo-negro (pero usted lo sabía) 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 darle a la colección sus propias reglas para lo que debería ser el pedido (en lugar de confiar en el orden definido por la clase de los elementos) utilizando un Comparable o Comparator

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

Answer 6

La razón por la que la mayoría utiliza HashSet es 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 implementar hashCode para usar HashSet (aunque Effective Java muestra cómo), pero si usa un TreeSet , debe hacerlo Comparable o suministrar un Comparator . Esto puede ser un problema si la clase no tiene un orden particular.

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

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

Answer 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 ''terreno intermedio'' para la pregunta de Árbol contra Hash. Java proporciona un LinkedHashSet, que es un HashSet con una lista enlazada "orientada a la inserción" que se ejecuta a través de él, es decir, el último elemento de la lista enlazada también es el más reciente insertado en el Hash. Esto le permite evitar la irregularidad de un hash no ordenado sin incurrir en el aumento del costo de un TreeSet.

Answer 8

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

Pero preferiría decir que la elección debe ser impulsada primero por consideraciones conceptuales .

Si, para los objetos que necesita manipular, un orden natural no tiene sentido, entonces no use TreeSet .
Es un conjunto ordenado, ya que 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 que un TreeSet tenga sentido, ya que no hay un orden natural entre los estudiantes. Puede ordenarlos por su calificación promedio, está bien, pero esto no es un "pedido natural". La función compareTo devolvería 0 no solo cuando dos objetos representan al mismo estudiante, sino también cuando dos estudiantes diferentes tienen la misma calificación. Para el segundo caso, equals devolvería false (a menos que decida hacer que el último se vuelva verdadero cuando dos estudiantes diferentes tengan la misma calificación, lo que haría que la función equals tenga un significado engañoso, por no decir un significado incorrecto).
Tenga en cuenta que esta consistencia entre equals y compareTo es opcional, pero se recomienda encarecidamente. De lo contrario, el contrato del Set de interfaces se rompe, lo que hace que su código sea engañoso para otras personas, lo que también puede conducir a un comportamiento inesperado.

Este link puede ser una buena fuente de información con respecto a esta pregunta.

Answer 9

Si no está insertando suficientes elementos para provocar frecuentes reparaciones (o colisiones, si su HashSet no puede redimensionarse), un HashSet sin duda le brinda el beneficio de un acceso de tiempo constante. Pero en conjuntos con mucho crecimiento o contracción, es posible que obtenga 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 )

Answer 10

Una ventaja aún no mencionada de un TreeSet es que tiene una mayor "localidad", que es una forma abreviada de decir (1) si hay dos entradas cerca en el pedido, un TreeSet coloca 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 a menudo una aplicación con una frecuencia similar accede a datos similares.

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

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

Answer 11

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

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

De los javadocs para TreeSet :

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

Answer 12

HashSet es mucho más rápido que TreeSet (tiempo constante frente a 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 permanezca constante en el tiempo
• el rendimiento de la iteración depende de la capacidad inicial y el 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 al que espera que crezca el conjunto.

TreeSet

• garantiza el 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) (implementa SortedSet )
• no ofrece ningún parámetro de ajuste para el rendimiento de iteración
• ofrece algunos métodos prácticos para tratar el conjunto ordenado como first() , last() , headSet() y tailSet() etc.

Puntos importantes:

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

Por lo tanto, la elección del uso depende totalmente de sus necesidades, pero creo que incluso si necesita una colección ordenada, debería preferir que HashSet cree el Conjunto y luego lo convierta en TreeSet.

• por ejemplo, SortedSet<String> s = new TreeSet<String>(hashSet);

Answer 13

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