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.
- 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.
- 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
HashSet
y 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
TreeSet
es que tiene una mayor "localidad", que es la abreviatura de decir (1) si dos entradas están cercanas en el orden, a lasTreeSet
ubican 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,
TreeSet
puede ser una opción mucho mejor.fuente
TreeSet
/TreeMap
no 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 .HashSet
es O (1) para acceder a elementos, por lo que ciertamente importa. Pero no es posible mantener el orden de los objetos en el conjunto.TreeSet
es ú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 para
TreeSet
:fuente
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
fuente
null
a tu conjunto de ninguna manera.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);
Basándome en una respuesta visual encantadora en Maps by @shevchyk, aquí está mi opinión:
fuente
La razón por la cual la mayoría de los usos
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 implementarlohashCode
para usarloHashSet
(aunque Effective Java muestra cómo), pero si usa aTreeSet
, debe hacerloComparable
o proporcionar aComparator
. Esto puede ser un problema si la clase no tiene un orden particular.A veces he usado
TreeSet
(o en realidadTreeMap
) 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
TreeSet
es 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.fuente
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 )
fuente
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.
fuente
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.
fuente
Se han dado muchas respuestas, basadas en consideraciones técnicas, especialmente en torno al rendimiento. Según yo, la elección entre
TreeSet
yHashSet
asuntos.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óncompareTo
, que debe ser coherente con lo que devuelve la funciónequals
. Por ejemplo, si tiene un conjunto de objetos de una clase llamada Estudiante, entonces no creo queTreeSet
tendrí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óncompareTo
devolverí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,equals
devolverí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 laequals
función tenga un significado engañoso, por no decir un significado incorrecto).Tenga en cuenta esta coherencia entre
equals
ycompareTo
Es opcional, pero muy recomendable. De lo contrario, el contrato de interfazSet
se 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.
fuente
¿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
fuente
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í.
fuente
fuente