LRU Cache: From implementation to efficiency
Tags: performance, architecture, algorithms
Published: 2024-02-06 16:07:02

## 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.*
> 

```tsx
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.

```tsx
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:


| Data Structure   | Pros                    | Cons                                                       |
|------------------|-------------------------|------------------------------------------------------------|
| **Array**            | - Simple implementation | - Finding an item has a time complexity of _O(n)_            |
|                  |                         | - Moving or deleting an item has a time complexity of _O(n)_ |
|                  |                         | - Fixed space in RAM → Can easily lead to out-of-memory situations with large data |
| **Single Linked List** | - More complex        | - Finding an item has a time complexity of _O(n)_            |
|                  |                         | - Moving or replacing an item has a time complexity of _O(n)_|
|                  |                         | - Flexible space in RAM                                    |


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.


![LRU cache uses hash map and linked list](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fcnq6zboabg7xdu9yqar.png)


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.

```tsx
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.

![LRU after enhancement](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/x93je7bd6ecx0rzis4yv.png)

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.

```tsx
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.