LinkedHashMap LIFO or FIFO?

When access order is not utilized (standard case) you can consider LHM as a linked list w/ very fast access O(1) by key.

In that aspect it is FIFO when access order is unused (look at the c-tors). When access order is used the insertion order doesn't matter if there are any get() operations as they reorder the Entries. Look at protected boolean removeEldestEntry(Map.Entry<K,V> eldest) eldest=FIFO.

Essentially the LHM is a good doubly linked list of Map.Entry<Key, Value> with a hash index over the keys. I myself never use the vanilla HashMap as in its current impl. it has very little benefit over LHM - lower memory footprint but horrid iteration. Java8 (or 9) perhaps may finally fix HashMap, hopefully Doug Lea will push his impl.

LinkedHashMap to quote from the javadocs is "Hash table and linked list implementation of the Map interface, with predictable iteration order" . So the keySet will return keys based on the order of insertion, esssentially a FIFO.

In a linked hash map the elements in the backing doubly-linked list are added at the end (clearly: for preserving iteration order), but can be removed from any part in the list as the elements get removed from the map, it's incorrect to label the backing list (and by extension: the map) as LIFO or FIFO, it's neither - there's no concept of removal order in a map, and consequently no removal order can be assumed for the backing list in a linked hash map.

What a linked hash map does guarantee is that iterating over its contents (be it: the keys or the entries) will occur in the same order in which the elements were inserted in the map; from the documentation:

This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

EDIT :

Regarding the last edit to the question, a LinkedHashMap guarantees that the iteration order of the keySet() will be the same order in which the elements were inserted: 1, 2 for the example in the question. This has nothing to do with FIFO/LIFO, those concepts deal with the order in which elements are removed from a data structure, and they're not related with the iteration order after inserting elements.

According to Java docs, if you were to iterate over the map, the keyset would be in insertion-order. So the first key you get is the first key entered, over the existing keys. Note, reinserting a key-value pair does not change the original key position.