AtticCollectionsMaps
LinkedHashMap
Doubly-linked entry chaining, insertion order, access ordering, and building an LRU cache
LinkedHashMap<K, V> extends HashMap by maintaining a doubly-linked list through all its entries. It can maintain elements in the order they were inserted, or in the order they were last accessed (ideal for LRU caches).
Access Order vs Insertion Order
By default, iteration follows the order in which keys were inserted. Constructing with accessOrder = true moves an entry to the tail of the list whenever it is accessed via get() or updated via put().
public class SimpleLruCache<K, V> extends LinkedHashMap<K, V> {
private final int maxCapacity;
public SimpleLruCache(int capacity) {
// initialCapacity, loadFactor, accessOrder (true = LRU access order)
super(capacity, 0.75f, true);
this.maxCapacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
// Automatically evicts the least recently accessed element when size exceeds limit
return size() > maxCapacity;
}
}Map<Integer, String> cache = new SimpleLruCache<>(3);
cache.put(1, "A");
cache.put(2, "B");
cache.put(3, "C");
cache.get(1); // Accesses 1, moving it to tail of recency list
cache.put(4, "D"); // Exceeds capacity 3 -> Evicts key 2!
System.out.println(cache.keySet()); // [3, 1, 4]Complexity Profile
| Operation | Time Complexity | Notes |
|---|---|---|
get() / put() / remove() | O(1) average | Hash bucket lookup + pointer re-linking |
containsValue() | O(n) | Linear scan |
- Memory Overhead: Marginally higher than
HashMapdue to storing two pointer references per entry. - Null Allowance: Permits one
nullkey and multiplenullvalues.