Question about LRU Cache implementation in Java

Question

The standard example for implementing LRU Cache in Java points to the example depot url http://www.exampledepot.com/egs/java.util/coll_Cache.html

How is removeEldestEntry called by default after just adding a new entry in the code snippet below?

final int MAX_ENTRIES = 100;
Map cache = new LinkedHashMap(MAX_ENTRIES+1, .75F, true) {
    // This method is called just after a new entry has been added
    public boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }
};

// Add to cache
Object key = "key";
cache.put(key, object);

// Get object
Object o = cache.get(key);
if (o == null && !cache.containsKey(key)) {
    // Object not in cache. If null is not a possible value in the cache,
    // the call to cache.contains(key) is not needed
}

// If the cache is to be used by multiple threads,
// the cache must be wrapped with code to synchronize the methods
cache = (Map)Collections.synchronizedMap(cache);

Answer 1

Per the Java API for LinkedHashMap:

The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.

Specifically:

This method is invoked by put and putAll after inserting a new entry into the map.

Also note:

This method typically does not modify the map in any way, instead allowing the map to modify itself as directed by its return value. It is permitted for this method to modify the map directly, but if it does so, it must return false (indicating that the map should not attempt any further modification). The effects of returning true after modifying the map from within this method are unspecified.

Answer 2

In this example, the LinkedHashMap is being extended with an "anonymous inner class".

The removeEldestEntry method is overriding the super-class's version, which always returns false (indicating the eldest entry should not be removed). The overriding version returns true if the size of the map exceeds the limit, indicating that the oldest entry should be removed.

Answer 3

The LinkedHashMap class documentation states that it will call the method removeEldestEntry() at appropriate times. In the code above we provide an anonymous "extends" of the LinkedHashMap class which explicitly provides our implementation for that method.