2.8 如何实现LRU缓存方案

难度系数：★★★★☆　被考察系数：★★★★☆

题目描述：

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

分析与解答：

可以使用两个数据结构来实现一个LRU缓存。如下所示：

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

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

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

实现代码如下：