Designing a Generic LRU Cache
Hey learners! Let’s build a generic LRU(Least Recently Used) Cache with Java. Interviewers usually ask candidates to implement an LRU cache. The important thing to keep in mind is that all operations should be implemented in constant time, i.e
1. Get – fetching a value from the cache using a key, in O(1).
2. Put – putting a new key and value pair in the cache, in O(1).
3. Evict – if the cache is full and more elements are to be inserted, remove the oldest key, in O(1).
Let’s quickly see the project structure. It’s a simple java application. LRUCache.java is the class that implements the caching mechanism.
Code Structure:-
Let’s see the data structure that we are going to use. Since we need to implement fetch operation in constant time, we need to use the map.
But is using a map alone sufficient? Remember that map does not guarantee ordering of elements. To figure out which key we have to evict we need to keep an order of the keys so that we can figure out which is the oldest key. To solve this problem we are going to use DoublyLinkedList.
But why do we need a DoublyLinkedList? Imagine the below scenario and we had a SinglyLinkedList as below:-
Head -> N1 -> N2 -> N3 …..-> N99 -> N100 -> null
Let’s say the Capacity is full and the user adds a new node. Tail is pointing to N100(Least recently used) and should be evicted. Post eviction, node N99 should be the new tail and N99.next should point to null. But how are we going to get to N99? We would have to traverse the entire LinkdedList from Head to N99(1 node before tail) and set tail to node N99 and set N99.next to null. This would make the eviction to O(n).
To perform eviction in constant time, we increase the space and use DoublyLinkedList. Now node N99 can be accessed simply, as now tail.prev points to N99. Problem solved in O(1) by increasing space.
Let’s see the structure of our Cache.
The Cache class:-
class DoublyLinkedListNode<K, V> {
DoublyLinkedListNode<K, V> prev;
DoublyLinkedListNode<K, V> next;
K key;
V data;
}
This takes care of the DoublyLinkedList. Now let’s see how to make use of map. In the implementation class, we will store map, head, and tail as below. Map’s key will be ‘K’ and value will be the entire DoublyLinkedListNode
DoublyLinkedListNode<K, V> head;
DoublyLinkedListNode<K, V> tail;
Map<K, DoublyLinkedListNode<K, V>> map;
Get Operation:-
We want to fetch the value ‘V’ from the cache which corresponds to the key ‘K’. To fetch the value all we have to do is to use the map and get the value corresponding to the key ‘K’. But we also need to put the node to the head. For putting the node which we found, to the head, we make use of doubly linked list. In this example, we have
Head -> c1 <-> c2 <-> c3 <- Tail, and say we want to fetch c2. The new linked list should look like this:-
Head -> c2 <-> c1 <-> c3 <- Tail.
Also, we have to handle 2 corner cases when:-
1. c2 is the head, then no structure change is needed in the linked list.
2. c2 is the tail node.
/**
* If key 'k' is present in the Cache, then:-
* 1. Get the node from DoublyLinkedList.
* 2. Remove the node from between, and put the node in the beginning.
* 3. Adjust the connections.
* else return null.
*/
public V get(K k) {
DoublyLinkedListNode<K, V> node = map.get(k);
// move 'node' to head.
// c1 <-> c2 <-> c3, and 'c2' is the node to be found.
if (node != null) {
DoublyLinkedListNode<K, V> c1 = node.prev;
DoublyLinkedListNode<K, V> c2 = node;
DoublyLinkedListNode<K, V> c3 = node.next;
if (c2 == head) {
return c2.data;
} else if (c2 == tail) {
c1.next = null;
tail = c1;
} else {
c1.next = c3;
c3.prev = c1;
}
head.prev = c2;
c2.next = head;
c2.prev = null;
head = c2; // Brings c2 to the head.
return c2.data;
}
return null;
}
Put Operation:-
Now what if we want to add a new pair
1. The key that we want to insert is already present.
2. The key is not present, hence a new node needs to be created.
In the first case, if the key ‘K’ is already present then all we really have to do is to get the node to the front, as it is getting used. For this, we can just call get(k), which takes care of bringing the node to the front.
When the node that we want to insert is not already present, we will create a new node. Update the head of the linked list with the newly created node and increment the size of the linked list. If the size is already more than the capacity of the cache, then eviction has to be done during the put operation.
/**
* Item is not present in the cache, so we are adding it.
* 1. Adds to the head of the DoublyLinkedList.
* 2. Puts the node in the map.
*/
public void put(K k, V v) {
DoublyLinkedListNode<K, V> node = map.get(k);
if (node != null) {
// Node is present, so update the value.
node.data = v; // Update the value to 'v'.
get(k); // Brings the node to the head.
} else {
// Creates a new node.
if (size == capacity) {
evict();
}
DoublyLinkedListNode<K, V> newNode = new DoublyLinkedListNode<>();
newNode.key = k;
newNode.data = v;
newNode.next = head;
if (head == null) {
tail = newNode;
} else {
head.prev = newNode;
}
head = newNode;
map.put(k, newNode);
size++;
}
}
Evict Operation:-
Evict operation is pretty simple. Remove the key ‘K’ from the map, remove the tail node from the linked list, as the tail is always the least recently used node in this implementation, and decrease the size.
/**
* Evicts the last item from the cache, in case the cache capacity is full.
*/
private void evict() {
map.remove(tail.key);
DoublyLinkedListNode<K, V> prevNode = tail.prev;
prevNode.next = null;
tail.prev = null;
tail = prevNode;
size--;
}
Testing:-
Testing can be performed using TestLRUCache.java. You can get it from GitHub using the below link. I have covered the corner cases which can occur in LRU cache.
While running the tests ensure that you add -ea to the VM options, or else assert won’t get executed.
.
.
// Enable -ea in VM arguments before testing.
testSingleNodeCache();
testDoubleNodeCache();
testTripleNodeCache();
testTripleNodeCache_overflowingCapacity();
.
.
You can checkout the entire codebase along with tests from the GitHub.
Keep Learning! Stay Sharp!
