Custom LRU Cache implementation In Javascript

Hello Folks,

It has been a long time since I wrote something new on my blog and now, This year’s resolution is to get back to writing 🙂

On that note, I have tried my hands on a very frequently asked question in the interviews, about custom LRU cache.

LRU cache is known as Least Recently Used cache, This is a caching strategy to determine how to make space in cache when it is full of its capacity. This strategy instructs to keeps the recently used items on the top and least recently used items on the bottom.

The approach to implement LRU Cache is very intuitive, The overall goal is to have a cache, where Reading/writing is constant time operation i.e. Big O(1), so we will use 2 famous data structures:
1. Map for constant lookup.
2. Double linked list for constant-time updates to cache collection.

Steps are as below: [Note this is a very basic idea for the implemenation]

  1. Define a custom implementation for a Node [ key, value, next, prev], remember we are using Double linked list for this purpose to get hold off prev and next pointers in constant time for updates.
  2. Define an LRUCache class and write the below common contracts:
    1. put (key, value)
    2  get (key)
  3. For Put API, Do the following:
    Any time an item is written to cache, We will check for the following:
    1. Ensure List has space, if not clean up by removing Tail node.
    2. If HEAD not exist, then add it on Head and Tail of the list
    3. Else Update HEAD => prev To this new node and make this new node HEAD
    4. Add the key mapping to our Map table for lookup
    5. Increment the length counter
  4. For Get API, Do the following:
    1. Look up the Key in Map table.
    2. Remove the key from List(update both prev/next references, remove from MAP table)
    3. Add it back to list (use PUT API)
    4. return the node.

 

That’s it for a basic implementation of the LRU map. There are tons of other optimization we can add to this above approach like making it time-based(TTL) i.e auto removing nodes if they cross the TTL on them etc.

Here is the implementation using Javascript example, I have also posted this in Github.

class Node {
constructor(key, value, next, prev) {
this.key = key;
this.value = value;
this.next = next ? next : null
this.prev = prev ? prev : null
}
}

class LruCache {

constructor(limit = 5) {
this.limit = limit; // default limit is 5
this.head = null;
this.tail = null
this.size = 0;
this.lookUpTable = {}
}

ensureCapacity() {
if(this.size === this.limit) {
this.makeSpace();
}
}

makeSpace() {
const node = this.lookUpTable[this.tail.key];
if(node) {
this.removeKey(node.key)
}
}

removeKey(key) {
const node = this.lookUpTable[key];
if(!node) {
console.log(“Remove :: no node found”);
return;
}

// e.g
// 1 2 3 4 5 6
// key = 4

// if prev of current node not null
// update 3 to point to 5 instead of 4
if(node.prev) {
node.prev.next = node.next;
}

// if next of current node not null
// update 5 to point back to 3 instead of 4
if(node.next) {
node.next.prev = node.prev;
}

delete this.lookUpTable[key];
this.size–;
}

put(key, value) {
this.ensureCapacity();
const node = new Node(key, value);
if(!this.head) {
this.head = node
this.tail = this.head;
} else {
// we need to add this to head
node.next = this.head;
this.head.prev = node;
this.head = node;
}

this.lookUpTable[key] = node;
++this.size;
}

get (key) {
const node = this.lookUpTable[key];
if (!node) {
console.log(“No key found.”)
return null;
}

this.removeKey(key)
this.put(key);

return node;
}

peek() {
if(!this.head) {
console.log(“Empty cache”);
return;
}

return this.lookUpTable[this.head.key];
}

clear() {
this.size =0;
this.lookUpTable = {}
this.head == null
this.tail = null;
}

log() {
let node = this.head;
while(node) {
const prev = node.prev;
const next = node.next;
let logPrevKey = “.”
let logNextKey = “.”
if(prev) {
logPrevKey = prev.key;
}
if(next) {
logNextKey = next.key;
}
console.log(“[“+logPrevKey+ “]<- [” + node.key +”]” + ” ->[“+ logNextKey+”]”);
node = node.next;
}
}

}
let cache = new LruCache(4);
cache.put(‘1’, 7777);
cache.put(‘2’, 9999);
cache.put(‘3’, 8888);

// should print 3
//console.log(cache.peek());
// do a lookup for 2
//cache.get(‘2’);
// should print 2
//console.log(cache.peek());

cache.log();
console.log(“#############Reading a key”)
cache.get(‘2’);
console.log(“#############Cache Updated”)
cache.log();

cache.get(“44”)

Hope this helps. If you like please leave a comment, it will motivate me to improve.

Peace!

 

 

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.