LinkedHashMap vs HashMap! = LinkedList vs ArrayList

Question

He leído que LinkedHashMap tiene una velocidad de iteración más rápida que HashMap porque sus elementos están doblemente vinculados entre sí. Además, debido a esto, LinkedHashMap es más lento al insertar o eliminar elementos. Presumiblemente porque estos enlaces también necesitan ser actualizados.

Aunque puedo ver una analogía con LinkedList vs ArrayList, porque los elementos de LinkedList también están doblemente ligado a, leí que itera lento de ArrayList, y tiene tiempos de inserción y eliminación más rápidas.

¿Por qué es esto? Quizás estoy cometiendo un error en alguna parte?

¡Salud!

Answer 1

La analogía no funciona. LinkedList y ArrayList son dos implementaciones no relacionadas de una lista. LinkedHashMap, sin embargo, es la misma estructura de datos que un HashMap pero con una LinkedList entrelazada para hacer que la iteración sea más rápida y consistente.

La razón de que la iteración de LinkedHashMap sea más rápida que la iteración de HashMap es que la iteración de HashMap tiene que iterar sobre todos los intervalos, incluso los vacíos. El hecho de que LinkedHashMap tiene una lista que apunta a los datos significa que puede omitir los intervalos vacíos. La lista en LinkedHashMap es una lista vinculada porque los tiempos de eliminación permanecen constantes (en lugar de O (n) si se trata de alguna lista respaldada por arrray).

Answer 2

Algunos detalles:

El orden iterador para LinkedHashMap es la misma que para la inserción en el mapa. Por lo tanto, la parte LinkedList solo tiene que "insertarse" al final (que es O (1) para una lista vinculada que realiza un seguimiento de la cola), y la parte Map solo hace una inserción de mapa que es O (1). Una inserción de lista enlazada general es O (N) y una inserción de ArrayList tiene que copiar en matriz el contenido en 1 ranura antes de que se pueda insertar.

Answer 3

Los tiempos de ejecución de las listas vinculadas (accediendo a cada elemento) son "teóricamente" lo mismo que una lista de arreglos. Ambos requieren O (n) (Big-O Notation) tiempo de ejecución. Sin embargo, dado que la asignación de memoria para las matrices se realiza a través de un bloque continuo de memoria (los elementos de las listas vinculadas se asignan individualmente y pueden estar en cualquier lugar de la memoria), el almacenamiento en caché entra en vigencia.

Answer 4

Para iterar en una lista vinculada, debe seguir cada referencia (enlace) en cada elemento. Estas referencias pueden apuntar casi a cualquier parte, no hay garantía de que el siguiente elemento siga al actual en la memoria, lo que es malo para el almacenamiento en caché. Debido a que cada referencia debe recuperarse, es más lenta. Las matrices son continuas en la memoria y el siguiente elemento es solo la ubicación de la memoria del elemento actual incrementado con el tamaño del elemento.

Para una lista doblemente vinculada, la inserción en cualquier lugar de la matriz es muy rápida porque solo deben cambiarse las referencias del elemento anterior y siguiente. Una matriz, por otro lado, es más lenta porque la inserción en cualquier punto hará que toda la matriz se copie para dejar espacio para el nuevo elemento. Incluso si se agrega un elemento, también se copiará toda la matriz cuando no haya suficiente memoria continua asignada para la matriz más el elemento recién agregado.

Notará especialmente las diferencias de inserción al tratar con grandes conjuntos de datos. No importa qué tan rápido sea arraycopy(), una lista doblemente enlazada siempre es más rápida para la inserción. Debido a que los HashMaps raramente se repiten y dependen de la inserción y el orden, una lista doblemente enlazada puede darle un aumento de rendimiento.