LinkedHashMap LRU Cache - Determines what values are removed?
Background information
You can make LRU cache with LinkedHashMap as shown in this link . Basically, you just:
- Extending a linked hash map.
- Specify the capacity parameter.
- Initialize superclass (LinkedHashMap) with parameters to tell it its capacity, scaling factor (which should never be used), and keep elements in input / reference order.
- Override removeEldestEntry to remove the oldest entry when there is a bandwidth problem.
My question
This is a fairly standard LRU cache implementation. But one thing I can't figure out how to do this is to know when the LinkedHashMap is deleting a record due to not being used recently enough.
I know I can do removeEldestEntry to provide some form of notification ... but is there a way to retrieve an item that is removed from the cache when a new one is inserted (pushed) into the basemap? Also, is there a way to query for the last item that was removed from the cache?
source to share
is there a way to fetch an item that is removed from the cache when a new one is inserted (pushed) into the basemap?
removeEldestEntry
is notified of the entry to be deleted. You can add a listener called by this method if you want to make it dynamically configurable.
From Javadoc
protected boolean removeEldestEntry (Map.Entry senior)
eldest is the least recently inserted card entry, or if it is an ordered card, the least available entry. This is the entry to be removed and this method will return true. If the map was empty before the call to put or putAll that invoked this call, this will be the entry that was just inserted; in other words, if the card contains one entry, the oldest entry is also the newest.
...
Is there a way to query for the last item that was removed from the cache?
The last item removed has been removed, however you could subclass this entry into a field that you can retrieve later.
source to share
You can get it to work with some creative use of local thread storage:
class LRUCacheLHM<K,V> extends LinkedHashMap<K,V> {
private int capacity;
public LRUCacheLHM(int capacity) {
//1 extra element as add happens before remove (101), and load factor big
//enough to avoid triggering resize. True = keep in access order.
super(capacity + 1, 1.1f, true);
this.capacity = capacity;
}
private ThreadLocal<Map.Entry<K,V>> removed = new ThreadLocal<Map.Entry<K,V>>();
private ThreadLocal<Boolean> report = new ThreadLocal<Boolean>();
{
report.set(false);
}
@Override
public boolean removeEldestEntry(Map.Entry<K,V> eldest) {
boolean res = size() > capacity;
if (res && report.get()) {
removed.set(eldest);
}
return res;
}
public Map.Entry<K,V> place(K k, V v) {
report.set(true);
put(k, v);
try {
return removed.get();
} finally {
removed.set(null);
report.set(false);
}
}
}
The idea behind the method place(K,V)
is to signal removeEldestEntry
that we would like to receive the older record by setting a flag report
at the stream level true
. When it removeEldestEntry
sees this flag and knows that an item is being removed, it puts the highest entry in a variable report
, which is also a thread local.
The call removeEldestEntry
happens in a method call put
. After that, the older record is either null
or is inside a variable report
ready for collection.
The set(null)
on call is removed
important to avoid lingering memory leaks.
source to share