Thursday, July 10, 2008
LRU For Dummies
I needed a Least Recently Used data structure for some work I was doing so I went out to see what I could find in the open source world. I have used the LRUMap from Commons Collections before, but I was hoping to find one that makes use of generics. I checked out Google Collections, but they don't have any LRU data structures (yet). Fortunately, I check out the JavaDocs for LinkedHashMap on a hunch and was happy to discover that Sun already implemented an LRU algorithm in LinkedHashMap that can be enabled by setting a constructor parameter. They even provided a protected method that can be overriden in a subclass to create a fixed-size LRU map in fewer than 10 lines of code. The JavaDocs explain it all if you're interested.