LFU Cache Problem in Java
A caching technique known as Least Frequently Used (LFU) eliminates the least used cache block each time the cache overflows. When a page is found in LFU, its frequency is compared to its predecessor. If the frequency of the new page is higher than that of the old page, it cannot be removed. If all of the previous pages have the same frequency, the page can be removed using the FIFO approach.
The implementation of this algorithm can be effectively handled by the min-heap data structure, which manages insertion, deletion, and updates with logarithmic time complexity. The least recently used cache block can be eliminated to break the lead. The issue has been resolved by utilizing the next two containers:
- The cache is represented by a vector of integer pairs, where each pair has the block number and the number of times it has been used. Because the vector is arranged like a min-heap, we can access the block that is utilized the least frequently in an infinite amount of time.
- The indices of the cache blocks are stored in a hash map, allowing for continuous searching.
For the Least Frequently Used (LFU) cache, create and implement a data structure. Two operations that include the following should be supported by it:
get(key) – Returns -1 if the key does not exist in the cache; otherwise, it returns the Value of the key, which is always positive.
set (key, value) – In the event that the key does not exist, set or insert the Value. Prior to adding a new item, the cache needs to invalidate the least-used item when it fills up. In this particular problem, the least used key would be evicted in the event of a tie (i.e., two or more keys with the same frequency).
Implementation:
Filename: LFUCacheProblem.java
import java.io.*;
import java.util.*;
class Node
{
long keyval;
long val;
int freq;
Node previous;
Node next;
public Node(long keyval, long val, int freq)
{
this.keyval = keyval;
this.val = val;
this.freq = freq;
}
}
class LFUCacheTest
{
Node headnode;
Node tailnode;
Map<Long, Node> map = null;
int capacity = 0;
public LFUCacheTest(int capacity)
{
this.capacity = capacity;
this.map = new HashMap<>();
}
public long get(long keyval)
{
if (map.get(keyval) == null)
{
return -1;
}
Node data = map.get(keyval);
// shift to the suitable position based on frequency
deleteNode(data);
data.freq = data.freq + 1;
NodeAdditionwithNewFrequency(data);
return data.val;
}
public void put(Long keyval, int val)
{
if (map.containsKey(keyval))
{
Node data = map.get(keyval);
data.val = val;
data.freq = data.freq + 1;
// shift to the suitable position based on frequency
deleteNode(data);
NodeAdditionwithNewFrequency(data);
}
else
{
if (map.size() >= capacity)
{
// remove the head that hasn't been used in awhile.
map.remove(headnode.keyval);
deleteNode(headnode);
}
//Remove the head that hasn't been used in a while.
Node node = new Node(keyval, val, 1);
NodeAdditionwithNewFrequency(node);
map.put(keyval, node);
}
}
private void deleteNode(Node node)
{
if (node.previous != null)
{
node.previous.next = node.next;
}
else
{
headnode = node.next;
}
if (node.next != null)
{
node.next.previous = node.previous;
}
else
{
tailnode = node.previous;
}
}
private void NodeAdditionwithNewFrequency(Node node)
{
if (tailnode != null && headnode != null)
{
Node temp = headnode;
while(temp != null)
{
if(temp.freq > node.freq)
{
if(temp == headnode)
{
node.next = temp;
temp.previous = node;
headnode = node;
break;
}
else
{
node.next = temp;
node.previous = temp.previous;
temp.previous.next = node;
node.previous = temp.previous;
break;
}
}
else
{
temp = temp.next;
if(temp == null)
{
tailnode.next = node;
node.previous = tailnode;
node.next = null;
tailnode = node;
break;
}
}
}
}
else
{
tailnode = node;
headnode = tailnode;
}
}
}
public class LFUCacheProblem
{
public static void main(String[] args)
{
System.out.println(" Get start to the testing of the LFU Cache Implementation");
LFUCacheTest cache = new LFUCacheTest(5);
// The initial Value of 10 is being stored in the cache with a default frequency using the key (1).
cache.put(1l, 10);
// The cache is being populated with the default frequency by storing the second Value, which is 20, with the key (2)
cache.put(2l, 20);
// Keeping third value 30 with key (3) at the default frequency in the cache.
cache.put(3l, 30);
// The cache is being populated with the fourth Value, which is 40, and it is being stored with the key (4) using the default frequency
cache.put(4l, 40);
// The cache is being populated with the fifth Value, which is 50, and it is being stored with the key (5) using the default frequency.
cache.put(5l, 50);
System.out.println("The Value for the key: 1 is " + cache.get(1));
// Key 2 is evicted from the cache, while a new key (6) with a value of 60 is stored using the default frequency
cache.put(6l, 60);
System.out.println("The Value for the key: 2 is " + cache.get(2));
// Remove key 3 from the cache and replace it with a new key (7) having a value of 70.
// Set the frequency of the new key to the default value.
cache.put(7l, 70);
System.out.println("The Value for the key: 3 is " + cache.get(3));
System.out.println("The Value for the key: 4 is " + cache.get(4));
System.out.println("The Value for the key: 5 is " + cache.get(5));
}
}
Output:
Get start to the testing of the LFU Cache Implementation
The Value for the key: 1 is 10
The Value for the key: 2 is -1
The Value for the key: 3 is -1
The Value for the key: 4 is 40
The Value for the key: 5 is 50