Implementing a Least Recently Used Cache in Java – Slick
I have to admit that I'm not impressed by Java a lot. It's just the level of familiarity I have with the language. It's just not that often that something really surprises me. So when it happens, it really blows me away. Today is one of those days.
I was trying to implement a Least Recently Used (LRU) Cache, and a co-worker said it would be easy. I doubted it, it's not like it's that easy to make one. But he Googled a few places, and when you base it on the Java LinkedHashMap, it really is easy:
package one.bkit.util; /** * Java System-level Imports */ import java.util.*; import java.util.Map.*; /** * Superclass Imports */ /** * Class Imports */ /** * This class is a simple implementation a Map where only the last * recently used entries are going to stay in the map. You can use * the default size of 100, or you can give it a size. In either case, * every <tt>get()</tt> and <tt>put()</tt> are put through the test * the 'most recently used' filter. If the next <tt>put()</tt> pushes * one out of the map, then it wasn't in the most recently used. */ public class BKLRUCache<K, V> extends LinkedHashMap<K, V> { /** * This is the size of the cache. No more elements will be held * in this map than this. After this, the oldest goes to make room * for the newest. */ private int _maxEntries = 100; // this is the serial version tag for this class private static final long serialVersionUID = 20091014; /** * ---------------------------------------------------------- * Constructors * ---------------------------------------------------------- */ /** * The default constructor assumes a default maximum size of 100 * elements such that <b>only</b> the most recently used 100 entries * will be maintained in the map. After that, the oldest is discarded * to make room for the newer entries. */ public BKLRUCache() { this(100); } /** * The general form of the constructor takes the maximum size of the * LRU cache, and uses that as opposed to any default. */ public BKLRUCache(int maxEntries) { // fix the size, keep things flat for speed, and use access order super(maxEntries + 1, 1, true); _maxEntries = maxEntries; } /** * This version of the constructor takes a map and populates this * map with up to 100 entries - actually, it'll hold the <b>last</b> * 100 entries of the iterator on the argument. It's doing the * <tt>putAll()</tt> on the argument, and the way this works, only * the last 100 are saved. */ public BKLRUCache(Map<? extends K, ? extends V> m) { this(m, 100); } /** * This version of the constructor takes a map and populates this * map with up to maxEntries entries - actually, it'll hold the * <b>last</b> entries of the iterator on the argument. It's doing * the <tt>putAll()</tt> on the argument, and the way this works, * only the last 'n' are saved. */ public BKLRUCache(Map<? extends K, ? extends V> m, int maxEntries) { this(maxEntries); putAll(m); } /** * The magic happens here as the Java LinkedHashMap has a method * that we can intercept and tell it to keep (or not) the oldest * entry in the map. This is where we look at the size and then * see if it's a keeper or not. Simple. */ @Override protected boolean removeEldestEntry(Entry<K, V> eldest) { return (size() > _maxEntries); } }
This is the kind of code I love to see: simple... elegent... compact. It does something very useful and it does it without a lot of grief. Amazing.
Days like this make me want to do more Java coding and learn more of the newest language additions. It might be nice.