Java Program of LRU Cache Implementation using TreeMap
Java
// Java Program to demonstrate LRU Cache Implementation using TreeMap import java.io.*; import java.util.*; class GFG { public static void main(String[] args) { System.out.println( "Going to test the TreeMap LRU " + " Cache Implementation" ); LRUCache cache = new LRUCache( 2 ); // add key-value pairs to the cache cache.put( 1 , 10 ); cache.put( 2 , 20 ); System.out.println( "Value for the key: 1 is " + cache.get( 1 )); // returns 10 cache.put( 3 , 30 ); System.out.println( "Value for the key: 2 is " + cache.get( 2 )); // returns -1 (not found) cache.put( 4 , 40 ); System.out.println( "Value for the key: 1 is " + cache.get( 1 )); // returns -1 (not found) System.out.println( "Value for the key: 3 is " + cache.get( 3 )); // returns 30 System.out.println( "Value for the key: 4 is " + cache.get( 4 )); // return 40 } } class LRUCache { // TreeMap to store entries based on access count TreeMap<Integer, int []> entries = new TreeMap(); // HashMap to store entries with their respective access count HashMap<Integer, int []> map = new HashMap(); int size; int count = 0 ; // constructor to initialize the cache with given capacity public LRUCache( int capacity) { size = capacity; } // method to get the value of a given key from the cache public int get( int key) { if (map.containsKey(key)) { int c = map.get(key)[ 1 ]; entries.remove(c); count++; int val = map.get(key)[ 0 ]; entries.put(count, new int [] { key, val }); map.put(key, new int [] { val, count }); return val; } return - 1 ; } // method to put a key-value pair into the cache public void put( int key, int value) { if (map.containsKey(key)) { int c = map.get(key)[ 1 ]; entries.remove(c); count++; entries.put(count, new int [] { key, value }); map.put(key, new int [] { value, count }); return ; } if (entries.size() == size) { int lcount = entries.firstKey(); int [] lkey = entries.get(lcount); map.remove(lkey[ 0 ]); entries.remove(lcount); } count++; entries.put(count, new int [] { key, value }); map.put(key, new int [] { value, count }); } } |
Going to test the TreeMap LRU Cache Implementation Value for the key: 1 is 10 Value for the key: 2 is -1 Value for the key: 1 is -1 Value for the key: 3 is 30 Value for the key: 4 is 40
Explanation of the Program:
- The
LRUCache
class manages the cache using aTreeMap
to maintain the order of entries based on their access time. - We have also used a
HashMap
to provide fast access to entries. - Then, the
get()
method retrieves the value associated with the given key from the cache. If the key is found, it updates its access time in theentries
map and returns the value. - The
put()
method inserts or updates a key-value pair in the cache. If the cache exceeds its capacity, it takes the least recently used entry, else it adds the new entry to the cache.
Time Complexity:
- The time complexity of this is O(logn).
Note: TreeMap <count, {key,value}> here we are using the count as the key in the TreeMap as TreeMap store the value(key) in sorted (by default it stores that in the increasing order). So here, the “Count” variable is like a counter that increases every time an item is accessed or added to the cache.
With this it helps in identifying the least recently used entry when the cache is full, and eviction is required. If the count value is least, then it will on the top of the TreeMap and then through that we will get the least used.
Implementation of LRU Cache Using TreeMap in Java
In Java, an LRU (Least Recently Used) cache is a data structure that stores a limited number of items and removes the least recently used item when the limit is reached. It is commonly used in computer systems to improve performance by keeping frequently used data readily available,
In this article, we will learn the implementation of LRU cache using TreeMap in Java.
Contact Us