如何设计最近最新使用的缓存？

Question

如何设计最近最新使用的缓存？

假设您访问了一些项目.您需要设计一个数据结构来保存这些项目.每个项目都与最近访问的时间相关联.

每次访问项目时,请在数据结构中进行检查.如果该项目已在缓存中,请更新其访问时间.否则,将其插入缓存中.高速缓存大小是固定的,如果已满,则删除最旧的项目.

我的解决方案

1. 使用地图<item,visitTime>

2. 初始化:使用f(visitTime)按降序对地图进行排序.O(nlg n)

3. 如果访问了某个项目,请使用O(lg n)在地图中搜索该项目.

4. 如果它已在地图中,则更新时间O(1).对地图O(lg n)进行排序.

5. 如果没有,请将其插入地图然后排序.O(lg n)

6. 如果地图大小>固定大小,则删除最后一个元素O(1).

另一种方案:

1. 使用哈希表<item,visitTime>

2. 将它排序为O(n lgn).

3. 如果访问了某个项目,请使用O(1)在该项目中进行搜索.

4. 如果它已在表中,则更新时间O(1).对表O(n lg n)进行排序.

5. 如果没有,请将其插入表中然后排序.O(n lg n)

6. 如果表大小>固定大小,则删除最后一个元素O(1).

有更好的解决方案吗？上) ？

Answer 1

如果您使用双向链表，您将获得 O(1) 插入（搜索后）、O(1) 删除、O(n) 搜索。

假设您在前面插入新项目：

如果缓存未满，则添加到前面即可（O(1)）。

如果需要更新一个项目，找到它（O(n)），将其从链表中删除（O(1)），然后添加到前面（O(1)）。

如果需要删除最旧的元素来插入新元素，请删除末尾元素（O(1)），然后插入到前面（O(1)）[注意：在这种情况下，您需要先搜索列表才能看到如果该项目尚未在缓存中，则 O(n)]。

链接列表也可以为您提供相同的时间，因为搜索会将您留在最后一个元素。