Design a data structure that follows the constraints of a Least Recently Used (LRU) cache
Author: Mohammad J Iqbal
Follow Mohammad J Iqbal on LinkedIn
The Problem description of this code has been taken from leetcode.
If watching the topic on video more convenient to you, you can watch it on YouTube below:
Implement the LRUCache class:
-
LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
-
int get(int key) Return the value of the key if the key exists, otherwise return -1.
-
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache.
If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
Example 1:
Input
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
Constraints:
1 <= capacity <= 3000
0 <= key <= 104
0 <= value <= 105
At most 2 * 105 calls will be made to get and put.
Implementation:
In order to create a cache, we will need to have efficient lookup, we can use a HashMap for that and for cache eviction we can use a Double Ended LinkedList that can also serve as Queue. In the Queue we will be adding new elements at the end of the queue and will remove from the beginning of the queue.
The Node of the Queue looks like below:
package com.spsoft.lrucache;
public class Node {
public int key;
public int value;
Node next;
Node prev;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
We can directly create object of the LinkedList inside the constructor of LRUCache or we can have the LinkedList class implement an interface MyDeque and passing the object of LinkedList as dependency to the LRUCache via constructor overloading.
MyDeque Interface having minimum functionality
package com.spsoft.lrucache;
/* FIFO Double Ended Queue */
public interface MyDeque {
public Node addLast(Node node);
public Node removeFirst();
public void remove(Node node);
public boolean isEmpty();
public int size();
}
Let’s look at the implementation of LinkedList class below:
package com.spsoft.lrucache;
public class DoublyLinkList implements MyDeque {
private int size = 0;
Node first;
Node last;
@Override
public Node addLast(Node node) {
final Node l = last;
//next node of last node should be null
node.next = null;
last = node;
if (l == null)
first = node;
else
{
l.next = node;
node.prev = l;
}
size++;
return node;
}
@Override
public Node removeFirst() {
final Node f = first;
first = f.next;
if (first == null)
last = null;
else
first.prev = null; //make the prev node of current first (f.next) to null
size--;
return f;
}
@Override
public void remove(Node node) {
Node prev = node.prev;
Node next = node.next;
if(prev != null)
prev.next = node.next;
if(next != null)
next.prev = prev;
if(node == last)
last = node.prev;
if(node == first)
first = node.next;
size--;
}
@Override
public boolean isEmpty() {
return size==0;
}
@Override
public int size() {
return this.size;
}
}
The LRUCache class Implementation:
package com.spsoft.lrucache;
import java.util.HashMap;
import java.util.Map;
public class LRUCache {
// Hash map to store key-node pairs for O(1) access
private final Map<Integer, Node> cacheMap;
// Maximum capacity of the cache
private final int capacity;
private MyDeque myDeque;
// Constructor to initialize the LRU cache
public LRUCache(int capacity) {
this(capacity, new DoublyLinkList());
}
public LRUCache(int capacity, MyDeque myDeque) {
this.capacity = capacity;
this.cacheMap = new HashMap<>();
this.myDeque = myDeque;
}
// Retrieves the value of the node associated with the given key
public int get(int key) {
if (!cacheMap.containsKey(key)) {
return -1;
}
Node node = cacheMap.get(key);
// Move the accessed node to the head to maintain LRU order
moveToLast(node);
return node.value;
}
// Adds a new key-value pair to the cache or updates the value if it already exists
public void put(int key, int value) {
if (cacheMap.containsKey(key)) {
Node node = cacheMap.get(key);
node.value = value;
// Move the updated node to the head
moveToLast(node);
} else {
Node newNode = new Node(key, value);
cacheMap.put(key, newNode);
// Add the new node to the head of the linked list
myDeque.addLast(newNode);
if (myDeque.size() > capacity) {
// Remove the least recently used node
Node tail = myDeque.removeFirst();
cacheMap.remove(tail.key); // Also remove it from the map
}
}
}
private void moveToLast(Node node){
myDeque.remove(node);
myDeque.addLast(node);
}
}
Let’s Test the LRUCache class using a Driver Class:
package com.spsoft.lrucache;
public class LRUCacheTest {
public static void main(String args[]){
LRUCacheTest lruCacheTest = new LRUCacheTest();
lruCacheTest.test();
}
private void test(){
int capacity =2;
LRUCache lRUCache = new LRUCache(capacity, new DoublyLinkList());
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
System.out.println(lRUCache.get(1)); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
System.out.println(lRUCache.get(2)); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
System.out.println(lRUCache.get(1)); // return -1 (not found)
System.out.println(lRUCache.get(3)); // return 3
System.out.println(lRUCache.get(4)); // return 4
}
}
You can also test code at Leetcode using below code:
// Leetcode 146. LRU Cache
// https://leetcode.com/problems/lru-cache/description/
import java.util.*;
public class LRUCache {
// Hash map to store key-node pairs for O(1) access
private final Map<Integer, Node> cacheMap;
// Maximum capacity of the cache
private final int capacity;
private MyDeque deque;
// Constructor to initialize the LRU cache
public LRUCache(int capacity) {
this(capacity, new DoublyLinkList());
}
public LRUCache(int capacity, MyDeque deque) {
this.capacity = capacity;
this.cacheMap = new HashMap<>();
this.deque = deque;
}
// Retrieves the value of the node associated with the given key
public int get(int key) {
if (!cacheMap.containsKey(key)) {
return -1;
}
Node node = cacheMap.get(key);
// Move the accessed node to the head to maintain LRU order
moveToLast(node);
return node.value;
}
// Adds a new key-value pair to the cache or updates the value if it already
// exists
public void put(int key, int value) {
if (cacheMap.containsKey(key)) {
Node node = cacheMap.get(key);
node.value = value;
// Move the updated node to the head
moveToLast(node);
} else {
Node newNode = new Node(key, value);
cacheMap.put(key, newNode);
// Add the new node to the head of the linked list
deque.addLast(newNode);
if (deque.size() > capacity) {
// Remove the least recently used node
Node tail = deque.removeFirst();
cacheMap.remove(tail.key); // Also remove it from the map
}
}
}
private void moveToLast(Node node){
deque.remove(node);
deque.addLast(node);
}
}
/* FIFO Double Ended Queue */
interface MyDeque {
public Node addLast(Node node);
public Node removeFirst();
public void remove(Node node);
public boolean isEmpty();
public int size();
}
class Node {
public int key;
public int value;
Node next;
Node prev;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
class DoublyLinkList implements MyDeque {
private int size = 0;
Node first;
Node last;
@Override
public Node addLast(Node node) {
final Node l = last;
//next node of last node should be null
node.next = null;
last = node;
if (l == null)
first = node;
else
{
l.next = node;
node.prev = l;
}
size++;
return node;
}
@Override
public Node removeFirst() {
final Node f = first;
first = f.next;
if (first == null)
last = null;
else
first.prev = null;
size--;
return f;
}
@Override
public void remove(Node node) {
Node prev = node.prev;
Node next = node.next;
if (prev != null)
prev.next = node.next;
if (next != null)
next.prev = prev;
if (node == last)
last = node.prev;
if (node == first)
first = node.next;
size--;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int size() {
return this.size;
}
}
Below is another approach if you don’t want to create a LinkedList, instead want to use a java collection. In this case a LinkedHashSet has been used instead of your custom LinkedList.
import java.util.*;
// Leetcode 146. LRU Cache
// https://leetcode.com/problems/lru-cache/description/
// LRUCache class implementing LRU caching mechanism
public class LRUCache {
class Node{
int key;
int value;
public Node(int key,int value){
this.key = key;
this.value = value;
}
}
Set<Node> cache;
HashMap<Integer, Node> hm;
int capacity;
public LRUCache(int capacity) {
cache = new LinkedHashSet<>();
hm = new HashMap<>();
this.capacity = capacity;
}
public int get(int key) {
int value = -1;
if (hm.containsKey(key)) {
Node node = hm.get(key);
value = node.value;
cache.remove(node); // remove node with O(1)
cache.add(node); // add last
}
return value;
}
public void put(int key, int value) {
if (!hm.containsKey(key)) {
Node nodeToInsert = new Node(key,value);
cache.add(nodeToInsert); //will be adding in the tail/rear or at the end of the list
hm.put(key, nodeToInsert);
if (cache.size() > capacity) {
Node head = cache.iterator().next(); //find the head of the linked Hashset which is also the front.
cache.remove(head); //remove from front/head in the cache
hm.remove(head.key); //remove the head from the hashmap as well
}
} else { //Update exiting value in cache
Node nodeToUpdate = hm.get(key);
cache.remove(nodeToUpdate); //remove the node that needs to be updated in O(1)
nodeToUpdate.value = value; //Update the value of the node
cache.add(nodeToUpdate); //add the note in the rear/end of the linked hash set
}
}
}