There is actually an LRU map implemented in Java, though it is sort of hidden in the LinkedHashMap using a special constructor.

http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Linke...