Code4ReferenceList Recently Used(LRU) implementation using LinkedHashMap

Recently I stumbled on one of the Java interview questions:

“Implement List-Recently-Used (LRU) Cache using Java collection class?”

If you have worked on a 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 keeps 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 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 objects 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 gets 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 difficulties 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}

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

JPA Mini Book

Learn how to leverage the power of JPA in order to create robust and flexible Java applications. With this Mini Book, you will get introduced to JPA and smoothly transition to more advanced concepts.

JVM Troubleshooting Guide

The Java virtual machine is really the foundation of any Java EE platform. Learn how to master it with this advanced guide!

Given email address is already subscribed, thank you!
Oops. Something went wrong. Please try again later.
Please provide a valid email address.
Thank you, your sign-up request was successful! Please check your e-mail inbox.
Please complete the CAPTCHA.
Please fill in the required fields.

One Response to "Code4ReferenceList Recently Used(LRU) implementation using LinkedHashMap"

  1. Stas says:

    This is not thread-safe implementation, while cache usually applied in multy-threaded environment.

Leave a Reply


six × 8 =



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use | Privacy Policy | Contact
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.
Do you want to know how to develop your skillset and become a ...
Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

Get ready to Rock!
You can download the complementary eBooks using the links below:
Close