实现LRU缓存的最佳方式

Question

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

我有两个实现:

1).创建两个看起来像这样的地图

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

要插入新元素,我们可以将当前时间戳和值放在LRUCache中.当缓存的大小已满时,我们可以通过查找time _to_ key中存在的最小时间戳并从LRUCache中删除相应的键来逐出最近的元素.插入一个新项是O(1),更新时间戳是O(n)(因为我们需要在时间 _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;
        }
    };
}

注意:我使用的构造函数将集合从最新的第一个更改为最近使用的集合.

来自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是trueLinkedHashMap时,只要你得到一个不是最后一个的条目,就会重新排列地图的顺序.

这样,最旧的条目是最近使用的最小条目.