LFU (Least Frequently Used) Cache Eviction Policy
Below is the implementation of the LFU (Least Frequently Used) Cache Eviction Policy using TreeMap in Java:
Java
// Java Program to implement LFU using TreeMap import java.util.*; class LFUCache<K, V> { private final int capacity; // Store actual key-value pairs private final Map<K, V> cache; // Store frequency of each key private final Map<K, Integer> frequencyMap; // TreeMap for efficient frequency tracking private final TreeMap<Integer, LinkedHashSet<K>> frequencyCounter; public LFUCache( int capacity) { this .capacity = capacity; this .cache = new HashMap<>(); this .frequencyMap = new HashMap<>(); this .frequencyCounter = new TreeMap<>(); } public V get(K key) { if (!cache.containsKey(key)) { return null ; } // Update frequency int frequency = frequencyMap.get(key); frequencyMap.put(key, frequency + 1 ); // Update frequencyCounter frequencyCounter.get(frequency).remove(key); if (frequencyCounter.get(frequency).isEmpty()) { frequencyCounter.remove(frequency); } frequencyCounter.computeIfAbsent(frequency + 1 , k -> new LinkedHashSet<>()).add(key); return cache.get(key); } public void put(K key, V value) { if (capacity <= 0 ) { // Capacity is zero or negative, no caching return ; } if (cache.size() >= capacity) { // Least frequently used element int lowestFrequency = frequencyCounter.firstKey(); K leastFrequentKey = frequencyCounter.get(lowestFrequency).iterator().next(); // Remove from cache and frequency maps cache.remove(leastFrequentKey); frequencyMap.remove(leastFrequentKey); // Remove from frequencyCounter frequencyCounter.get(lowestFrequency).remove(leastFrequentKey); if (frequencyCounter.get(lowestFrequency).isEmpty()) { frequencyCounter.remove(lowestFrequency); } } // Add the new key-value pair to cache cache.put(key, value); // Update frequency maps frequencyMap.put(key, 1 ); // Update frequencyCounter frequencyCounter.computeIfAbsent( 1 , k -> new LinkedHashSet<>()).add(key); } } public class LFUCacheExample { public static void main(String[] args) { LFUCache<Integer, String> lfuCache = new LFUCache<>( 3 ); lfuCache.put( 1 , "One" ); lfuCache.put( 2 , "Two" ); System.out.println( "Get 1: " + lfuCache.get( 1 )); lfuCache.put( 3 , "Three" ); lfuCache.put( 4 , "Four" ); System.out.println( "Get 2: " + lfuCache.get( 2 )); System.out.println( "Get 3: " + lfuCache.get( 3 )); System.out.println( "Get 4: " + lfuCache.get( 4 )); } } |
Output
Get 1: One Get 2: null Get 3: Three Get 4: Four
Explanation of the Program:
- We have implemented the usage of LFU Cache Eviction policy by adding key-value pairs and retrieving those values for different keys.
- We have implemented a Map to store the actual key-value pair and the frequency of each key by using frequencyMap.
- Then we have implemented a TreeMap to track efficient frequency by the use of frequencyCounter.
- After that, by using put() and get() methods, we have added and retrieved key-value pairs to the cache.
- Then the LFUCache class creates an object with capacity of 3, then adds and retrieves the values using get() method.
How to Implement a Cache Eviction Policy using TreeMap in Java?
To enhance application speed, caching is a method that stores frequently visited data in memory. When the cache fills up, a cache eviction policy decides which things must be removed. A sorted map implementation is provided by Java’s TreeMap, which may be used to create a cache with a unique eviction strategy.
A TreeMap makes efficient retrieval and iteration possible by keeping the keys ordered. Here, we will be using a TreeMap with timestamps as keys to design a cache eviction strategy in which the oldest items are removed first.
Contact Us