We created a LRU cache from scratch in an earlier article located here. This is somewhat error prone and takes a reasonable amount of work due to the fact that you have to track additions to the doubly-linked-list and the cache in parallel. Tracking all of the null/not-null empty/full edge cases gets rather burdensome. Enter the Java LinkedHashMap.

The LinkedHashMap Class

The LinkedHashMap class provides functionality by default which is very similar to what we need to form a LRU cache. If we derive from it, we can pass the constructor args (capacity + 1, 1.1f, true). The first two arguments tell it to leave one extra items space and not to re-size until its load is 1.1x the amount of elements, and the third argument tells it to keep its items in access order (most recently accessed at the head) in its backing linked list. These arguments were suggested by Pete Ford in this article. We avoid the resize with 1.1f just for efficiency, and we leave one extra element’s worth of space as elements are added before they are removed (so, for a 5 element cache we would technically have 6 elements for a second when the last element was added, before it is automatically removed. This brings us to our next point…

Automatic Removal

The automatic removal is build in to LinkedHashMap as well, but we need to give it some help. It doesn’t have the removal policy that we need by default. So, we have to explicitly tell it to remove an element when it’s size breaches the capacity we would like to be our maximum. We can tell the underlying LinkedHashMap to use this policy by overriding removeEldestEntry(Map.Entry eldest), as you will see in the below code.

The Code

The following code, minus the main which is just present as an example, is only about 8 lines excluding white space and braces. It creates a class deriving from LinkedHashMap, saves its capacity, and overrides the remove-eldest-entry function as we talked about. It provides all the required functionality from our first article despite its simplicity. So, enjoy!

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

 public class LRUCacheLHM<K,V> extends LinkedHashMap<K,V> {

     private int capacity;

     public LRUCacheLHM(int capacity) {
         //1 extra element as add happens before remove (101), and load factor big
         //enough to avoid triggering resize.  True = keep in access order.
         super(capacity + 1, 1.1f, true);
         this.capacity = capacity;
     }

     @Override
     public boolean removeEldestEntry(Map.Entry eldest) {
         return size() > capacity;
     }

     //--------------------------------------------------------------------
     // That's it; the rest is just a main method to show example usage.
     //--------------------------------------------------------------------

     public static void main(String[] args) {

         //Create cache and add 8 elements.  The first 3 (hey, how, are) should drop off.
         LRUCacheLHM<Integer, String> cache = new LRUCacheLHM<>(5);
         cache.put(0, "Hey");
         cache.put(1, "how");
         cache.put(2, "are");
         cache.put(3, "you");
         cache.put(4, "doing?");
         cache.put(5, "I'm");
         cache.put(6, "good");
         cache.put(7, "thanks");
         System.out.println(cache);

         //Should move 3/you to the head.
         cache.get(3);
         System.out.println(cache);

         //Should put 8/x at the head.
         cache.put(8, "x");
         System.out.println(cache);
     }
 }

The Output

Running this class’s main() method will produce the following output which lets you see the eldest items being removed, and the most recently accessed items being moved forward in the list. The toString() representation of the cache shows its iteration order, and thus its removal order (back of the list first).

 {3=you, 4=doing?, 5=I'm, 6=good, 7=thanks}
 {4=doing?, 5=I'm, 6=good, 7=thanks, 3=you}
 {5=I'm, 6=good, 7=thanks, 3=you, 8=x}