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

我正在研究LRU高速缓存实现的问题，在该问题中，在高速缓存大小已满之后，弹出最近最少使用的项目，并用新项目替换它。

我想到了两个实现:

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

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

要插入一个新元素，我们可以将当前时间戳和值放在LRUCache中。当高速缓存的大小已满时，我们可以通过找到time_to_key中存在的最小时间戳并将相应的 key 从LRUCache中删除来逐出最近的元素。
插入新项目为O(1)，更新时间戳为O(n)(因为我们需要在time_to_key中搜索与时间戳相对应的k。

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

现在我有以下问题:

这些实现中的哪一种更适合LRUCache。

还有其他方法可以实现LRU缓存。

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

我见过类似的问题，实现了通用的LRU缓存，也见过诸如实现LRU缓存的问题。通用LRU缓存与LRU缓存是否不同？

提前致谢!!!

编辑:

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

最佳答案

如果要使用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时，只要您获得而不是最后一项的条目，LinkedHashMap就会重新排列 map 的顺序。

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

关于java - 实现LRU缓存的最佳方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6398902/