Tuesday 2 February 2016

Impementing LRU (Least Recent Used) cache is simpler than what you think actually

What is Cache ? 
A cache is an area of local memory that holds a copy of frequently accessed data(limited no of data) so future requests for that data can be served faster.

Next is LRU ? 
This is the technique which discards the least recently used items from the cache.

Implementing LRU cache in Java is as simple as just instantiating java.util.LinkedHashMap.
So before going forward, first of all we need to know the secret of LinkedHashMap
(Refer my previous blog http://secretsinjava.blogspot.in/2015/11/know-linkedhashmap-in-depth.html  for more details).

Now the Secrets :
#1. accessOrder : this is a boolean flag which is passed to LinkedHashMap constructor while instantiating. i.e It keeps the last accessed entry as last of the double linked list which LinkedHashMap used internally.

#2. protected boolean removeEldestEntry(Map.Entry<String, String> eldest);
This is the method of LinkHashMap which decides whether the map should remove its eldest entry or not. For each eldest entry, this method is invoked by put() and putAll() method after inserting a new entry into the map. Default this method returns false to keep all entries added into the map. This method can be overriden by the implentor to decide the no of entries can be kept in the map.

Example : 
Output :
{A4=2552, A5=2444}

Here the overriden method retuns true if size is more than 2. So the map always deletes the oldest entry when a new etry is put into it.

Now we understood the secrets of LinkedHashMap. So now implementing the LRU cache is just creating a LinkedHashMap provided above 2 proprties.
Example :

Output : 
{A6=Theta6, A1=Theta345, A3=Theta11, A2=Theta234}

Here we have given CACHE_SIZE = 4. So the map deletes all eldest entry when size > 4. The final content of the map the last 4 accessed keys.

Thats all about the LRU implementation using java.util.LinkdHashMap.  In place of LinkedHashMap you can also implement your own Map and using double linked internally. 


Please feel free to give your comment/suggestion. Thank you.

No comments:

Post a Comment