实现MRU缓存替换算法

Question

在软件中实现 LRU 缓存替换算法的通常推荐方法是将缓存项按访问顺序存储在双向链表中。如果我们假设最近使用的元素存储在头部位置，最近最少使用的元素存储在尾部位置，那么当我们填满缓存时，我们会通过逐出尾部元素为新元素腾出空间。

是否有比上述技术更有效的实现 MRU 缓存替换算法的方法，但不是逐出头元素而是逐出尾元素？

Answer 1

任何索引数据结构都可以用来存储元素。与 LRU 不同，MRU 不需要保存历史记录。保留一个 MRU 变量以及最后使用的缓存条目的索引。在命中和替换时更新它。当需要替换元素时，选择MRU元素。