实现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) (因为我们需要搜索与time_to_key中时间戳对应的k)。

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

现在我有以下问题：

1. 这些实现中哪一个对LRUCache更好。
2. 有没有其他方法来实现LRU缓存。
3. 在Java中，我应该使用HashMap实现LRUCache吗？
4. 我看到了一些问题，比如，实现一般的LRU缓存，以及类似于实现LRU缓存的问题。一般的LRU缓存与LRU缓存不同吗？

提前谢谢！

编辑：

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

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是true时，每当您得到一个不是最后一个条目的条目时，LinkedHashMap就会重新排列映射的顺序。

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

Answer 2

通常，LRU缓存被表示为LIFO结构--一个元素队列。如果标准提供的对象不允许您从中间移除对象，例如，将它们放在顶部，那么您可能不得不自己滚动。

Answer 3

考虑到缓存允许并发访问，LRU缓存的良好设计问题归结为：

( a)在更新两种结构(缓存结构和LRU结构)时，能否避免使用互斥。

( b)缓存的读取(获取)操作是否需要互斥体？

更详细的内容:比如说，如果我们使用java.util.concurrent.ConcurrentLinkedQueue(LRU (缓存结构)和java.util.concurrent.ConcuurentHashMap(缓存结构)来实现这一点。

(A)在编辑操作中锁定这两个结构- addEntry()、removeEntry()、evictEntries()等。

( b)上述操作可能会作为慢速写入操作传递，但问题是即使对于读(get)操作，我们也需要对这两个结构应用锁。因为，get将意味着将条目放在LRU策略的队列前面。(假设从队列的末尾删除条目)。

使用高效的并发结构，如ConcurrentHashMap和等待空闲的ConcurrentLinkedQueue，然后对它们设置一个锁，就会失去它的全部用途。

我用同样的方法实现了LRU缓存，但是，LRU结构化的LRU被异步更新，消除了在访问这些结构时使用任何互斥的需要。LRU是缓存的内部细节，可以以任何方式实现，而不会影响缓存的用户。

后来，我还读到了关于ConcurrentLinkedHashMap的文章。

https://code.google.com/p/concurrentlinkedhashmap/

并发现它也在试图做同样的事情。没有使用这种结构，但可能是一个很好的匹配。