LRU Cache Implementation using TreeMap

Java Program of 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.

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.

Similar Reads

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 entries = new TreeMap(); // HashMap to store entries with their respective access count HashMap 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 }); } }...

Tags:

#Java Examples #java-TreeMap #Java #Java Programs #Java

Java Program of LRU Cache Implementation using TreeMap

LRU Cache Implementation using TreeMap

Algorithm:

Implementation of LRU Cache Using TreeMap in Java

Similar Reads

Contact Us