¿En qué se diferencia la implementación de LinkedHashMap de HashMap?

Question

Si la complejidad de tiempo de LinkedHashMap es la misma que la complejidad de HashMap, ¿por qué necesitamos HashMap? ¿Cuáles son todos los gastos generales adicionales que tiene LinkedHashMap en comparación con HashMap en Java?

Answer 1

LinkedHashMap tomará más memoria. Cada entrada en un HashMap normal solo tiene la clave y el valor. Cada entrada LinkedHashMap tiene esas referencias y referencias a las entradas siguiente y anterior. También hay que hacer un poco más de limpieza, aunque eso suele ser irrelevante.

Answer 2

• LinkedHashMap mantiene además una lista doblemente enlazada que se ejecuta a través de todas sus entradas, que proporcionará un orden reproducible. Esta lista vinculada define el orden de iteración, que normalmente es el orden en el que las claves se insertaron en el mapa (orden de inserción).
• HashMap no tiene estos costos adicionales (tiempo de ejecución, espacio) y debería preferirse a LinkedHashMap cuando no le importe el orden de inserción.

Answer 3

LinkedHashMap es una estructura de datos útil cuando necesita conocer el orden de inserción de las claves en el Mapa. Un caso de uso adecuado es para la implementación de un caché LRU. Debido al mantenimiento de la orden de LinkedHashMap, la estructura de datos necesita memoria adicional en comparación con HashMap. En caso de que el orden de inserción no sea un requisito, siempre debe elegir el HashMap.

Answer 4

Si la complejidad del tiempo de LinkedHashMap es la misma que la complejidad de HashMap, ¿por qué necesitamos HashMap?

No debe confundir la complejidad con el rendimiento. Dos algoritmos pueden tener la misma complejidad, pero uno puede funcionar mejor que el otro.

Recuerde que f(N) is O(N) significa que:

C1*N <= limit(f(N), N -> infinity) <= C2*N 

donde C1 y C2 son estrictamente constantes positivas. La complejidad no dice nada acerca de cuán pequeños o grandes son los valores C. Para dos algoritmos diferentes, las constantes probablemente sean diferentes.

(Y recuerda que las grandes-O complejidad es sobre el comportamiento/rendimiento como N se hace muy grande. Se le dice nada sobre el comportamiento/rendimiento para las pequeñas N valores.)

---

Una vez dicho esto, la diferencia en el rendimiento entre las operaciones HashMap y LinkedHashMap en casos de uso equivalentes es relativamente pequeña. A menudo, los gastos generales de memoria adicionales que son más relevantes.

Answer 5

Hay otra gran diferencia entre HashMap y LinkedHashMap: La iteración es más eficiente en caso de LinkedHashMap.

como elementos en LinkedHashMap están conectados entre sí de manera iteración requiere un tiempo proporcional al tamaño del mapa, independientemente de su capacidad. Pero en el caso de HashMap; ya que no hay un orden fijo, entonces la iteración sobre él requiere tiempo proporcional a su capacidad.

He puesto más detalles en mi blog.

Answer 6

• redimensionamiento se supone que es más rápido, ya que itera a través de su lista de doble ligado a transferir el contenido a una nueva matriz de tabla.
• containsValue() se reemplaza para aprovechar el iterador más rápido.
• LinkedHashMap también se puede usar para crear un caché LRU. Un LinkedHashMap (capacidad, loadFactor, accessOrderBoolean) constructor especial se proporciona para crear un mapa hash ligado cuyo orden de iteración es el orden en que sus entradas se accedió por última, desde menos recientemente acceder a más recientemente. En este caso, simplemente consultar el mapa con get() es una modificación estructural.

Answer 7

LinkedHashMap hereda HashMap, lo que significa que utiliza la implementación existente de HashMap para almacenar clave y valores en un nodo (objeto de entrada). Aparte de esto, almacena una implementación de lista doblemente vinculada para mantener el orden de inserción en el que se han ingresado las claves.

Parece que este:

nodo de cabecera < ---> nodo 1 < ---> nodo 2 < ---> nodo 3 < ----> nodo 4 < ---> cabecera nodo.

Así que la sobrecarga adicional es mantener la inserción y eliminación en esta lista doblemente vinculada. El beneficio es: la orden de iteración está garantizada para ser un pedido de inserción, que no está en HashMap.

Answer 8

HashMap no mantiene el orden de inserción, por lo tanto, no mantiene ninguna lista doblemente vinculada.

La característica más destacada de LinkedHashMap es que mantiene el orden de inserción de pares de valores-clave. LinkedHashMap usa la Lista doblemente enlazada para hacerlo.

entrada de LinkedHashMap se ve así:

static class Entry<K, V> { 
    K key; 
    V value; 
    Entry<K,V> next; 
    Entry<K,V> before, after;  //For maintaining insertion order  
    public Entry(K key, V value, Entry<K,V> next){ 
     this.key = key; 
     this.value = value; 
     this.next = next; 
    } 
    } 

Al utilizar antes y después - hacemos un seguimiento de entrada recién añadido en LinkedHashMap, que nos ayuda a mantener el orden de inserción.

Antes consulte la entrada anterior y después se refiere a la siguiente entrada en LinkedHashMap.

Para diagramas y explicación paso a paso por favor referirse http://www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html