java - LinkedHashMap LRU 缓存 - 确定删除了哪些值？

Question

背景信息

您可以使用 LinkedHashMap 创建 LRU 缓存，如图所示 at this link .基本上，您只需:

• 扩展链接 HashMap 。
• 提供容量参数。
• 使用参数初始化父类(super class) (LinkedHashMap)，告诉它它的容量、比例因子(永远不应该使用)，并保持项目的插入/引用顺序。
• 覆盖 removeEldestEntry 以在超出容量时删除最早的条目。

我的问题

这是一个非常标准的 LRU 缓存实现。但是我不知道该怎么做的一件事是当 LinkedHashMap 由于最近没有足够使用而删除条目时如何得到通知。

我知道我可以让 removeEldestEntry 提供某种形式的通知...但是有什么方法可以在将新元素插入(放置)到基础 map 中时立即检索从缓存中删除的元素？或者，有没有办法查询从缓存中删除的最后一项？

Answer 1

您可以通过创造性地使用线程本地存储来让它工作:

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);
        }
    }

}

Demo.

place(K,V) 方法背后的想法是向 removeEldestEntry 发出信号，我们希望通过设置线程局部 来获取最老的条目>report 标志为 true。当 removeEldestEntry 看到这个标志并知道一个条目正在被删除时，它会将最老的条目放在 report 变量中，该变量也是线程本地的。

对 removeEldestEntry 的调用发生在对 put 方法的调用中。在那之后，最老的条目要么是 null，要么位于 report 变量中准备好被收集。

在 removed 上调用 set(null) 对于避免挥之不去的内存泄漏很重要。