java - 以恒定时间运行的最近最少使用的缓存

Question

我正在尝试创建一个以恒定时间运行并遵循最近最少使用的逐出策略的缓存。它使用 HashMap 来存储数据，并使用链接列表来跟踪数据请求的顺序。头部是最近最少被请求的，尾部是最近被请求的。

一切都在 O(1) 中进行，除非用户请求缓存中已有的项目，并且链接列表必须从列表中删除该项目并将其添加为尾部。我怎样才能实现一个系统，使最近请求的项已经在缓存中，因此链表，尾部的时间复杂度为 O(1)？

Answer 1

这听起来像是双向链表的完美用例。如果您通过元素串联一个双链表而不是单链表，并且有一个虚拟的头和尾对象，则可以通过编写

从列表中拼接出一个元素

elem.next.prev = elem.prev;
elem.prev.next = elem.next;

然后您可以通过编写将元素放在尾部

elem.next = tail;
elem.prev = tail.prev;
tail.prev = elem;
elem.prev.next = elem;

由于这里只有固定数量的指针杂耍，因此运行时间为 O(1)。

这种技术通常在操作系统内核中用于在不同运行队列之间移动线程等对象，因为它速度非常快。