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}| Reference: | Code4ReferenceList Recently Used(LRU) implementation using LinkedHashMap from our JCG partner Rakesh Cusat at the Code4Reference blog. |
This is not thread-safe implementation, while cache usually applied in multy-threaded environment.