LRU cache briefly known as Least Recently Used cache is a caching policy that is used to evict elements from the cache to make room for new elements when the cache is full. It removes the least recently used elements first before adding the new one. We will see how to implement it in Javascript.
Cache, as you know, is one of the important concepts of computer science, because it drastically speeds up things by storing things in memory. Thus it can store n single element or whole index to optimize it.
How LRU cache works?
Let us understand how LRU cache works by taking an example of a cache of 4 elements, say 1, 2, 3, 4.
In order to add a new element to this (say 5), we will have to first remove the least recently used which in this case is 1.
Now when you try to access the 2 again it will be shifted to the end again as it will be the most recently used one and 3 will become the least recently used.
Implementing LRU cache in Javascript
We use two data structures to implement an LRU Cache.
- Queue: which is implemented using a doubly-linked list. The most recently used items will be near the front end and the least recent pages will be near the rear end.
- HashMap: With item / page number as key and address of the corresponding queue node as value.
Following is the list of operations that will be formed on the LRU cache.
- get: Returns the cache value for the given item / page number.
- put: Adds a new value in the cache.
- use: Uses one of the existing values and re-arranges the cache by marking the used one as most recently one.
- evict: Removes a value from the cache.
- Insert: A helper function to add value in cache while performing put
Implementation
Base function
class Node {
constructor(key, val) {
this.key = key;
this.val = val;
this.prev = null;
this.next = null;
}
}
const LRUCache = function(cap) {
this.cap = cap;
this.count = 0;
this.head = null;
this.tail = null;
this.cache = new Map();
//other methods will go here
}
This is the order of implementation.
Use
- First get the queue node of the key from the hashmap.
- Then re-arrange the doubly linked list to push the current node at the end or tail marking it as most recently used.
//Uses the cache with given key and marks it as most recently used
this.use = function(key) {
const node = this.cache.get(key);
if (node === this.head) {
return;
} else if (node === this.tail) {
node.prev.next = null;
this.tail = node.prev;
node.prev = null;
node.next = this.head;
this.head.prev = node;
this.head = node;
} else {
if (node.prev) {
node.prev.next = node.next;
}
if (node.next) {
node.next.prev = node.prev;
}
node.next = this.head;
node.prev = null;
this.head.prev = node;
this.head = node;
}
};
Evict
- First get the queue node from the hashmap and then remove this node from it and re-arrange all the nodes.
- Then delete it from the hashmap as well.
//Removes the least recent used cache
this.evict = function() {
const keyToEvict = this.tail ? this.tail.key : null;
if (!this.tail) {
return;
} else if (this.head === this.tail) {
this.head = null;
this.tail = null;
} else {
this.tail.prev.next = null;
this.tail = this.tail.prev;
}
if (keyToEvict) {
this.count--;
this.cache.delete(keyToEvict);
}
};
Insert
- Adds a new element at the appropriate position in the queue and also inserts it in the hashmap.
//Helper function to add new cache in the queue
this.insert = function(key, val) {
const node = new Node(key, val);
this.count++;
this.cache.set(key, node);
if (!this.head) {
this.head = node;
this.tail = node;
} else {
this.head.prev = node;
node.next = this.head;
this.head = node;
}
};
Put
- If the key already exists then uses it and marks it as the most recent one.
- If the capacity is exceeding then removes the least recent one and then insert the new key.
//Adds new item in the list
this.put = function(key, val) {
if (this.cache.has(key)) {
const node = this.cache.get(key);
node.val = val;
this.use(key);
this.cache.set(key, node);
} else {
if (this.count >= this.cap) {
this.evict();
}
this.insert(key, val);
this.use(key); // may not be needed
}
};
Get
- Returns the queue node of the associated key.
//Returns the value of the given key
this.get = function(key) {
if (!this.cache.has(key)) {
return -1;
}
const node = this.cache.get(key);
this.use(key);
return node.val;
};
Display
- Prints all the items of the queue in the least to most order along with its value.
//Display the list
this.display = function(){
let current = this.head;
while(current){
console.log(current.key, current.val);
current = current.next;
}
}
Complete code of LRU cache implementation in Javascript.
class Node {
constructor(key, val) {
this.key = key;
this.val = val;
this.prev = null;
this.next = null;
}
}
const LRUCache = function(cap) {
this.cap = cap;
this.count = 0;
this.head = null;
this.tail = null;
this.cache = new Map();
//Returns the value of the given key
this.get = function(key) {
if (!this.cache.has(key)) {
return -1;
}
const node = this.cache.get(key);
this.use(key);
return node.val;
};
//Adds new item in the list
this.put = function(key, val) {
if (this.cache.has(key)) {
const node = this.cache.get(key);
node.val = val;
this.use(key);
this.cache.set(key, node);
} else {
if (this.count >= this.cap) {
this.evict();
}
this.insert(key, val);
this.use(key); // may not be needed
}
};
//Uses the cache with given key and marks it as most recently used
this.use = function(key) {
const node = this.cache.get(key);
if (node === this.head) {
return;
} else if (node === this.tail) {
node.prev.next = null;
this.tail = node.prev;
node.prev = null;
node.next = this.head;
this.head.prev = node;
this.head = node;
} else {
if (node.prev) {
node.prev.next = node.next;
}
if (node.next) {
node.next.prev = node.prev;
}
node.next = this.head;
node.prev = null;
this.head.prev = node;
this.head = node;
}
};
//Removes the least recent used cache
this.evict = function() {
const keyToEvict = this.tail ? this.tail.key : null;
if (!this.tail) {
return;
} else if (this.head === this.tail) {
this.head = null;
this.tail = null;
} else {
this.tail.prev.next = null;
this.tail = this.tail.prev;
}
if (keyToEvict) {
this.count--;
this.cache.delete(keyToEvict);
}
};
//Helper function to add new cache in the queue
this.insert = function(key, val) {
const node = new Node(key, val);
this.count++;
this.cache.set(key, node);
if (!this.head) {
this.head = node;
this.tail = node;
} else {
this.head.prev = node;
node.next = this.head;
this.head = node;
}
};
//Display the list
this.display = function(){
let current = this.head;
while(current){
console.log(current.key, current.val);
current = current.next;
}
}
};
Input: const lru = new LRUCache(4); lru.put(1, 'a'); lru.put(2, 'b'); lru.put(3, 'c'); lru.put(4, 'd'); lru.display(); lru.use(2); lru.display(); Output: //LRU 4 "d" 3 "c" 2 "b" 1 "a" //After using 2 2 "b" 4 "d" 3 "c" 1 "a"
Time complexity or LRU cache
| # | Get | Put | Use | Evict |
|---|---|---|---|---|
| Average | Θ(1) | Θ(N) | Θ(N) | Θ(N) |
| Worst | O(1) | O(N) | O(N) | O(N) |
Space complexity
| # | space |
|---|---|
| Worst | O(N) |