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.