LRU Cache: From implementation to efficiency

LRU cache

LRU stands for Least Recently Used, it’s one of the cache policies applicable in CDNs and network caching. As its name suggests, the primary mechanism of this policy is to remove the least recently used items out of the cache. In this article, I’ll show you how to implement the LRU from scratch, through a simple to an optimal way.

Target

Because the main focus of this article is on the algorithm, so we will narrow down the cache data type, specifically, keys and values stored in the cache will be positive numbers.

The ultimate goal of the implementation is to create a class LRUCache which includes the following methods:

• get(key) : Returns the value of given key, if there isn’t any matching key, return -1.
• put(key, value) : If there is insufficient capacity, the least recently used item must be removed from the cache, finally, the key and value are inserted into the cache.
• constructor(capacity) : Initializes the capacity of the cache.

The items in cache will be refreshed every time we access their keys.

class LRUCache {
    constructor(capacity: number) {

    }

    get(key: number): number {

    }

    put(key: number, value: number): void {

    }
}

First come up

The crucial aspect of a cache is a hash map to efficiently store and retrieve the values based on keys. So in initialization stage, we can have a cache like this.

class LRUCache {
    private readonly map;
    private readonly capacity;

    constructor(capacity: number) {
        this.map = new Map<number, number>()
        this.capacity = capacity
    }

    get(key: number): number {
        const value = this.map.get(key)
        return value ?? -1
    }

    put(key: number, value: number): void {
        this.map.set(key, value)
    }
}

As the requirement, we need to implement a data structure to track the recently used items. There are two options to consider:

After the comparison, a single linked list is better choice than an array so we will implement a linked list to store all keys in the order of recent usage, from tail to head, it means the least recently used item is at the head of the list.

Here is how the implementation works:

• We create a dump head node to make it easy to handle the first node, a tail pointer to help us add the node to the end of the list efficiently.
• Every time we get a key, if it’s exist in the hash map, the key will be moved to the end of the list.
• When putting an item and the cache is full
  • The first item of the list will be removed. The corresponding key in hash map will be removed too.
  • The new key and value are then inserted into the hash map, a new node with that key and value is also pushed to the end of the list.

class MyListNode {
    constructor(public key: number, public val: number, public next: MyListNode | null = null) { }
}

class LRUCache {
    private readonly map;
    private capacity;
    private head: MyListNode;
    private tail: MyListNode;

    constructor(capacity: number) {
        this.map = new Map<number, number>()
        this.capacity = capacity
        this.head = new MyListNode(-1, -1)
        this.tail = this.head
    }

    get(key: number): number {
        const value = this.map.get(key)
        if (value === undefined) {
            return -1
        }

        // Find the previous node
        let p = this.head
        while (p.next && p.next.key !== key) {
            p = p.next
        }

        // Move the node to the end of the list
        const node = p.next;
        if (!node) {
            return - 1
        }
        p.next = node.next;
        node.next = null
        this.tail.next = node
        this.tail = node;

        return value
    }

    put(key: number, value: number): void {
        const node = new MyListNode(key, value)
        this.tail.next = node
        this.tail = node

        if (this.map.size === this.capacity && this.head.next) {
            const leastRecentlyUsedNode = this.head.next
            this.map.delete(leastRecentlyUsedNode.key)
            this.head.next = leastRecentlyUsedNode.next
        }

        this.map.set(key, value)
    }
}

Let take a look at time and space complexity:

• The list and hash store n items, therefore, the space complexity is O(n).
• get : To find the previous node, we may visit almost the node in the list, so it takes O(n) in time complexity
• put : takes O(1) in time complexity.

Improvement

So it looks quite good at this time, if there is a thing need to be improved, it should be the get method, we need to reduce the time complexity to O(1), but how?

Notice, the get method is taking more time to find the previous node, so if there is a way to access the previous node immediately without going through the nodes, the time complexity will be dramatically optimized to O(1).

• To find an item quickly in O(1) time complexity, we can use a hash map in which the value will be the node of the linked list.
• To immediately get the previous node of current node in list, we can apply double linked list data structure.

After the enhancement, we have the new LRU cache like the figure. The new hash map offers a very quick way to get the node, then we can easily access the previous node in double linked list. We also additionally implement the renew and unlink method to support add a node to the end and remove a node from the list.

class DoubleLinkNode {
    constructor(public key: number, public val: number, public next: DoubleLinkNode | null = null, public prev: DoubleLinkNode | null = null) {}
}

class LRUCache {
    private readonly capacity;
    private readonly map: Map<number, DoubleLinkNode>
    private head: DoubleLinkNode
    private tail: DoubleLinkNode

    constructor(capacity: number) {
        this.capacity = capacity
        this.map = new Map()
        this.head = new DoubleLinkNode(-1, -1)
        this.tail = new DoubleLinkNode(-2, -1)
        this.head.next = this.tail
        this.tail.prev = this.head
    }

    get(key: number): number {
        const node = this.map.get(key)
        if(!node) {
            return -1
        }
        this.unlink(node)
        this.renew(node)
        return node.val
    }

    unlink(node: DoubleLinkNode) {
        const prevNode = node.prev;
        const nextNode = node.next;
        if(!prevNode || !nextNode) {
            return
        }

        prevNode.next = node.next
        nextNode.prev = prevNode
    }

    renew(node: DoubleLinkNode) {
        const prevTail = this.tail.prev
        if(!prevTail) {
            return
        }
        prevTail.next = node
        node.prev = prevTail
        node.next = this.tail
        this.tail.prev = node
    }

    put(key: number, value: number): void {
        let node = this.map.get(key)
        if(node) {
            node.val = value
            this.unlink(node)
            this.renew(node)
        } else {
            node = new DoubleLinkNode(key, value)
            if(this.map.size === this.capacity) {
                this.map.delete(key)
            }
            const nextNode = this.head.next?.next
            if(nextNode) {
                this.head.next = nextNode
                nextNode.prev = this.head
            }
        }
        this.map.set(key, node)
    }
}

Finally, we significantly improved the performance of the get method from time complexity O(n) to O(1), it’s more complicated but it’s quite efficient.

Keys take away

LRU cache is a cache policy which will remove the least recently used item when the capacity is full. It can be implemented by linked list and hash map to efficiently put and get items.

LRU cache can be enhanced by the combination of a double linked list and a hash map which stores keys and nodes following above. The optimization will reduce the time complexity of get method from O(n) to O(1). Through this article, I also hope it can help you understand how to approach a problem from simple state to an optimal solution.