LinkedHashMap in Java
LinkedHashMap extends HashMap and adds a doubly linked list that runs through all its entries. This linked list preserves either insertion order or access ...
Preserving Order with LinkedHashMap
LinkedHashMap extends HashMap and adds a doubly linked list that runs through all its entries. This linked list preserves either insertion order or access order, depending on how the LinkedHashMap is constructed. By default, it maintains insertion order, meaning entries are iterated in the sequence they were added. This makes LinkedHashMap a predictable and deterministic alternative to HashMap.
When you create a LinkedHashMap with the constructor LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) and pass true for accessOrder, the map reorders entries so that the most recently accessed entry appears last. This behavior makes LinkedHashMap ideal for building a Least Recently Used (LRU) cache.
LinkedHashMap<String, Integer> menu = new LinkedHashMap<>(); menu.put("Coffee", 3); menu.put("Tea", 2); menu.put("Juice", 4); for (String item : menu.keySet()) { System.out.println(item); // Coffee, Tea, Juice in insertion order }
To implement an LRU cache, extend LinkedHashMap and override removeEldestEntry():
class LRUCache<K, V> extends LinkedHashMap<K, V> { private final int capacity; LRUCache(int capacity) { super(capacity, 0.75f, true); this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; } }
Performance-wise, LinkedHashMap has slightly more memory overhead than HashMap because of the linked list pointers. However, iteration over a LinkedHashMap is faster than over HashMap because it follows the linked list rather than scanning the full bucket array.
LinkedHashMap permits one null key and multiple null values, just like HashMap, and is not thread-safe.
Interview tip: When asked how to implement an LRU cache in Java without external libraries, the canonical answer involves extending LinkedHashMap with access-order mode and overriding removeEldestEntry(). This demonstrates knowledge of both data structures and Java's design for extension.