In this tutorial, we'll discuss implementing an LFU (Least Frequently Used) cache. Here's what we'll cover:

What is an LFU Cache?

A brief overview of how an LFU cache works and why it's useful.

How is it Different from LRU Cache?

We'll explain the difference between LFU and LRU caching strategies.

Required Operations

The key operations we need to implement for an LFU cache.

Implementation #1: HashMap

A first pass implementation using a HashMap.

Implementation #2: Singly Linked List

An improved version using a linked list for tracking order.

Implementation #3: Doubly Linked List

Final implementation with a doubly linked list structure.

Alright, let's get started!

LFU Cache

Least Frequently Used or LFU cache is a cache algorithm that manages the replacement of blocks in a cache. The algorithm keeps track of the number of times a block of memory is referenced, and replaces the block with the least frequency once the cache is full.

How LFU Cache is Different From LRU Cache?

The primary difference between Least Frequently and Least Recently Used cache is that the former evicts the memory block with the lowest frequency, even if the block is just recently accessed. Whereas the latter removes the memory block that has not been referenced for the longest time.

Also, check out, Design an LRU Cache.

Design an LFU Cache

The problem statement is to design a data structure for an LFU cache. Our LFUCache class should perform the following operations:

LFUCache(int n)

The constructor initializes the cache object with the required capacity.

int get(int key)

This method gets the value of the key if the key exists in the cache. If not, it returns -1.

void put(int key, int value)

This method does the following:

• If the key is present, it updates the value of the key.
• If the key is not present, it inserts the key along with the value.
• If the cache becomes full, it removes the least frequently used key, and then inserts a new element.
• If the cache becomes full, and there's a tie between the least frequently used key, then the least recently used key would be invalidated.

Implement an LFU Cache Using HashMap

Before moving on to designing the cache using HashMap, let's look at a straightforward approach to implementing an LFU Cache:

• First, initialize an array with the required capacity.
• Each element in an array should contain fields to store key, value, frequency, and timestamp.
• In order to get an element with a particular key, traverse the array, if the element exists, return it, otherwise return -1. The worst-case complexity, in this case, is O(n).
• To insert an element into the array, there can be two possibilities.
• If the array is not full, and the key doesn't exists already, insert the element with frequency 1 and timestamp 0. Update the timestamp of the remaining elements in the array.
• If the array is full, traverse the entire array to find the element with the least frequency to remove it. If there's a tie, then remove the element with the highest timestamp.
• Now insert the new element.

Now, let's discuss a better approach using HashMap.

Here, we'll use maps. One will be to store key-value pairs, and the other to store the count of the times a block is referenced from the cache. In other words, a value is accessed from the key-value map:

1let valueMap = new Map();
2let countMap = new Map();

1LFUCache = function(n) {
2    this.size = n;
3}

To get an element from the valueMap, the implementation is straightforward:

1get(key) {
2
3	if (!this.valueMap.has(key) || this.size == 0) {
4		return -1;
5	}
6
7	this.countMap.set(key, this.countMap.get(key) + 1);
8	return this.valueMap.get(key);
9
10}

If you want to access an element, it will only take O(1) time.

Now, it's time to insert an element in the cache. We've multiple things to consider here:

• If the key already exists, just update the value in valueMap and increment the count in countMap. This will take O(1) time.
• If the key doesn't exists, and the size of the countMap hasn't reached it's maximum capacity, then insert the key and value in valueMap, and set the count to 1 in countMap. This will take O(1) time.
• Now,there can be a case when the cache is full. To handle this, iterate through the countMap to find the key with the lowest count, then remove that entry from both the countMap and the valueMap. This will take O(n) time.

1put(key, value) {
2    if (!this.valueMap.has(key) && this.size > 0) {
3        if (this.valueMap.size === this.size) {
4            let lowestCountEntry = this.countMap.entries().next().value;
5            let lowestCountKey = lowestCountEntry[0];
6            for (let entry of this.countMap.entries()) {
7                if (entry[1] < lowestCountEntry[1]) {
8                    lowestCountKey = entry[0];
9                }
10            }
11            this.countMap.delete(lowestCountKey);
12            this.valueMap.delete(lowestCountKey);
13        }
14        this.valueMap.set(key, value);
15        this.countMap.set(key, 1);
16    } else if (this.size > 0) {
17        this.valueMap.set(key, value);
18        this.countMap.set(key, this.countMap.get(key) + 1);
19    }
20}

Note that there's a problem here. If there exists multiple keys with the same count, then this solution will not work as HashMap doesn't keep track of the insertion order.

With this, we'll move to our next implementation in which we'll be using a Singly Linked List to handle this issue.

Implement an LFU Cache Using Singly Linked List

Here, we'll introduce a new data structure in which we'll insert the key as the count, and value as the list of elements with the same count. For this we'll be using TreeMap as it will store the count in sorted order:

1let sortedCountMap = new Map();

Now accessing the element that has been least recently accessed along with the lowest count will become straightforward. The first key in sortedCountMap will be the lowest frequency. Now to find the element that has been least recently accessed with that frequency, all you have to do is remove the first element from that list. This will take O(1) time.

Now, let's discuss the steps that are different from our previous implementation to get an element:

• First, we'll find the count from the countMap.
• Next, we'll remove the key from the sortedCountMap, and insert it again with a new count value.
• Note that we'll remove the entry of the previous count from the sortedCountMap if that element was the only element in the list.

1private removeEntryFromSortedCountMapIfListIsEmpty(count) {
2    if (this.sortedCountMap.get(count).size() === 0) {
3        this.sortedCountMap.remove(count);
4    }
5}

1get(key) {
2
3	if (!this.valueMap.has(key) || this.size === 0) {
4		return -1;
5	}
6
7	let count = this.countMap.get(key);
8	this.sortedCountMap.get(count).delete(key);
9	this.removeEntryFromSortedCountMapIfListIsEmpty(count);
10
11	if (!this.sortedCountMap.has(count + 1)) {
12		this.sortedCountMap.set(count + 1, new LinkedList());
13	}
14	this.sortedCountMap.get(count + 1).add(key);
15
16	this.countMap.set(key, this.countMap.get(key) + 1);
17
18	return this.valueMap.get(key);
19
20}

Let's discuss the steps that are different from our previous implementation to insert an element:

If the key doesn't exist, and the cache is full, the eviction strategy will be different now:

• We'll first remove the least frequently used key from the sortedCountMap.
• Next, we'll also remove that entry from the sortedCountMap if that key was the only element in the list.
• After that, we'll remove the key/value pair from both the countMap and the valueMap.
• Finally, we'll update the countMap, valueMap, and sortedCountMap.

Let's discuss the case, when the key already exists:

• Now, we'll update the position of the key in sortedCountMap.
• We'll also remove the entry if the key was the only element in the list with that previous count value.

1put(key, value) {
2  if (!this.valueMap.has(key) && this.size > 0) {
3    if (this.valueMap.size === this.size) {
4      let lowestFrequency = [...this.sortedCountMap.keys()][0];
5      let evictKey = this.sortedCountMap.get(lowestFrequency).shift();
6      if (!this.sortedCountMap.get(lowestFrequency).length) {
7        this.sortedCountMap.delete(lowestFrequency);
8      }
9      this.valueMap.delete(evictKey);
10      this.countMap.delete(evictKey);
11    }
12    this.valueMap.set(key, value);
13    this.countMap.set(key, 1);
14    if (!this.sortedCountMap.has(1)) {
15      this.sortedCountMap.set(1, []);
16    }
17    this.sortedCountMap.get(1).push(key);
18  } else if (this.valueMap.has(key) && this.size > 0) {
19    let count = this.countMap.get(key);
20    this.valueMap.set(key, value);
21    this.countMap.set(key, count + 1);
22    this.sortedCountMap.get(count).remove(key);
23    if (!this.sortedCountMap.get(count).length) {
24      this.sortedCountMap.delete(count);
25    }
26    if (!this.sortedCountMap.has(count + 1)) {
27      this.sortedCountMap.set(count + 1, []);
28    }
29    this.sortedCountMap.get(count + 1).push(key);
30  }
31}

There exists a problem in this implementation.

The keys having the same count are in a list. Now to access a key, inorder to update it's entry in the sortedCountMap, we'll have to iterate through the entire list. The worst complexity in this case will be O(n).

To solve this problem, we'll move to our next implementation.

Implement an LFU Cache Using Doubly Linked List

To avoid iterating through the whole list, remove the element directly, and insert it against other count value sortedCountMap, we'll be needing a Doubly Linked List. Note that this will now take O(1) time.

1let sortedCountMap = new Map();

Here, we'll store Node object as the value in valueMap. It will have key, value, and the position of the node in the linked list stored as the value in sortedCountMap:

1var valueMap = {};

1class Node {
2    constructor(key, value) {
3        super();
4        this.key = key;
5        this.value = value;
6    }
7}

Let's have a look at the DoubleLinkedList class:

1class DoubleLinkedList {
2
3  constructor(){
4    this.n = 0;
5    this.head = null;
6    this.tail = null;
7  }
8
9  add(node) {
10
11    if (this.head == null) {
12
13      this.head = node;
14    }
15
16    else {
17
18      this.tail.next = node;
19      node.previous = this.tail;
20
21    }
22    this.tail = node;
23    this.n++;
24
25  }
26
27  remove(node) {
28
29    if (node.next == null) {
30      this.tail = node.previous;
31
32    } else {
33
34      node.next.previous = node.previous;
35
36    }
37
38    if (node.previous == null) {
39
40      this.head = node.next;
41    } else {
42
43      node.previous.next = node.next;
44
45    }
46
47    this.n--;
48
49  }
50
51  size() {
52
53    return this.n;
54
55  }
56
57  getHead() {
58    return this.head;
59  }
60
61}

To get an element, and update the value in sortedCountMap takes O(1) time now:

1get(key) {
2  if (!this.valueMap.has(key) || this.size === 0) {
3    return -1;
4  }
5  let nodeToRemove = this.valueMap.get(key);
6  let node = new Node(key, nodeToRemove.value);
7  let count = this.countMap.get(key);
8  this.sortedCountMap.get(count).remove(nodeToRemove);
9  this.removeEntryFromSortedCountMapIfListIsEmpty(count);
10  this.valueMap.delete(key);
11  this.countMap.delete(key);
12  this.valueMap.set(key, node);
13  this.countMap.set(key, count + 1);
14  this.sortedCountMap.set(count + 1, this.sortedCountMap.get(count + 1) || new DoubleLinkedList());
15  this.sortedCountMap.get(count + 1).add(node);
16  return this.valueMap.get(key).value;
17}

Finally, let's have a look at how a new element can be inserted, or existing can be updated:

1put(key, value) {
2    if (valueMap.has(key) == false && size > 0) {
3
4        var node = new Node(key, value);
5        if (valueMap.size() == size) {
6            var lowestFrequency = Math.min(...sortedCountMap.keys());
7            var nodeToRemove = sortedCountMap.get(lowestFrequency).getHead();
8                sortedCountMap.get(lowestFrequency).remove(nodeToRemove);
9                removeEntryFromSortedCountMapIfListIsEmpty(lowestFrequency);
10
11            var keyToRemove = nodeToRemove.getKey();
12            valueMap.delete(keyToRemove);
13            countMap.delete(keyToRemove);
14        }
15        sortedCountMap.set(1, (sortedCountMap.get(1) || new DoubleLinkedList())).add(node);
16        valueMap.set(key, node);
17        countMap.set(key, 1);
18
19    } else if (valueMap.has(key) && size > 0) {
20        var node = new Node(key, value);
21        var nodeToRemove = valueMap.get(key);
22        var count = countMap.get(key);
23        sortedCountMap.get(count).remove(nodeToRemove);
24        removeEntryFromSortedCountMapIfListIsEmpty(count);
25        valueMap.delete(key);
26        countMap.delete(key);
27        valueMap.set(key, node);
28        countMap.set(key, count + 1);
29        sortedCountMap.set(count + 1, (sortedCountMap.get(count + 1) || new DoubleLinkedList())).add(node);
30
31    }
32}

Conclusion

In this tutorial, we learned to implement an LFU cache using HashMap, Singly Linked List, and Doubly Linked List.

One Pager Cheat Sheet

• An overview of LFU caching and its various implementations will be discussed in this tutorial.
• The LFU Cache algorithm measures frequency and replaces the block with least frequency when the cache is full.
• LFU Cache evicts blocks based on frequency, regardless of recent access, while LRU Cache evicts blocks based on least recent access.
• Design a data structure for an LFU Cache with operations to put and get values, and a constructor to set the initial capacity which also handles replacing the least frequently used and least recently used keys when full.
• The LFU cache evicts the least frequently used memory block, regardless of when it was last accessed, by keeping track of access counters for each key.
• Implementing an LFU Cache using HashMap with O(1) access time and O(n) time to replace entries in a full cache.
• The main advantage of a HashMap is that it provides constant time access to items, regardless of the size of the map.
• We can implement an LFU Cache using a Singly Linked List, which will allow us to access the element that has been least recently used in O(1) time, but the worst complexity for updating will be O(n).
• We can implement an LFU Cache using a Doubly Linked List, taking O(1) time for insertions/updates and lookups.
• It is much more efficient to use a Doubly Linked List to locate the least recently accessed entry with the lowest frequency in O(1) time, as opposed to a Singly Linked List that requires O(n) time.
• We implemented an LFU cache using HashMap, Singly Linked List, and Doubly Linked List.