2.8 如何实现LRU缓存方案

难度系数：★★★★☆

被考查系数：★★★★☆

题目描述

LRU是Least Recently Used的缩写，它的意思是“最近最少使用”，LRU缓存就是使用这种原理实现，简单地说就是缓存一定量的数据，当超过设定的阈值时就把一些过期的数据删除掉。常用于页面置换算法，是为虚拟页式存储管理中常用的算法。下面介绍如何实现LRU缓存方案。

分析与解答：

我们可以使用两个数据结构实现一个LRU缓存。

（1）使用双向链表实现的队列，队列的最大的容量为缓存的大小。在使用的过程中，把最近使用的页面移动到队列首，最近没有使用的页面将被放在队列尾的位置。

（2）使用一个哈希表，把页号作为键，把缓存在队列中的结点的地址作为值。

当引用一个页面时，所需的页面在内存中，我们需要把这个页对应的结点移动到队列的前面。如果所需的页面不在内存中，我们将它存储在内存中。简单地说，就是将一个新结点添加到队列的前面，并在哈希表中更新相应的结点地址。如果队列是满的，那么就从队列尾部移除一个结点，并将新结点添加到队列的前面。实现代码如下：

程序运行结果为：