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.
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.
Contact Us