Deep Dive (java.util) - LinkedHashMap

"HashMap with a memory — it remembers the order you put things in." LinkedHashMap extends HashMap and adds a doubly-linked list threaded through all entries. This gives you HashMap's O(1) performance