This article provides a demonstration of implementing an LRU (Least Recently Used) cache eviction strategy in Java, using the LeetCode #146 problem as a reference. Here, we will break down the different steps of LRU creation into easy-to-understand concepts like arrays, hashmaps, and queues.
To start with, let us describe the structure of the LRU.
class LRUCache {
public LRUCache(int capacity) {
}
public int get(int key) {
}
public void put(int key, int value) {
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/As you can see in the above code, LRU should support get and put method like a HashMap. But it should also support a fixed capacity.
Before diving into the LRU cache implementation, let's first create a basic cache. The HashMap is a suitable choice for a cache, offering O(1) time complexity. In real-world scenarios with concurrency concerns, a ConcurrentHashMap might be preferred. However, for simplicity and clarity, we'll use a regular HashMap. An LRU cache, by definition, is a fixed-size cache that removes the least recently used item. However, a HashMap tends to grow in size over time. To address this, we need to implement a restriction on the least recently used item.
To restrict the size of the HashMap, we can remove the last element from it. However, since HashMap doesn't maintain any order, we introduce another data structure - an array. This array helps manage the order of usage, with the element in the front representing the most recently used and the last element being the least recently used (LRU). When the array is full, we remove the last element, shift the others ahead, and insert the currently accessed element at position 0.
To avoid the continuous reordering of the array as elements are added or removed, we can opt for a more efficient data structure: a doubly linked list. Java's LinkedList class serves this purpose, implementing the Queue interface. Utilizing the poll() method removes the oldest element from the queue (FIFO), while offer(key) adds the most recently used element to the front.
The time complexity of inserting or modifying an array is O(n) in the middle or end, while for a linked list, it is O(1).
The core of the LRU implementation lies in the cache update strategy. When the queue size reaches the specified capacity, the update method removes the least recently used element from both the queue and the cache.
void update(int key){
queue.remove(key);
if(cap == queue.size()){
var k = queue.poll();
cache.remove(k);
}
queue.offer(key);
}Here is the complete code using Queue for LRU cache eviction strategy.
class LRUCache {
Map<Integer, Integer> cache = new HashMap<>();
Queue<Integer> queue = new LinkedList<>();
int cap;
public LRUCache(int capacity) {
cap = capacity;
}
public int get(int key) {
Integer val = cache.get(key);
if(val != null){
update(key);
return val;
} else {
return -1;
}
}
public void put(int key, int value) {
cache.put(key, value);
update(key);
}
/**
* LRU strategy
*/
void update(int key){
queue.remove(key); // Remove then add in front.
if(cap == queue.size()){
var k = queue.poll();
cache.remove(k);
}
queue.offer(key);
}
}Even though the cache should be fast with O(1) retrieval for a HashMap, it is actually O(n), which is not what we want. In the above implementation, the queue remove operation works in O(n), making the overall time complexity of get to O(n+1) = O(n).
queue.remove(key)Instead of using a queue, can we use a data structure that provides removal in O(n) time? Yes, we can use a LinkedHashSet instead of Queue to store the access order. Here we only need to change the update(key) method.
Set<Integer> set = new LinkedHashSet<>();
//...
void update(int key){
set.remove(key); // Remove then add in front.
if(cap == set.size()){
var k = set.iterator().next();
set.remove(k);
cache.remove(k);
}
set.add(key);
}Now your queue will fetch data in O(1) time, which is what a cache should do, while maintaining the LRU eviction strategy. LinkedHashSet internally uses a LinkedHashMap to store elements. That gets us to the next section.
What if we can use a single data structure that can work as a HashMap and a LinkedHashSet?
LinkedHashMap provides a way to maintain the order of insertion, which is helpful in implementing an LRU cache without the need for a separate Queue. Since LinkedHashMap can maintain the insertion order, there's no need for a separate Set to track the order. We can rely on the ordering provided by LinkedHashMap.
import java.util.LinkedHashMap;
import java.util.Map;
class LRUCache {
private final Map<Integer, Integer> cache;
public LRUCache(int capacity) {
// Using LinkedHashMap with access order (true) to maintain insertion order
cache = new LinkedHashMap<>(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
// Remove the eldest entry when the capacity is exceeded
return size() > capacity;
}
};
}
public int get(int key) {
return cache.getOrDefault(key, -1);
}
public void put(int key, int value) {
cache.put(key, value);
}
}In this version:
LinkedHashMap is used as the underlying data structure for the cache.LinkedHashMap is used to specify the access order (true) to maintain the order of insertion.removeEldestEntry method is overridden to control the removal of the eldest entry when the capacity is exceeded.LinkedHashMap seems like it was added to java.util to implement LRU cache.