Overview
I came across an interesting post on writing up a quick least recently used (LRU) cache in java that I wanted to write about. So we’ll break that post down and explain each line.
Content
By using a HashMap, we can find if an item is the least recently used item in constant time. We can also evict the item in constant time. The best part is that you can easily implement this ADT in java by extending a LinkedHashMap. It even has an eviction policy (removeEldestEntry).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.LinkedHashMap;
import java.util.Map;
public LRUCache<K, V> extends LinkedHashMap<K, V> {
private int cacheSize;
public LRUCache(int cacheSize) {
// initialCapacity, loadFactor, accessOrder
// accessOrder is access order when true, insertion order when false
super(16, 0.75, true);
this.cacheSize = cacheSize;
}
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() >= cacheSize;
}
}