I wrote a compact LRU (Least Recently Used) cache implementation using LinkedHashMap’s “access order” feature. In an LRU cache, the eviction policy is to evict entries which have been accessed the longest time ago. LinkedHashMap maintains a doubly linked list of entries internally which is by default in insertion order but it has a constructor which allows you to specify that the list be maintained in access order. This is perfect for LRU cache since any of the methods such as get and put (and their variants) are considered access methods and will update the list. To take it one step further, it allows you to override a method called removeEldestEntry where you can specify when you want the eldest entry to be evicted. The logic you can put in that method can be arbitrary, but for LRU cache we will simply check if the size is greater than the specified cache capacity.
