Implementation of LRU Cache Using TreeMap in Java - Coding

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.

LRU Cache Implementation using TreeMap

Below is the algorithm of LRU Cache Implementation:

Algorithm:

Initialize a TreeMap (entries) to store entries based on their access count.
Initialize a HashMap (map) to store the mapping of keys to their corresponding values and access counts.
Initialize variables.
Size to represent the maximum capacity of the cache.
Count to keep track of the access count.

get() method: If the key is present in pair,

Get the current access count (c) and value associated with the key.
Remove the entry from map with the old access count.
Increment count.
Update the entry in map with the new access count.
Update the mapping in pair with the new access count.
Return the value associated with the key.

If the key is not present, return -1.

put() method: If the key is already present in pair,

Get the current access count (c) and update the entry in map with the new access count.
Increment count.
Update the entry in map with the new access count.
Update the mapping in pair with the new access count.
Return.

If the key is not present,

If the cache is full (size == size)
Get the least recently used entry from map.
Remove the least recently used entry from both map and pair.
Increment count.
Add the new entry to map with the new access count.
Update the mapping in pair with the new access count.

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 }); 
    } 
} 

Output

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 a TreeMap 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 the entries 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.

Reffered: https://www.geeksforgeeks.org

Java

Related
How to Implement a Custom Order Sorting for Elements in a LinkedHashSet?
How to Create Subsets of a HashSet based on Specific Criteria in Java?
What is Top-Down and Bottom-Up Approach in Java?
How to Retrieve Information about a Network Interface in Java?
How to Handle Null Elements in a PriorityQueue in Java?

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	14