Colecciones Java que mantienen el orden de inserción

Question

¿Por qué algunas estructuras de datos de colección no mantienen el orden de inserción? ¿Qué es lo especial logrado en comparación con mantener el orden de inserción? ¿Ganamos algo si no mantenemos el orden?

Answer 1

Rendimiento. Si desea el orden de inserción original, existen las clases LinkedXXX, que mantienen una lista vinculada adicional en orden de inserción. La mayoría de las veces no te importa, entonces usas un HashXXX, o quieres un orden natural, entonces usas TreeXXX. En cualquiera de esos casos, ¿por qué debería pagar el costo adicional de la lista vinculada?

Answer 2

Depende de lo que necesita para que la implementación funcione bien. Por lo general, el orden de inserción no es interesante, por lo que no es necesario mantenerlo para que pueda reorganizarlo para obtener un mejor rendimiento.

En el caso de Maps, generalmente se utiliza HashMap y TreeMap. Mediante el uso de códigos hash, las entradas se pueden poner en pequeños grupos fáciles de buscar. TreeMap mantiene un orden ordenado de las entradas insertadas a costa de una búsqueda más lenta, pero más fácil de ordenar que un HashMap.

Answer 3

Cuando utiliza un HashSet (o un HashMap) los datos se almacenan en "cubos" basados ​​en el hash de su objeto. De esta forma, es más fácil acceder a sus datos porque no tiene que buscar estos datos en particular en todo el conjunto, solo tiene que buscar en el cubo correcto.

De esta manera puede aumentar el rendimiento en puntos específicos.

Cada implementación de Collection tiene su particularidad para que sea mejor usarla en ciertas condiciones. Cada una de esas particularidades tiene un costo. Entonces, si realmente no lo necesita (por ejemplo, el orden de inserción), es mejor que utilice una implementación que no lo ofrece y que se ajusta mejor a sus requisitos.

Answer 4

no puedo citar una referencia, pero por diseño los List y Set implementaciones de la interfaz Collection son básicamente extensibles Array s. Como Collections de forma predeterminada ofrecen métodos dinámicamente agregue y elimine los elementos en cualquier punto - que Array s no - el orden de inserción puede no conservarse. Por lo tanto, como hay más métodos para la manipulación de contenido, existe una necesidad de implementaciones especiales que mantengan el orden.

Otro punto es el rendimiento, ya que el mejor rendimiento Collection podría no ser el mismo, lo que conserva su orden de inserción. Sin embargo, no estoy seguro de cómo exactamente Collections administrar su contenido para aumentar el rendimiento.

Así que, en resumen, las dos razones principales que se me ocurre por qué hay orden de preservación Collection implementaciones son:

1. arquitectura Rendimiento Clase

Answer 5

• El orden de inserción
• no se mantiene inherentemente en hash tables - así es como funcionan (lea el artículo vinculado para comprender los detalles). Es posible agregar lógica para mantener el orden de inserción (como en el LinkedHashMap), pero eso requiere más código, y en el tiempo de ejecución más memoria y más tiempo. La pérdida de rendimiento generalmente no es significativa, pero puede ser.
• Para TreeSet/Map, la razón principal para usarlos es el orden de iteración natural y otras funcionalidades agregadas en la interfaz SortedSet/Map.

Answer 6

¿Por qué es necesario mantener el orden de inserción? Si usa HashMap, puede obtener la entrada al key. No significa que no proporciona clases que hacen lo que quieres.

Answer 7

Las colecciones no mantienen el orden de inserción. Algunos solo predeterminan agregar un nuevo valor al final. Mantener el orden de inserción solo es útil si le da prioridad a los objetos o los usa para ordenar objetos de alguna manera.

En cuanto a por qué algunas colecciones lo mantienen por defecto y otros no, esto es principalmente causado por la implementación y solo algunas veces parte de la definición de colecciones.

• Listas mantener el orden de inserción como se acaba de añadir una nueva entrada al final o al principio es la aplicación más rápida del método add (Object).

• Conjuntos Las implementaciones hashset y TreeSet no mantienen orden de inserción como los objetos se clasifican para la búsqueda rápida y el orden de inserción mantener requeriría memoria adicional. Esto resulta en una ganancia de rendimiento ya que el orden de inserción casi nunca es interesante para Sets.

• ArrayDeque un deque se puede utilizar para sencilla que y apilar por lo que quieren tener '' First In First Out '' o '' por primera vez en el último lugar '' comportamiento, ambos requieren que el ArrayDeque mantiene el orden de inserción. En este caso, el orden de inserción se mantiene como una parte central del contrato de clases.

Answer 8

Theres una sección en el libro de cocina de Java O'Reilly llamado "Evitar la necesidad de ordenar" La pregunta que se debería hacer en realidad es lo contrario de su pregunta original ... "Qué ganamos algo por la clasificación? " Se requiere un gran esfuerzo para ordenar y mantener ese orden. La clasificación segura es fácil, pero generalmente no se escala en la mayoría de los programas. Si va a manejar miles o decenas de miles de solicitudes (insrt, del, get, etc.) por segundo, ya sea que esté utilizando una estructura de datos clasificada o no, va a ser importante.

Answer 9

Bien ... entonces estas publicaciones son antiguas en comparación con ahora, pero el pedido de inserción es necesario según su necesidad o los requisitos de la aplicación, así que solo use el tipo correcto de colección. En su mayor parte, no es necesario, pero en una situación en la que necesita utilizar objetos en el orden en que fueron almacenados, veo una necesidad definitiva. Creo que el orden importa cuando estás creando, por ejemplo, un asistente o un motor de flujo o algo de esa naturaleza en el que tienes que ir de un estado a otro o algo así. En ese sentido, puede leer cosas de la lista sin tener que hacer un seguimiento de lo que necesita a continuación o recorrer una lista para encontrar lo que desea. Ayuda con el rendimiento en ese sentido. Importa o de lo contrario estas colecciones no tendrían mucho sentido.

Answer 10

algunos Colección no mantienen el orden debido a que calculan el hashCode del contenido y lo almacenan en consecuencia en el depósito correspondiente.