相关疑难解决方法(0)

我正在研究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)函数.