LRU Cache (Least Recently Used)
Objective:
- Add (put) key – value pairs
- retrieve (get) values using keys
- If cache exceeds the its capacity, it removes the least recently used (LRU) item
- HashMap to store key -> value (for fast access , which is giving O(1))
- Linked List (specifically, a double linked list) to track recent usage order
But instead of writing from scratch, we can go with the LinkedHashMap because:
- It maintains the insertion order or access order
- We can configure it to behave like an LRU cache automatically
import java.util.LinkedHashMap;
public class LRUCache {
private final int capacity;
private final LinkedHashMap cache;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new LinkedHashMap<>(capacity, 0.75f, true);
}
public int get(int key) {
return cache.getOrDefault(key, -1);
}
public void put(int key, int val) {
cache.put(key, val);
if (cache.size() > capacity) {
Integer lrukey = cache.keySet().iterator().next();
cache.remove(lrukey);
}
}
}
⚙️ How It Works:
Let’s say capacity = 2
Now:
LRUCache obj = newLRUCache(2);
obj.put(1,1);
obj.put(2,2);
obj.get(1);
So here, when we use ‘put‘ method, it stores into the cache. Present in the cache, here it looks like :-> cache:{1=1, 2=2}.
But when we use get(1); it returns 1.
So here recently used key is 1, and least key is 2. Right now it won’t remove, why because we given capacity is 2, and currently elements are also stored is 2. If we trying to add 3rd element, then least recently used key will be removed.
and why we used here LinkedHashMap<>(intitalcapacity, loadfactor, accessorder);
if accessorder = true means it maintains the order of access, so when you pass the true value in the map, it moves the key to end everytime when it is accessed via get() or put(), in this way, the least recently used key is always the first entry in the map – making it easy to remove