LRU Cache

What is LRU Cache?

Least Recently Used (LRU) is a cache replacement algorithm that replaces cache when the space is full. It allows us to access the values faster by removing the least recently used values. LRU cache is a standard question most of the time, it is usually asked directly but sometimes can be asked with some variation. It is an important algorithm for the operating system, it provides a page replacement method so that we get fewer page faults.

The cache will be of fixed size and when it becomes full we will delete the value which is least recently used and insert a new value. We will implement the get() and put() functions in the LRU cache. The get() function is used to get value from a cache if it is present and if it is not present in the cache then it will return -1 (page fault or cache miss). The put() function will insert key and value in the cache.

Example

Assume that initially, the cache is empty and its size is 2. We will check 1, 2, 3, 2, and 4 in the same order as they are mentioned.
First, it will check 1 in the cache using the get() method, which will return -1, meaning a cache miss occurred. So now the put() method will be called to add 1 to cache and the cache will contain a single value, 1.
Similarly, for 2, a cache miss will also occur, and then put() method will add 2 to cache. Now cache contains two values [1, 2] and it is full.
For 3, a cache miss will occur but the cache is full so we have to remove a value from it to add 3 in the cache. We will remove 1 as it is least recently used and add 3. The cache now contains [2, 3] from which 2 is least recently used.
Next in the list is 2, which is already present in the cache so a cache hit occurs and will return 2, but we also have to update our least recently used value which will now be 3, not 2, since 2 was used recently. This can be done by rearranging values as [3, 2] as we are arranging from left to right according to when it was used.
Now for 4, we will have a cache miss and we will replace 3 with 4 and make 4 shift to the right so our cache is [2, 4].
So in this way, the LRU algorithm replaces different cache values to reduce cache misses or page faults.

How to Implement LRU

LRU should work in O(1) since cache should always be fast, otherwise there would not be any point in implementing caches. To achieve it, we will use two data structures. One is a doubly-linked list and the other is a hash table.

We will implement a doubly-linked list to store cache values. Recently used cache values will be near to the head of the doubly-linked list, and the least recently used cache values will be nearer to the tail.

We will use the hash table to access nodes of the list in O(1). It will store the key-value pair for each key and it will point to one of the nodes’ addresses in the list.

We will start with a doubly-linked list that contains two dummy nodes, head and tail. Head next pointer points on tail and tail previous pointer points to head initially. We will also set the capacity of LRU cache to a fixed value.

Implementation of LRU Cache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class LRUCache {
  public:

    class node {
      public: int key;
      int val;
      node * next;
      node * prev;

      node(int key, int val) {
        this - > key = key;
        this - > val = val;
        this - > next = NULL;
        this - > prev = NULL;
      }
    };

  unordered_map < int,
  node * > mp;
  int capacity;

  /*two dummy nodes to keep track of starting and ending points of list */
  node * head = new node(0, 0);
  node * tail = new node(0, 0);

  LRUCache(int capacity) {
    this - > capacity = capacity;
    head - > next = tail;
    tail - > prev = head;
  }

  /* function to insert node in front of cache */
  void insert(node * currnode) {
    currnode - > next = head - > next; /*adding node in next of head (front of our cache)*/
    head - > next - > prev = currnode;
    head - > next = currnode;
    currnode - > prev = head;
    mp[currnode - > key] = currnode; //update hash table
  }

  /* function to remove a node */
  void remove(node * currnode) {
    mp.erase(currnode - > key);
    currnode - > next - > prev = currnode - > prev;
    currnode - > prev - > next = currnode - > next;
  }

  int get(int key) {
    /* return -1 if key is not present in the cache */
    if (mp.find(key) == mp.end()) {
      return -1;
    }
    /* if key is present , in this case we have to update node so that this new node become most recently used node we can do this by removing it and then adding it again */
    node * currnode = mp[key];
    remove(currnode);
    insert(currnode);
    return currnode - > val;
  }

  void put(int key, int value) {
    /* one case is that when key is already present in the cache then we will update  cache by first removing and then adding a node in front */
    if (mp.find(key) != mp.end()) {
      remove(mp[key]);
    }
    /* another case is when the cache is full, in this case we have to remove the least recently used value*/
    if (mp.size() == capacity) {
      remove(tail - > prev);
    }
    insert(new node(key, value));
  }
};

Here we are initializing LRU cache capacity head->next and tail->prev in the constructor. Head and tail are two dummy nodes that indicate the start and end of the doubly-linked list. Every node has key, value, next, and prev pointers. We are using unordered_map to use a hash table. The insert() and remove() methods are helping methods to add and remove nodes from the doubly-linked list.
The get() method is to get value from a cache if it is present, otherwise it will return -1 in this method. First we are finding the value using unordered_map. Then, if it is present, we are removing it and inserting it again to make it a recently used value and returning its value, and if it is not present we are returning -1.

The put() method is to insert value in the cache. In this we have three cases:

• When the key is already present in the cache then we need to remove it and insert it again to make it a recently used value.

• When the key is not present and the cache is not full then we need to simply add it to the cache.

• When the key is not present and the cache is full then we need to delete the least recently used key from the cache, which can be done by removing the last node which is nearest to the tail of the list.

Overview

LRU cache replacement algorithm provides a good way to replace cache so that cache misses or page faults occur less. It is not hard to implement and to do so we use two data structures, doubly-linked list and hash table (we have used unordered_map in our implementation for hash table). It is an important algorithm to help understand caching and for operating systems.