library
advancedLinkedHashMap & LRU Cache
Use insertion-order or access-order LinkedHashMap, and build an LRU cache with it.
LinkedHashMap extends HashMap and maintains a doubly-linked list through all entries, preserving insertion order (default) or access order.
Insertion-order LinkedHashMap = a guest book (signatures in order of arrival). Access-order = a recently-used apps list on your phone (most recently opened moves to front).
Key Concepts
1
Insertion order (default): iteration visits entries in the order they were put(). Useful when you need a map that iterates predictably.
2
Access order: created with new LinkedHashMap<>(capacity, loadFactor, true). Every get() or put() moves the entry to the end of the linked list. The head is the least recently used (LRU) entry. This is the basis for LRU cache implementation.
3
LRU Cache: override removeEldestEntry(Map.Entry) to automatically evict the oldest entry when the map exceeds a size limit:
4
new LinkedHashMap<>(maxSize, 0.75f, true) {
protected boolean removeEldestEntry(Map.Entry e) {
return size() > maxSize;
}
}
5
Performance: same O(1) as HashMap for get/put, with slight overhead for maintaining the linked list. Iteration is O(n) in the number of entries (not capacity, unlike HashMap).
6
Thread safety: not synchronized. For concurrent LRU, use ConcurrentLinkedHashMap (Guava) or Caffeine cache library.