Sunday, May 16, 2010

Creating a bounded LRU Cache with LinkedHashMap

I recently had cause to implement a fixed size cache in some code was writing. I wanted a straightforward map, but with a fixed size and the ability to evict on a least-recently-used (LRU) basis. I thought quickly to get something up and running that I would use a LinkedHashMap and then have my get and put methods use the ordering to implement the LRU policy.

Well it turns out that LinkedHashMap already has this support built-in if you know what you're doing. There are two parts of this jigsaw:

  1. Override the protected removeEldestEntry method which returns a boolean if the eldest entry should be removed. This method is called for every put with the element that
    is eldest according the LRU policy.
  2. Call the LinkedHashMap(int capacity, float loadFactor, boolean accessOrder) constructor. Specifying true for accessOrder means that the order of the elements will be sorted in the order they were last accessed (from least recently used to most recently used).
Putting this together yields:
public class BoundedLruCache<KEY, TYPE> extends LinkedHashMap<KEY, TYPE> {

    private static  final int DEFAULT_INITIAL_CAPACITY = 100;

    private static final float DEFAULT_LOAD_FACTOR = 0.75;

    private final int bound;

    public BoundedLruCache(final int bound) {
        super(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, true);
        this.bound = bound;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<KEY, TYPE> eldest) {
        return size() > bound;
    }
}
Which is remarkably compact. Once again the JRE library proves to have some nice bits and pieces if you know where to look.

4 comments:

Adam Jaskiewicz said...

We had to do something very similar several months ago, but ours had to implement a pre-existing cache interface. What we did is slightly different: we wrote our cache as a facade (implementing our cache interface) around a Map. The Map is instantiated as an anonymous inner class instance of LinkedHashMap that overrides removeEldestEntry.

merereflections said...

I think override method should be

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

Dean Povey said...

@merereflections: You are correct, I fixed up my example. Many thanks.

Dean Povey said...

@Adam: That's more or less the way I ended up using this code as well, ie. with a class that wraps the cache instance. Thanks for your comment.