You’ve heard of LinkedHashMap, right? Nice little addition to the collections API in JDK 1.4. Basically a normal HashMap except it also maintains a doubly-linked list tracking insertion order so any iterators you get on the Map walk the Map entries in a predictable (and possibly useful) manner.

It’s not something I use often but occasionally it’s just the right thing. What I didn’t realize until today was that LinkedHashMap has a special constructor that lets you specify that the list is maintained in access-order rather than insertion order. Any call to get(), put(), or putAll() is considered an access. An iterator from the map then walks from least-recently accessed to most-recently accessed.

Which makes it perfect for building a quick and dirty LRU cache. There’s a handy protected method called removeEldestEntry. This method is called when items are being added to the map. The default implementation just returns false. But you can subclass LinkedHashMap and override this method to check whether a maximum size has been reached, then just return true. The LinkedHashMap will find the oldest entry via the linked list and boot it before adding a new entry.

Something like this:

[source:java]

public class MyLRUMap<K,V> extends LinkedHashMap<K,V> {

private int maxCapacity;

public MyLRUMap(int initialCapacity, float loadFactor, int maxCapacity) {

super(initialCapacity, loadFactor, true);

this.maxCapacity = maxCapacity;

}

@Override

protected boolean removeEldestEntry(Entry<K,V> eldest) {

return size() >= this.maxCapacity;

}

}

[/source]

Voila, instant LRU cache.