por qué es mejor para convertir hashset a TreeSet luego trabajar directamente con TreeSet

Question

En muchos lugares en la web, incluyendo el sitio web del sol, la siguiente frase aparecen:

Es generalmente más rápido para preformas acciones en hashSet y luego convertir el hashset a treeset.

Bueno, estoy un poco confundido, eso es correcto que añadir los elementos de hashset es o(1) y el objeto de añadir en treeset (árbol negro & rojo) es o(logn) pero cuando puedo convertir el hashset a la TreeSet i necesidad de ordenar mis datos que es o(nlogn) entonces ¿por qué es más rápido trabajar con hashset y luego convertirlo a treeset? Sé que si preformas eliminar o elemento existente entonces hay una diferencia entre el hash y el árbol, pero no creo que sea el factor al que se refiere el sol (al menos eso espero, ya que parece una cosa muy pequeña) otra cosa es que los métodos hashcode pueden no ser tan buenos y agregar elementos al hash no será o(1) o el método hashcode puede ser complicado. por lo general, no entiendo la oración. ¿Alguien puede ayudarme?

Answer 1

Depende de cuántas operaciones suceden en la tabla hash antes de copiar los elementos a la estructura de árbol ordenada. Si todo lo que hace es insertar n elementos distintos en la tabla hash, entonces no, no será más rápido hacerlo y luego cópielos en el árbol :)

Un conjunto hash de elementos se puede convertir en un árbol ordenado ya sea: usando un ordenamiento regular luego construyendo el árbol a partir de eso, o insertando los ítems en el árbol uno a la vez. El primero significa una copia extra/cruce; lo último significa una sobrecarga adicional para mantener un árbol equilibrado (aunque si itera una tabla hash, obtiene los elementos en orden aleatorio, lo que significa que probablemente pueda evitar la mayoría del reequilibrio).

Las tablas hash son típicamente más rápidas que los árboles de búsqueda para las operaciones que son bien compatibles (insertar/modificar/borrar), pero definitivamente no vale la pena hacer lo que recomienda Sun hasta que midas el rendimiento de toda tu aplicación y puedas esperar una aceleración general valiosa de lo que probablemente será una ligera mejora.

Las tablas hash tienen una ventaja aún mayor sobre los árboles clasificados cuando la comparación de claves es costosa (como con cadenas), porque para conjuntos grandes, menos elementos tendrán una colisión hash que un árbol de búsqueda es profunda y porque es posible para almacenar en caché el código hash para las claves que ya están en el conjunto, omitiendo la costosa comparación para (probablemente) todo menos el resultado coincidente.