2.8 如何實現LRU緩存方案

【出自MT面試題】

難度系數：★★★★☆

被考察系數：★★★★☆

題目描述

LRU是Least Recently Used 的縮寫，它的意思是“最近最少使用”。LRU緩存就是使用這種原理實現，簡單地說，就是緩存一定量的數據，當超過設定的閾值時就把一些過期的數據刪除掉。常用于頁面置換算法，是為虛擬頁式存儲管理中常用的算法。如何實現LRU緩存方案？

分析與解答：

可以使用兩個數據結構實現一個LRU緩存。

1）使用雙向鏈表實現的隊列，隊列的最大容量為緩存的大小。在使用的過程中，把最近使用的頁面移動到隊列頭，最近沒有使用的頁面將被放在隊列尾的位置。

2）使用一個哈希表，把頁號作為鍵，把緩存在隊列中的結點的地址作為值。

當引用一個頁面時，所需的頁面在內存中，需要把這個頁對應的結點移動到隊列的前面。如果所需的頁面不在內存中，將它存儲在內存中。簡單地說，就是將一個新結點添加到隊列的前面，并在哈希表中更新相應的結點地址。如果隊列是滿的，那么就從隊列尾部移除一個結點，并將新結點添加到隊列的前面。實現代碼如下：

程序的運行結果為