Hashset vs Treeset

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?

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

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.

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).

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

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               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

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.

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 )

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.

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.

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.

¿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

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í.

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