Recently I stumble on one of the Java interview questions:
“Implement List-Recently-Used (LRU) Cache using Java collection class?”

If you have worked on similar problem before, then it is really easy for you. Otherwise you start thinking about the best collection class to implement LRU cache. 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

If you know this concept, then skip to the implementation section. There are different algorithms used in Cache item eviction. The most popular one is the Least-Recently-Used. Cache always has limited memory and can contain only limited number of items. It uses an algorithm to detect and evict items which are not worthy to keep. Studies suggest that new items are mostly likely to get accessed soon as compared to older items. LRU is based on this observation. The algorithm keep tracks of the items’ last accessed time. It evicts the items which have oldest access timestamp.

LRU Cache Implementation

LinkedHashMap is really helpful where you want to implement the LRU Cache. Even Sun Java framework uses this class to implement com.sun.tdk.signaturetest.util.LRUCache and sun.security.ssl.X509KeyManagerImpl.SizedMap
For the implementation, removeEldestEntry() method 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 in this case the old entries remain in the Map and never get deleted; It just acts as it general Map collection class.
In most of the implementations this method returns true, if the number of entries in the map is greater than initial capacity.

package code4reference.test;

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

public class LRUCacheImpl extends LinkedHashMap<Integer, String> {
	private static final long serialVersionUID = 1L;
	private int capacity;
	
	public LRUCacheImpl(int capacity, float loadFactor){
		super(capacity, loadFactor, true);
		this.capacity = 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<Integer, String> eldest){
		return size() > this.capacity;
	}
	
	public static void main(String arg[]){
		LRUCacheImpl lruCache = new LRUCacheImpl(4, 0.75f);
		
		lruCache.put(1, "Object1");
		lruCache.put(2, "Object2");
		lruCache.put(3, "Object3");
		lruCache.get(1);
		lruCache.put(4, "Object4");
		System.out.println(lruCache);
		lruCache.put(5, "Object5");
		lruCache.get(3);
		lruCache.put(6, "Object6");
		System.out.println(lruCache);
		lruCache.get(4);
		lruCache.put(7, "Object7");
		lruCache.put(8, "Object8");
		System.out.println(lruCache);
	}
}

println() method prints object in order of their staleness. As you can see in the above code, Object1, Object2 and Object3 are inserted and object1 is accessed just before inserting the Object4 and hence Object1 is printed before the object4 in the first line of the output. When Object5 is inserted the Object2 is get evicted from the list because this object is the oldest in the list. When object3 is accessed, it gets promoted higher than object5 and when object6 is inserted Object1 is evicted. The rest output is self-explanatory, hope you will not find difficult in understanding the output.

{2=Object2, 3=Object3, 1=Object1, 4=Object4}
{4=Object4, 5=Object5, 3=Object3, 6=Object6}
{6=Object6, 4=Object4, 7=Object7, 8=Object8}

If you like this post, please share it using social media buttons given on the left side. Please feel free to leave your comments or suggestions about the above post or the website. Thank you.

,
Trackback

2 comments untill now

  1. anyway a prefer cache that implemented in Google Guava

  2. Thanks Yury, for Sharing it.

Add your comment now