Creating a simple cache in Java

As part of the Collection suite in Java, there's LinkedHashSet and LinkedHashMap. These classes store the items in the order in which you insert or access them (into a doubly linked list). This is quite useful for caching, so we'll take a look at how this could conceptually be used to make a simple cache in Java.

Caching libraries

Before I begin, I should note that this is just for fun. In reality, you may want to use a performant library (such as an implementation that's synchronised) for caching, such as Caffeine (which the COVID-19 Dashboard uses) or Guava. Having said that, a LinkedHashMap can also be useful: it formed the basis of the more performant ConcurrentLinkedHashMap (use Caffeine instead, which is by the same author).

How do they work?

Before we jump into the caching part, let's see how they work.

LinkedHashMap<String, LocalDate> customers = 
	new LinkedHashMap<String, LocalDate>();
customers.put("Bob", LocalDate.of(1956, 4, 7)); // 7th April 1956 
customers.put("Alice", LocalDate.of(1990, 5, 31)); // 31st May 1990
customers.put("Claire", LocalDate.of(1975, 2, 1)); // 1st February 1975

for (String customer : cutomers.keySet() {
    System.out.println(customer);
}

This gives us:

Bob
Alice
Claire

This is as expected: it's the order in which we inserted the elements into the LinkedHashMap. If you were to iterate over the values instead, you would get the date of birth for Bob first, then Alice second and then Claire.

What's happening is that a call to get() or put() removes the element from its current position and adds it to the tail of the linked list.

Note that a LinkedHashMap is different from its cousin, HashMap. With a HashMap it may seem as if elements are stored randomly – they could be spread across a hash table after all.

Cache

Since invoking get() or put() removes the element and puts it at the end of the list, this is great for a cache. This is known as access order. With a cache, we want to keep the most frequently accessed elements (e.g. from a hard drive or a database) for quick retrieval.

What happens when the capacity of the hash table is reached? An iterator can remove the first few elements from the LinkedHashMap. In other words, the least recently used elements are removed.

There's also the convenient method removeEldestEntry(Map.Entry). If you override this method, you can decide what to do when new entries are added to the map.

What if you want to change the implementation from access order to insertion order? This is one of the constructors, according to the Javadoc page:

LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

If accessOrder is set to true, then access order is used. Otherwise, if accessOrder is set to false, insertion order is used.

(The load factor is how a number between 0.0 and 1.0 (inclusive) that denotes the percentage of how full the hash table is at which point the hash table needs to be rehashed into a larger hash table. The default value is 0.75).

Photo by Silas Köhler on Unsplash