Monday, December 4, 2006

LinkedHashMap to implement LRU caches

I must be living under a rock to have not noticed this before. The LinkedHashMap has a 3 argument constructor. The last argument, if true, orders the map according to the access order. It also defines a protected removeEldestEntry() method which returns false by default. One can override this method to return true in certain situations, in which case the map will remove its eldest entry.

The implementation of an LRUMap will look something like this:

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

int maxLimit;

public LRUMap(int maxLimit) {
super(maxLimit * 10/7 + 1, 0.7f, true);
this.maxLimit = maxLimit;
}

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

}

The removeEldestEntry() method is invoked by the put*() methods. With the above implementation, if the size of the map exceeds the max limit, the eldest entry is removed.

Short and sweet. Albeit some 2 years too late for my unenlightened self.