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);
Solution
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.
OTHER TIPS
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
andputAll
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.
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.