2.8 如何实现LRU缓存方案

【出自MT面试题】

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

题目描述

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

分析与解答：

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

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

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

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

程序的运行结果为