246LRU Cache From LinkedHashMap

Author: Dr. Heinz M. KabutzDate: 2017-02-28Java Version: 1.4Category: Tips and Tricks

Abstract: The LinkedHashMap has an interesting feature, where we can order elements in "access order", rather than the default "insertion order". This allows us to build a light-weight LRU cache.

Welcome to the 246th edition of The Java(tm) Specialists' Newsletter. I felt like a celebrity last week. I was recognized by someone on the flight from Chania to Athens and then by someone else from Athens to Zurich. As I arrived at Voxxed Zurich, I was recognized again. And this continued the whole day long. Java programmers would come up to me and tell me that they love my newsletter or that they are coming to JCrete this year. The next day we travelled to CERN, where we were taken on a tour of CMS. Nope, not the CMS you're thinking of, but a huge machine that detects subatomic particles when protons collide at close to the speed of light. It was a great honour to see this and I felt even more like royalty. This continued the next day, when I gave a lecture at Voxxed CERN to an almost empty main auditorium. Stephen Hawking had spoken in the same lecture theatre. Now some speakers would have been disappointed with the low turnout, but I was blown away and honoured beyond imagination. Next door, my long-time friend Joshua Long was speaking at the same time. He is a real rock star speaker and sucks in crowds like a black hole. It would have been obvious that he should've been given the main room. But they gave it to me instead. Afterwards one of the other speakers told me: "I enjoyed your talk. I tried going to Josh's talk, but it was standing room only, so I came to yours instead." ha ha :-)

My only regret was booking my flight home on the same day, which meant having to leave CERN before lunch. I seriously considered booking new flights, but unfortunately stuck to my original schedule. Getting to my flight was a challenge. I got completely lost trying to find my way out of the CERN buildings. There are so many corridors and parts that are closed. A bit like navigating your car through an old European town with a hundred one-way roads. And on my flight from Geneva to Athens, a Java friend sat in the seat in front of me. What an intoxicating three days of fun :-)

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

LRU Cache From LinkedHashMap

Least-recently-used. LRU. Meaning that elements are removed when they have been used the least recently. As opposed to most recently. It's very confusing, I admit.

LinkedHashMap was already in Java 1.4, but I keep on meeting Java programmers who have never heard of it. Granted, there are a lot of collection classes in the JDK, not to speak of all the third party libraries, such as from Google, Apache and Eclipse. LinkedHashMap is a blend of a linked list and a hash map. By default when you iterate over it, you get back the insertion order. This is useful when you want to build up a dictionary of entries that should be fast to access, but also have a very specific order. This is different to a sorted map such as TreeMap.

An oft overlooked feature of LinkedHashMap is the ability to also retrieve elements in the order in which they were last accessed. A special constructor is used to create this type of LinkedHashMap: new LinkedHashMap(initialCapacity, loadFactor, true) - the true means "accessOrder" instead of the default, which is "insertionOrder". For example, consider this code:

import java.util.*;

public class AccessOrderTest {
  public static void main(String... args) {
    test(new LinkedHashMap<>()); //insertion order
    System.out.println();
    test(new LinkedHashMap<>(16, 0.75f, true)); //access order
    System.out.println();
    test(new TreeMap<>()); //sorted order
    System.out.println();
    test(new HashMap<>()); //undefined order
  }

  private static void test(Map<Integer, String> map) {
    System.out.println(map.getClass().getSimpleName());
    map.put(42, "Meaning");
    map.put(7, "Days Per Week");
    map.put(86400, "Seconds");
    map.put(1, "Highlander");

    System.out.println("map = " + map);
    System.out.println("map.get(7) = " + map.get(7));
    System.out.println("map = " + map);
  }
}

When we run this, we can see that by default, the insertion order is maintained in the first LinkedHashMap. In the second LinkedHashMap, entry 7 goes to the end after being accessed. TreeMap stores entries sorted. And HashMap in an undefined order:

LinkedHashMap
map = {42=Meaning, 7=Days Per Week, 86400=Seconds, 1=Highlander}
map.get(7) = Days Per Week
map = {42=Meaning, 7=Days Per Week, 86400=Seconds, 1=Highlander}

LinkedHashMap
map = {42=Meaning, 7=Days Per Week, 86400=Seconds, 1=Highlander}
map.get(7) = Days Per Week
map = {42=Meaning, 86400=Seconds, 1=Highlander, 7=Days Per Week}

TreeMap
map = {1=Highlander, 7=Days Per Week, 42=Meaning, 86400=Seconds}
map.get(7) = Days Per Week
map = {1=Highlander, 7=Days Per Week, 42=Meaning, 86400=Seconds}

HashMap
map = {86400=Seconds, 1=Highlander, 7=Days Per Week, 42=Meaning}
map.get(7) = Days Per Week
map = {86400=Seconds, 1=Highlander, 7=Days Per Week, 42=Meaning}

So far we have seen that we can store entries in the order in which they were last accessed. But we can also automatically remove the eldest entries if we have exceeded our maximum number. To do that we subclass LinkedHashMap and add a maxEntries field. We also override the removeEldestEntry(Map.Entry<K, V> eldest) method from LinkedHashMap to return true when we have reached our maximum size.

import java.util.*;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
  private final int maxEntries;
  private static final int DEFAULT_INITIAL_CAPACITY = 16;
  private static final float DEFAULT_LOAD_FACTOR = 0.75f;

  public LRUCache(int initialCapacity,
                  float loadFactor,
                  int maxEntries) {
    super(initialCapacity, loadFactor, true);
    this.maxEntries = maxEntries;
  }

  public LRUCache(int initialCapacity,
                  int maxEntries) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR, maxEntries);
  }

  public LRUCache(int maxEntries) {
    this(DEFAULT_INITIAL_CAPACITY, maxEntries);
  }

  // not very useful constructor
  public LRUCache(Map<? extends K, ? extends V> m,
                  int maxEntries) {
    this(m.size(), maxEntries);
    putAll(m);
  }

  protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > maxEntries;
  }
}

Here's an example of how it can be used. Look at the test code and try to imagine what the output will be before scrolling down:

import java.util.*;

public class LRUCacheTest {
  public static void main(String... args) {
    Map<Integer, String> cache = new LRUCache<>(5);
    for (int i = 0; i < 10; i++) {
      cache.put(i, "hi");
    }
    // entries 0-4 have already been removed
    // entries 5-9 are ordered
    System.out.println("cache = " + cache);

    System.out.println(cache.get(7));
    // entry 7 has moved to the end
    System.out.println("cache = " + cache);

    for (int i = 10; i < 14; i++) {
      cache.put(i, "hi");
    }
    // entries 5,6,8,9 have been removed (eldest entries)
    // entry 7 is at the beginning now
    System.out.println("cache = " + cache);

    cache.put(42, "meaning of life");
    // entry 7 is gone too
    System.out.println("cache = " + cache);
  }
}

Here is the output now. You can see that entry 7 jumps around a bit, due to it being accessed directly:

cache = {5=hi, 6=hi, 7=hi, 8=hi, 9=hi}
hi
cache = {5=hi, 6=hi, 8=hi, 9=hi, 7=hi}
cache = {7=hi, 10=hi, 11=hi, 12=hi, 13=hi}
cache = {10=hi, 11=hi, 12=hi, 13=hi, 42=meaning of life}

I hope you found this useful. I was certainly quite surprised when I discovered that you could do this with the LinkedHashMap.

Kind regards

Heinz

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive