LRU cache implementation in Java using LinkedHashMap

Hi Folks , 

If you have not worked on this problem before , the following might help you get an understanding. Most of the people fail to recognize that LinkedHashMap provides the support and can be used off-the-self with minimal code.

What is Least Recently Used (LRU) Cache ?? 


First , What is  a cache ?? 

A cache in Computing World, is a place to store something temporarily in a computing environment. Active data from any data Source be it a database or a file system or network , is often cached to shorten data access times, reduce latency and improve input/output (I/O) and hence the application performance.

Cache always has limited memory and can contain only limited number of items. 

Now what happens if a cache is full ?? 

If a cache is full, an item needs to be evicted from the cache. There are different algorithms used in Cache item eviction. The most popular one is the Least-Recently-Used. Hence the name LRU cache. It uses an algorithm to detect and evict items which are the oldest in the cache. The algorithm keep tracks of the items’ last accessed time. It evicts the items which have oldest access timestamp.

LRU Cache Implementation

java.util.LinkedHashMap is quite helpful in implementing a LinkedHashMap. It has a method removeEldestEntry() , that should be overridden. This method gets called after put() and putAll(). 

Based on its return value Map removes the old entry. If this method returns true, then old entry is removed. Otherwise it can stay in the Map. The default implementation of this method returns false and in such a case , the old entries remain in the Map and never get deleted.

Override the method and return true if the number of entries in the map is greater than initial capacity.

Let's write some code now - 

package sampleLru;

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCacheImpl<K, V> extends LinkedHashMap<K, V> {

private static final long serialVersionUID = 1L;
private int capacity;

public LRUCacheImpl(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}

public int getCapacity() {
return capacity;
}

/**
* removeEldestEntry() should be overridden by the user, otherwise it will
* not remove the oldest object from the Map.
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
if (size() > this.capacity) {
System.out.println("Cache is full : Eldest Entry is "
+ eldest.getKey());
}
return size() > this.capacity;
}

}

--------------------------------------------------------------------

package sampleLru;

import java.util.Map;

public class UseLRUCache {

public static void main(String[] args) {

Map<Integer, String> cache = new LRUCacheImpl<>(3);

cache.put(1, "One");

cache.put(2, "Two");

cache.put(3, "Three");

System.out.println(cache + " SIZE " + cache.size());

cache.get(1);

cache.put(4, "Four");

cache.get(3);

System.out.println(cache + " SIZE " + cache.size());

cache.put(5,"Five");

}

}

Console Output : 

{1=One, 2=Two, 3=Three} SIZE 3

Cache is full : Eldest Entry is 2

{1=One, 4=Four, 3=Three}

Cache is full : Eldest Entry is 1

-------------------------------------------------------------------

Let's try to understand the program and the output .

-> Extend the java.util.LinkedHashMap class, define a constructor that takes the capacity of the cache and instantiate a cache of that capacity.

for super(capacity, 0.75f, true); , see here for LinkedHashMap constructor , to understand what it means to send true or false.




accessOrder - the ordering mode - true for access-order, false for insertion-order.

-> Further override the removeEldestEntry method 

UseLRUCache : 

-> Create a cache of capacity 3 , add three elements to the cache with key 1,2 and 3.

-> Access element 1 , now 1 is the recently used entry and then 3 and least recently used entry is 2.

-> Add key 4 , this prints Cache is full : Eldest Entry is 2

-> Access element with key 3.

Now the 1 is the oldest entry then 4 and  the recently accessed is 3.

-> Adding key 5 to the cache , removes the entry 1 from the cache.

Please run the above program to better understand the LRU cache. Thanks for reading . My next blog will be about implementing an LRU cache in java from scratch using other collections.

Happy Learning