LRU 最近使用算法的实现（版本）

LRU

学习过操作系统课程的人应当了解，缓存系统中存在多种用于淘汰数据的机制，其中最为人熟知的便是 LRU 缓存淘汰策略。当缓存空间即将饱和时，该机制会优先释放那些最近被访问次数最少的数据块。那么，这一算法究竟是如何具体实现的呢？接下来我们将对其进行深入分析。

一、LRU算法运行机制解析

下面我们先来了解 LRU 的具体运作流程：

假定当前缓存容量为 3，并且已经存储了三个数字 1,2,3：

[1,2,3]

此时若访问了 2，则该数字成为最近使用项，并被移动至队列前端：

[1,3,2]

接下来，我们尝试将 4 插入缓存。由于 1 是当前最久未被使用的数据，因此将其替换掉：

[3,2,4]

随后，再次访问 3，它将被调整到最前面：

[2,4,3]

…

通过上述步骤，我们可以大致理解 LRU 所要实现的核心机制是什么。

二、数据结构选型

通过观察可以得知，数据的输入过程与队列的操作方式存在相似之处，因此在选择数据存储的数据结构时，我们决定采用队列的形式，并且在实现队列时选用双向链表作为基础结构。

然而，双向链表在进行查找操作时的时间复杂度为 O(n)，为了将这一复杂度降低至 O(1) 的水平，我们可以将哈希表与之结合使用，从而构建出一种复合型数据结构——**哈