Showing posts with label cache. Show all posts
Showing posts with label cache. Show all posts

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.