A Simple LRU Cache in 5 lines

The applications usually need to cache information in memory. The most often used classes to do this in Java are HashMap and Hashtable. If you need to do any sophisticated caching, then you can use JBoss Cache, OSCache or EHCache. Even if you use an external caching system, you may still want to cache some information locally within an object just to have fast access. The problem with this approach is that, if you are not careful and do not control the size of this in-memory cache, then it may grow too big and affect the performance of your application.

A very simple solution to this problem is to set a maximum size for your in-memory cache and most preferably make it LRU (Least Recently Used). This way you will have a predictable memory utilization and only the items used recently will be kept in the cache.

Starting with JDK 1.4, a new (and very rarely used) collection class was added called LinkedHashMap. There are couple of benefits of using a LinkedHashMap:

• It is possible to preserve the order of items in the map. So, the order of iteration through the items is same as the order of insertion. A special constructor is provided for this purpose. This is very useful when you already have a sorted collection of data and you want to do some processing on it and return it as a Map. Using a TreeMap (the only other map that allows iteration in a given order) is too expensive for this scenario.


• It exposes a method removeEldestEntry(Map.Entry) that may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map. This is what we are going to use to create a LRU cache.

Check out the following snippet for an example of simple LRU cache.

import java.util.*;

public class SimpleLRU {

  private static final int MAX_ENTRIES = 50;

  private Map mCache = new LinkedHashMap(MAX_ENTRIES, .75F, true) {
    protected boolean removeEldestEntry(Map.Entry eldest) {
      return size() > MAX_ENTRIES;
    }
  };

  public SimpleLRU() {
    for(int i = 0; i < 100; i++) {
      String numberStr = String.valueOf(i);
      mCache.put(numberStr, numberStr);

      System.out.print("\rSize = " + mCache.size() + "\tCurrent value = " + i + "\tLast Value in cache = " + mCache.get(numberStr));
      try {
        Thread.sleep(10);
      } catch(InterruptedException ex) {
      }
    }

    System.out.println("");
  }

  public static void main(String[] args) {
    new SimpleLRU();
  }
}

This code creates a simple LRU cache with maximum 50 entries. The magic happens during the creation of the LinkedHashMap where a boolean flag for access order is set to true and the method removeEldestEntry is overridden. Now, if you run the program, you can see that the cache size is fixed to 50 entries and the least recently used entries are removed from the map. It is possible to create a pruning thread to prune the map so you don't always necessarily maintain the maximum number of entries.