Programming Puzzle: Implement LRU Cache

Since we were talking about cache recently, it’s worth it to look at implementing our own cache as a programming exercise.

Why?

First, let’s be clear: There is really no need to use your own cache implementation in production. There are a variety of existing caching options (such as EHCache, Guava, and JCache), and you put yourself at risk by re-inventing the wheel.

That said, looking into how caches work is a fun exercise. It can give us a feel for the issues involved and hopefully an intuition for dealing with off-the-shelf caching implementations.

Out With The Old, In With The New

Let’s look at a Least Recently Used (LRU) cache. In this cache, entries that have not been accessed for the longest amount of time are eligable for removal when the cache reaches its maximum size. Java provides an easy base class out of the box to implement this idea: the LinkedHashMap.

Things To Note

  • The constructor specifies the ordering by access mode (get or put). This is important so that the least recently used entries are make eligible for removal.
  • We have an implementation of removeEldestEntry(), this is called when entries are added to see if any entries can be removed.
  • The map by default is not thread safe, so we can add the option of providing this as a synchronized cache.
  • Optionally we can choose the cache to store values of type Optional instead of type V. This reduces the need of the caller to do null handling if the value is not present.

Finally: The Code

public class LRUCache<K, V> extends LinkedHashMap<K, Optional<V>> {

    private static final long serialVersionUID = 1L;
    private final int maxEntries;

    public LRUCache(final int maxEntries) {
        super(16, 0.75f, true);
        this.maxEntries = maxEntries;
    }
    
    @Override
    public Optional<V> get(Object key) {
        return super.get(key);
    }

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

    public Map<K, Optional<V>> asSynchronizedCache() {
        return Collections.synchronizedMap(this);
    }
}
Advertisements

Leave a comment

Filed under Software Engineering

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s