Hashset vs Treeset

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

Esto está en contraste con un HashSet, que extiende las entradas por toda la memoria, sin importar qué sus llaves lo son.

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

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

TreeSet es útil si mantener un orden(en términos de valores y no de orden de inserción) es importante para usted. Pero, como ha señalado, está negociando la 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 log(n) garantizado para el operaciones básicas (add, remove y contains).

1.El HashSet permite el objeto null.

2.TreeSet no permitirá el objeto null. Si intenta agregar valor null, lanzará una excepción NullPointerException.

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

Por ejemplo

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

 HashSet<String> hs = new HashSet<String>();
 hs.add(null); // runs fine

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

La razón por la que la mayoría usa 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 para usted. Si el conjunto contiene clases personalizadas, debe implementar hashCode para usar HashSet (aunque Java efectivo muestra cómo), pero si usa un TreeSet debe hacerlo Comparable o proporcionar un Comparator. Esto puede ser un problema si la clase no tiene un orden particular.

Tengo a veces se usa TreeSet (o en realidad TreeMap) para conjuntos/mapas muy pequeños (

Ahora bien, si necesita ordenar, entonces TreeSet es apropiado, aunque incluso entonces 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.

Si no está insertando suficientes elementos para dar lugar a repeticiones frecuentes (o colisiones, si su HashSet no puede cambiar el tamaño), un HashSet ciertamente le da el beneficio de un acceso de tiempo constante. Pero en sets 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 no me falla. El libro de Okasaki tendría una mejor explicación de la que yo puedo sacar. (O ver su lista de publicaciones)

Las implementaciones de HashSet son, por supuesto, mucho más rápidas less menos sobrecarga porque no hay orden. Un buen análisis de las diferentes implementaciones en Java se proporciona 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 Árbol 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 es decir, el último elemento de la lista enlazada es también el más reciente insertado en el Hash. Esto le permite evitar la irregularidad de un hash desordenado sin incurrir en el aumento del costo de un conjunto de árboles.

El conjunto de árboles es una de 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, según el orden natural. Opcional, puede construir un conjunto de árboles con un constructor que le permite dar a la colección su reglas propias para lo que debe ser el orden (en lugar de confiar en el orden definido por la clase de los elementos) utilizando un Comparador o Comparador

Y A LinkedHashSet es una versión ordenada de HashSet que mantiene una Lista doblemente vinculada a todos los elementos. Usar esta clase en lugar de HashSet cuando te importa el orden de iteración. Cuando se itera a través de un HashSet la el orden es impredecible, mientras que un LinkedHashSet le permite iterar a través de los elementos en el orden en que se insertaron

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

Pero prefiero decir que la elección debe ser impulsada por conceptual consideraciones primero.

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. Así que significa que necesitas anular function compareTo, que debe ser consistente con lo que devuelve function equals. Por ejemplo, si tienes un conjunto de objetos de una clase llamada Student, entonces no creo que un TreeSet tenga sentido, ya que no hay un orden natural entre los estudiantes. Puedes pedirlos por su calificación promedio, está bien, pero esto no es un "pedido natural". Function 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 este último devuelva true cuando dos estudiantes diferentes tienen 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 coherencia entre equals y compareTo es opcional, pero se recomienda encarecidamente. De lo contrario, el contrato de interface Set se rompe, haciendo que su código engañe a otras personas, lo que posiblemente también conduzca a un comportamiento inesperado.

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

¿Por qué tener manzanas cuando puedes tener naranjas?

En serio chicos y chicas - si su colección es grande, leída y escrita a millones de veces, y está pagando por ciclos de CPU, entonces la elección de la colección es relevante SOLO si la NECESITA para funcionar 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? [cue otro discusión]. Así que el punto es si estás feliz usando cualquier colección que hayas elegido, y resuelve tu problema [incluso si no es específicamente el mejor tipo de colección para la tarea] diviértete. 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 tío Bob lo dice

Message Edit ( complete rewrite) Cuando el orden no importa, es cuando. Ambos deberían dar Log (n) - sería de utilidad ver si cualquiera es más del cinco por ciento más rápido que el otro. HashSet puede dar O (1) pruebas en un bucle debe revelar si es.

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