LinkedHashMap trick
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:
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;
}
}
Voila, instant LRU cache.
Hi! My name is Alex Miller and I live in St. Louis. I write code for a living and currently work for 
nice.. probably you know, it is also used for writing shortest way of eliminating duplicates in a list.
like: List nonDuplicatesList = new ArrayList(new LinkedHashSet(listToProcess))
A thing that annoyed me to no end is that there is no way to specify the iteration order. So even if you do a LRUMap with that technique, iterating over its values Entries only gets you the eldest to younger order and not the opposite. So you need to override hashmap anyway to get something with both behaviours.
Fair enough…seems like you could possibly override addEntry and play some tricks but they wouldn’t be very efficient without changing the code enough to maintain a tail pointer.
It seems like a design mistake to me to pass a boolean in that constructor – I would have passed an Enum (in JDK 5+) or at least a short. Passing a boolean locks you into 2 choices forever. This is a case where a boolean is being used as a poor substitute for an enumerated value that happens to have two choices. If they’d done that, the JDK could later go back and add an option for MRU as well.
Pretty cool but man I hate the java APIs – override the class to change its behavior?? Yuck. I much prefer composition to inheritance.
Yep, I completely agree with composition over inheritance. Probably would have been better to take some kind of callback interface rather than force you to subclass.
Make maxCapacity final or else someone could potentially set it to a different value from underneath you.
you can get LRU with PriorityQueue as well.
@BlogReader: Yep, shoulda been final.
@Maris: Yes, PriorityQueue can definitely do LRU (or whatever you want). But it’s not a map or suitable for a cache, so I’m not sure it applies here.
Hi Alex,
commons-collections (since v3.0) also offers a LRU Map implementation: http://commons.apache.org/collections/apidocs/org/apache/commons/collections/map/LRUMap.html
Regards,
José
It makes more sense to inherit rather than use composition (callback) since the method will require access to the internals of the class. Otherwise you would be bound to only using the methods publicly available in your callback method which may not be desirable. Its not a big deal to subclass since you’re not really trying to inherit other behavior.
A suggested change.
return size() >= this.maxCapacity;
should be
return size() > this.maxCapacity;
because removeEldest is called after a new element is inserted. If you do >=, your map will maintain maxCapacity-1 as its size.
This technique is mentioned in the book “Java Generics and Collections”
(I hope this site has legitimate permission to reprint)
http://codeidol.com/java/javagenerics/Maps/Implementing-Map/