LinkedHashMap's hidden (?) features

Recently I discovered two very nice features of the java.util.LinkedHashMap: accessOrder and removeEldestEntry(Entry). These features combined let you implement simple LRU caches in under two minutes.

accessOrder

The accessOrder flag is set when creating the LinkedHashMap instance using the LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) constructor. This boolean flag specifies how the entries in the map are ordered:

accessOrder=true

The elements are ordered according to their access: When iterating over the map the most recently accessed entry is returned first and the least recently accessed element is returned last. Only the get, put, and putAll methods influence this ordering.

accessOrder=false

The elements are ordered according to their insertion. This is the default if any of the other LinkedHashMap constructors is used. In this ordering read access to the map has no influence on element ordering.

removeEdlestEntry(Entry)

The second feature of interest is the removeEldestEntry(Entry) method. This method is called with the eldest entry whenever an element is added to the map. Eldest means the element which is returned last when iterating over the map. So the notion of eldest is influenced by accessOrder set on the map. The removeEldestElement in its default implementation just returns false to indicate, that nothing should happen. An extension of the LinkedHashMap may overwrite the default implementation to do whatever would be required:

• If the implementation decides to remove the eldest element for any one reason, say a size limitation, it just returns true and the eldest element is removed from the map


• The implementation may also decide to modify the map itself in some way or the other. But in this case, the implementation should return false, otherwise the eldest element will still be removed.

A simple LRU Cache

Taking the two features together, a very simple LRU Cache may be implemented in just a few lines of code:

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int limit;
public LRUCache(int limit) {
  super(16, 0.75f, true);
  this.limit = limit;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
  return size() > limit;
}
}

The mechanism is very easy: The LRUCache(int) constructor initializes the map with the default initial size and load factor and sets the map into accessOrder mode. The removeEldestEntry just checks the current map size (after the addition of a new entry) against the limit and returns true if the limit has been reached.

A real world implementation would of course have to check and handle the limit value on the constructor.


To see a LinkedHashMap based LRU Cache in action, have a look at the BundleResourceCache.BundleResourceMap. This implements a simple entry cache to speed access to OSGi Bundle entries. To not waste memory, the size of the cache is limited.