java - 实现 LRU 缓存的最佳方法

Question

我正在研究 LRU 缓存实现的这个问题，在缓存的大小已满后，弹出最近最少使用的项目并将其替换为新项目。

我想到了两种实现方式:

1)。创建两个看起来像这样的 map

std::map<timestamp, k> time_to_key
std::map<key, std::pair<timestamp, V>> LRUCache

要插入一个新元素，我们可以将当前时间戳和值放入LRUCache。而当缓存的大小已满时，我们可以通过找到 time_to_key 中存在的最小时间戳并从 中删除相应的键来驱逐最近的元素LRUCache。插入一个新item是O(1)，更新时间戳是O(n)(因为我们需要在time_to_中查找时间戳对应的k键。

2)。有一个链表，其中最近最少使用的缓存出现在头部，新项目添加在尾部。当一个已经存在于缓存中的项目到达时，与该项目的键对应的节点被移动到列表的尾部。插入一个新元素是O(1)，更新时间戳也是O(n)(因为我们需要移动到列表的尾部)，删除一个元素是O(1)。

现在我有以下问题:

1. 这些实现中哪一个更适合 LRUCache。

2. 有没有其他方式来实现LRU Cache。

3. 在Java中，我应该使用HashMap来实现LRUCache

4. 我看到了诸如实现通用 LRU 缓存之类的问题，也看到了诸如实现 LRU 缓存之类的问题。通用 LRU 缓存与 LRU 缓存不同吗？

提前致谢!!!

编辑:

在 Java 中实现 LRUCache 的另一种方法(最简单的方法)是使用 LinkedHashMap 并覆盖 boolean removeEldestEntry(Map.entry eldest) 函数。

Answer 1

如果你想要一个 LRU 缓存，Java 中最简单的就是 LinkedHashMap。默认行为是 FIFO，但是您可以将其更改为“访问顺序”，使其成为 LRU 缓存。

public static <K,V> Map<K,V> lruCache(final int maxSize) {
    return new LinkedHashMap<K, V>(maxSize*4/3, 0.75f, true) {
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > maxSize;
        }
    };
}

注意:我使用的是 constructor这会将集合从最新的优先更改为最近使用的优先。

来自 Javadoc

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder)
Constructs an empty LinkedHashMap instance with the specified initial capacity, load factor and ordering mode.
Parameters:
initialCapacity - the initial capacity
loadFactor - the load factor
accessOrder - the ordering mode - true for access-order, false for insertion-order

当 accessOrder 为 true 时，只要您 get() 一个不是最后一个条目，LinkedHashMap 就会重新排列映射的顺序。

这样最旧的条目是最近使用最少的。