Dinesh on Java

In this article, we will discuss how to design and implement a Least Frequently Used (LFU) cache in Java to get fast fetching and updating items. This LFU cache discards the least frequently used items first when the cache is full and a new item is added which is not there in cache.

Problem Statement

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support two operations like the following:

• get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
• set(key, value) – Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Solution for Least Frequently Used (LFU)

In this article, we will use two data structures one is Map to store key-value pairs and another is Doubly Linked List to store value and frequency of the elements in memory.

Designing LFU strategies

First, we have to focus on some problems associated with the LFU implementation before going to designing.

LFU storage size

Fix the size of the cache to avoid memory limit exceeding. The size should be bounded to take care of memory usages.

Eviction Policy

As the name suggested, we have to evict least frequently used item first from the cache when the cache is full, in case of the same frequency, we have to evict least recently used item from the cache when the cache is full.

Fast Fetching & Updation

We have to choose such data structure that can provide fast fetching and updating and also which supports get and put.

LFU cache Implementation

We have chosen two data structure to implement LFU cache here that is Map and Linked List. HashMap will make get operation in constant time that is O(1) time. But due to the frequency of each item can impact this performance to O(N).

Let’s see its implementation like the following:

package com.dineshonjava.algo.lfu;

/**
 * @author Dinesh.Rajput
 *
 */
public class Node {
	
	long key;
	long value;
	int frequency;
	Node prev;
	Node next;
 
    public Node(long key, long value, int frequency){
        this.key   = key;
        this.value = value;
        this.frequency = frequency;
    }
}

Let’s see the following code for LFUCache class like the following:

package com.dineshonjava.algo.lfu;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Dinesh.Rajput
 *
 */
public class LFUCache {

	Node head;
	Node tail;
	Map<Long, Node> map = null;
	int capacity = 0;

	public LFUCache(int capacity) {
		this.capacity = capacity;
		this.map = new HashMap<>();
	}

	public long get(long key) {

		if (map.get(key) == null) {
			return -1;
		}

		Node item = map.get(key);
		// move to right position according to frequency
		removeNode(item);
		item.frequency = item.frequency+1;
		addNodeWithUpdatedFrequency(item);

		return item.value;
	}

	public void put(Long key, int value) {

		if (map.containsKey(key)) {
			Node item = map.get(key);
			item.value = value;
			item.frequency = item.frequency + 1;
			// move to right position according to frequency
			removeNode(item);
			addNodeWithUpdatedFrequency(item);
		} else {
			if (map.size() >= capacity) {
				// delete head with least frequency and least recently used
				map.remove(head.key);
				removeNode(head);
			}

			// move to right position according to frequency
			Node node = new Node(key, value, 1);
			addNodeWithUpdatedFrequency(node);
			map.put(key, node);
		}
	}

	private void removeNode(Node node) {

		if (node.prev != null) {
			node.prev.next = node.next;
		} else {
			head = node.next;
		}

		if (node.next != null) {
			node.next.prev = node.prev;
		} else {
			tail = node.prev;
		}
	}

	private void addNodeWithUpdatedFrequency(Node node) {
        
		if (tail != null && head != null) {
			Node temp = head;
			while(temp != null) {
				if(temp.frequency > node.frequency) {
					if(temp == head) {
						node.next = temp;
						temp.prev = node;
						head = node;
						break;
					}else {
						node.next = temp;
						node.prev = temp.prev;
						temp.prev.next = node;
						node.prev = temp.prev;
						break;
					}
				}else {
					temp = temp.next;
					if(temp == null) {
						tail.next = node;
						node.prev = tail;
						node.next = null;
						tail = node;
						break;
					}
				}
			}
		} else {
			tail = node;
			head = tail;
		}
	}
}

Let’s test this LFU cache algorithm like the following test class:

package com.dineshonjava.algo.lfu;

/**
 * @author Dinesh.Rajput
 *
 */
public class TestLFUCache {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		System.out.println("Going to test the LFU Cache Implementation"); 
		
		LFUCache cache = new LFUCache(5);
		
		//Storing first value 10 with key (1) in the cache with default frequency. 
        cache.put(1l, 10);  
        
      //Storing second value 20 with key (2) in the cache with default frequency. 
        cache.put(2l, 20);
        
      //Storing third value 30 with key (3) in the cache with default frequency. 
        cache.put(3l, 30);
        
      //Storing fourth value 40 with key (4) in the cache with default frequency. 
        cache.put(4l, 40);
        
      //Storing fifth value 50 with key (5) in the cache with default frequency. 
        cache.put(5l, 50);
        
        
        System.out.println("Value for the key: 1 is " +  
                           cache.get(1)); // returns 10 and increased frequency
  
      // evicts key 2 and store a key (6) with value 60 in the cache  with default frequency. 
        cache.put(6l, 60);  
  
        System.out.println("Value for the key: 2 is " +  
                cache.get(2)); // returns -1 (not found) 
  
        //evicts key 3 and store a key (7) with value 70 in the cache with default frequency. 
        cache.put(7l, 70); 
        
        System.out.println("Value for the key: 3 is " + 
               cache.get(3)); // returns -1 (not found) 
        
        System.out.println("Value for the key: 4 is " +  
                           cache.get(4)); // returns 40 
        
        System.out.println("Value for the key: 5 is " + 
                           cache.get(5)); // return 50 
		
	}

}

Now run this code and see the following output:

Going to test the LFU Cache Implementation
Value for the key: 1 is 10
Value for the key: 2 is -1
Value for the key: 3 is -1
Value for the key: 4 is 40
Value for the key: 5 is 50