ReviseAlgo Logo

Collections Framework

LinkedHashMap

Analyze LinkedHashMap structures, iteration order preservation, and building LRU caches.

Interview: Focuses on LinkedHashMap entry layouts, insertion vs access order, and LRU cache construction using removeEldestEntry.

Last Updated: June 13, 2026 • 10 min read

A LinkedHashMap is a hash table and doubly-linked list implementation of the Map interface. It maintains a doubly-linked list running through all its entries, defining iteration order.

Order Modes

Supports two iteration modes: insertion-order (default) and access-order (recent access to oldest).

LRU Caching

Overriding removeEldestEntry in access-order mode allows automatic eviction of the least recently used element.

Pointer Overhead

Requires before and after pointer references for every entry, increasing memory overhead compared to HashMap.

Building an LRU Cache

LinkedHashMap can be configured as a Least-Recently-Used (LRU) cache:

  1. Instantiate the map with the access-order constructor parameter set to true.
  2. Override the protected method removeEldestEntry(Map.Entry<K,V> eldest).
  3. Return true when the map's size exceeds the cache capacity, triggering the automatic eviction of the oldest entry.

Common Pitfalls

  • Memory leaks in access-order maps: Retaining old, unused entries in maps configured with default insertion-order, which prevents eviction.
  • Assuming concurrent safety: Using LinkedHashMap in multi-threaded caching setups without external synchronization, which corrupts the linked list pointers.

Best Practices

  • Limit size via eviction: Always override removeEldestEntry when using access-order to build memory-bounded caches.
  • Protect against concurrency: Wrap the map in a synchronized collection view (e.g. Collections.synchronizedMap) when sharing it across threads.

Interview-Relevant Information

Q1: What are the two ordering modes supported by LinkedHashMap?
Answer: 1) Insertion-order (default): iteration matches the order elements were added. 2) Access-order: iteration ranges from the least recently accessed elements to the most recently accessed elements.

Q2: How do you build a simple LRU cache using LinkedHashMap?
Answer: Construct the LinkedHashMap with the access-order flag set to true, and override removeEldestEntry(Map.Entry) to return true when the map's size exceeds the target capacity.

Quick Checklist

Can you explain how insertion-order differes from access-order, write a code sample for an LRU cache using LinkedHashMap, and outline its memory characteristics? If yes, you understand LinkedHashMap.

Use Cases

Building memory-bounded local LRU caches for web services.

Implementing order-sensitive response caching layers.

Common Mistakes

Using default insertion-order and expecting Least-Recently-Used eviction behavior.

Neglecting to synchronize LinkedHashMap when using it as a shared cache.