LinkedHashMap ¿LIFO o FIFO?

Question

¿Está vinculadoHashMap LIFO o FIFO en la naturaleza? Si mi mapa es de la forma ->

map.put(1,"one"); 
map.put(2,"two"); 

lo que sería el orden si volviese a repetir en el mapa utilizando conjunto de claves ??

EDIT: Creo que realmente confundí dos conceptos diferentes.Dame la siguiente pregunta: ¿Cuál sería el orden en el que encuentro las cantidades usando entryset? Gracias por señalar eso. Por cierto, no tengo la intención de eliminar ninguna entrada.

Answer 1

En un mapa hash vinculado, los elementos en la lista doblemente vinculados se agregan al final (claramente: para preservar el orden de iteración), pero se pueden eliminar de cualquier parte de la lista a medida que los elementos se eliminan del mapa , es incorrecto etiquetar la lista de respaldo (y por extensión: el mapa) como LIFO o FIFO, no es ninguna: no existe un concepto de orden de eliminación en un mapa y, en consecuencia, no se puede suponer una orden de eliminación para la lista de respaldo en un hash vinculado mapa.

Lo que un mapa hash vinculado hace garantiza que iterar sobre su contenido (ya sea: las claves o las entradas) se producirá en el mismo orden en el que se insertaron los elementos en el mapa; desde el documentation:

Esta implementación difiere de HashMap en que mantiene una lista doblemente enlazada que se ejecuta a través de todas sus entradas. 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).

EDIT:

Con respecto a la última edición de la cuestión, a LinkedHashMapgarantías que el orden de iteración de la keySet() será el mismo orden en el que se insertan los elementos: 1, 2 para el ejemplo en la pregunta. Esto no tiene nada que ver con FIFO/LIFO, esos conceptos se relacionan con el orden en que los elementos se eliminan de una estructura de datos, y no están relacionados con el orden de iteración después de insertar elementos.

Answer 2

LinkedHashMap para citar del javadocs es "Hash table and link list implementation of the Map interface, with predictable iteration order". Por lo tanto, keySet devolverá claves basadas en el orden de inserción, esencialmente un FIFO.

Answer 3

De acuerdo con los documentos de Java, si tuviera que iterar sobre el mapa, el conjunto de claves estaría en orden de inserción. Entonces, la primera clave que obtiene es la primera clave ingresada, sobre las claves existentes. Tenga en cuenta que reinsertar un par de clave-valor no cambia la posición original de la clave.

Answer 4

Cuando no se utiliza la orden de acceso (caso estándar) puede considerar LHM como una lista vinculada con acceso muy rápido O (1) por clave.

En ese aspecto es FIFO cuando la orden de acceso no se utiliza (observe los codificadores). Cuando se usa una orden de acceso, el orden de inserción no importa si hay operaciones get() cuando reordenan las entradas. Mire protected boolean removeEldestEntry(Map.Entry<K,V> eldest) eldest = FIFO.

Esencialmente, el LHM es una buena lista doblemente vinculada de Map.Entry<Key, Value> con un índice hash sobre las teclas. Yo mismo nunca uso el vanash HashMap como en su impl actual.tiene muy poco beneficio sobre LHM - menor huella de memoria pero iteración horrible. Java8 (o 9) quizás finalmente pueda arreglar HashMap, con suerte Doug Lea empujará su impl.