LinkedHashMap was introduced in Java 1.4 as a hybrid data structure combining HashMap's O(1) average lookup with a doubly-linked list that provides deterministic iteration order, either insertion-order or access-order. Its design introduced the removeEldestEntry template method, enabling subclasses to implement LRU (Least Recently Used) eviction policies by returning true when the map exceeds a desired size. However, the implementation was never intended for concurrent use; it inherits HashMap's non-thread-safe nature and adds the complexity of maintaining bi-directional before and after pointers across all entries, including those within treeified buckets.
Under concurrent structural modification—such as one thread inserting while another deletes or resizes—the linked list pointers can be updated non-atomically, leading to a corrupted graph structure where entries form circular references or become orphaned from the main chain. For example, if Thread A updates an entry's after pointer to point to Entry B, but Thread B removes Entry B and updates its before pointer concurrently, the list may end with A pointing to B while B points to C, effectively skipping A or creating a cycle. This corruption causes iterators to spin infinitely (consuming 100% CPU) or skip valid entries silently, rendering the removeEldestEntry policy unreliable because the "eldest" pointer may no longer reflect the true head of the list.
To safely use LinkedHashMap in multi-threaded contexts, you must externally synchronize all operations. For accessOrder=true caches, even get() is a structural modification (it reorders the linked list), so standard ReadWriteLock optimizations for read-only operations are invalid; you must treat all operations as writes or use a global mutex. The safest approach is Collections.synchronizedMap, though you must manually synchronize on the map when iterating. However, for production systems, replace LinkedHashMap with Caffeine or Guava's CacheBuilder, which provide lock-striped or entirely concurrent eviction algorithms without global contention.
public class SafeLRUCache<K, V> { private final Map<K, V> map; public SafeLRUCache(int maxSize) { // LinkedHashMap is NOT thread-safe; synchronize externally this.map = Collections.synchronizedMap(new LinkedHashMap<>(16, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxSize; } }); } // All methods must synchronize on the map public V get(K key) { synchronized (map) { return map.get(key); } } public void put(K key, V value) { synchronized (map) { map.put(key, value); } } // Iteration requires explicit synchronization public void forEach(BiConsumer<K, V> action) { synchronized (map) { map.forEach(action); } } }
A backend service for an e-commerce platform required an in-memory cache for product pricing data to reduce database load. The initial implementation used LinkedHashMap with accessOrder=true and overrode removeEldestEntry to enforce a 1,000-item limit, assuming the map would simply drop old entries automatically. During low-load testing, this worked correctly; however, under production traffic with forty concurrent threads handling flash sales, the service experienced intermittent CPU spikes to 100% and eventual thread starvation.
Thread dumps revealed multiple threads stuck inside LinkedHashMap iterators, traversing circular references in the doubly-linked list caused by concurrent modifications. Specifically, one thread was resizing the internal table while another was updating the access order of an entry, causing an Entry node's after pointer to reference itself, creating an infinite loop during iteration. Additionally, the removeEldestEntry callback occasionally removed the wrong entry because the "eldest" pointer had been corrupted by a concurrent reordering, leading to cache thrashing where recently accessed items were evicted instead of stale ones.
The team first considered wrapping the map with Collections.synchronizedMap. Pros: This requires minimal code changes and ensures atomicity of individual operations by wrapping them in synchronized methods. Cons: It introduces a global monitor, serializing all reads and writes, which reduced throughput from an expected 20,000 operations per second to under 3,000 under contention. Furthermore, iterators still required explicit synchronized(map) blocks, which developers occasionally forgot, leading to ConcurrentModificationException.
Next, they evaluated using ConcurrentHashMap paired with a ConcurrentLinkedQueue to track recency and a background cleanup thread. Pros: This offers high concurrency for reads and writes. Cons: Implementing LRU correctly is error-prone; removing the eldest entry is not atomic with insertion, allowing the cache to temporarily exceed its size limit significantly under high load. Additionally, updating the queue on every get() requires a write operation, creating similar contention points and complexity in maintaining consistency between the queue and the map.
Finally, they benchmarked Caffeine, a high-performance caching library. Pros: It uses a BoundedLocalCache with lock striping and a write-buffer for evictions, allowing concurrent reads without locking and high-throughput writes. It handles LRU/W-TinyLFU eviction atomically without explicit synchronization. Cons: It adds an external dependency and requires learning a new API (e.g., CacheLoader).
The team selected Caffeine after load testing demonstrated it sustained 80,000+ operations per second with p99 latency under 1ms, whereas the synchronized LinkedHashMap bottlenecked at 5k ops/sec with p99 spikes to 500ms. The migration involved replacing the map with Caffeine.newBuilder().maximumSize(1000).build() and registering a removal listener for cleanup logic.
Post-deployment monitoring showed stable CPU usage and zero thread hangs. The cache hit rate improved from 85% to 94% because eviction became deterministic and race-condition-free. The incident highlighted that LinkedHashMap is a single-threaded data structure unsuitable for concurrent LRU caches despite its convenient API.
How does LinkedHashMap maintain the LRU ordering for entries that have been moved into treeified buckets (red-black trees) due to high hash collisions?
LinkedHashMap uses a specialized inner class Entry that extends HashMap.Node and includes before and after pointers. When a bucket treeifies, LinkedHashMap overrides newTreeNode to create TreeNode instances that still inherit from LinkedHashMap.Entry (via LinkedHashMap.TreeNode). Consequently, even when entries are stored in a tree structure for O(log n) collision resolution, they remain nodes in the global doubly-linked list. The afterNodeAccess method updates these pointers after every access, ensuring the LRU chain traverses entries regardless of whether they reside in linked lists or trees within the hash table.
Why does calling get() on a LinkedHashMap with accessOrder=true trigger a ConcurrentModificationException if performed during iteration, while the same operation on a standard HashMap does not?
In accessOrder mode, LinkedHashMap treats get() as a structural modification because it moves the accessed entry to the tail of the doubly-linked list, incrementing modCount. The fail-fast iterator checks this counter and throws immediately upon detecting the change. In contrast, a standard HashMap only increments modCount on insertions, deletions, and resizes; get() is read-only relative to the table structure. This distinction means that even "read-only" logical operations can invalidate iterators in LinkedHashMap, necessitating synchronization for all operations including reads when iterating concurrently.
What specific pointer corruption occurs during concurrent resize (rehashing) in LinkedHashMap that is impossible in a standard HashMap?
During resize, HashMap transfers nodes to a new table array, risking infinite loops in the buckets if done concurrently. LinkedHashMap additionally risks corruption of the before and after pointers that form the auxiliary linked list. If Thread A is relinking entries to preserve order in the new table while Thread B modifies the list (e.g., via remove), Thread A may link an entry to a successor that Thread B has already unlinked, creating a dangling reference or a cycle. Specifically, the after pointer of the header node might point to an entry whose before pointer was nulled by another thread, breaking the list invariant and causing iterators to spin forever when next() follows the broken chain.