LRU算法 - LRU Cache

這個是比較經典的LRU（Least recently used，最近最少使用）算法，算法根據資料的曆史通路記錄來進行淘汰資料，其核心思想是“如果資料最近被通路過，那麼将來被通路的幾率也更高”。 一般應用在緩存替換政策中。其中的”使用”包括通路get和更新set。

LRU算法

LRU是Least Recently Used 近期最少使用算法。記憶體管理的一種頁面置換算法，對于在記憶體中但又不用的資料快（記憶體塊）叫做LRU，Oracle會根據那些資料屬于LRU而将其移出記憶體而騰出空間來加載另外的資料，一般用于大資料處理的時候很少使用的資料那麼就直接請求資料庫，如果經常請求的資料就直接在緩存裡面讀取。

最近最久未使用(LRU)的頁面置換算法，是根據頁面調入記憶體後的使用情況進行決策的。由于無法預測各頁面将來的使用情況，隻能利用“最近的過去”作為“最近的将來”的近似，是以，LRU置換算法是選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個通路字段，用來記錄一個頁面自上次被通路以來所經曆的時間t，當須淘汰一個頁面時，選擇現有頁面中其t值最大的，即最近最久未使用的頁面予以淘汰（可以使用這種方法去實作）。

LRU的實作

1) 可利用一個棧來儲存目前使用的各個頁面的頁面号。每當程序通路某頁面時，便将該頁面的頁面号從棧中移出，将它壓入棧頂。是以，棧頂始終是最新被通路頁面的編号，而棧底則是最近最久未使用頁面的頁面号。(由于效率過低在leetCode上逾時，代碼未貼出)

2) 也可以過雙向連結清單和HashMap來實作。

雙向連結清單用于存儲資料結點，并且它是按照結點最近被使用的時間來存儲的。 如果一個結點被通路了， 我們有理由相信它在接下來的一段時間被通路的機率要大于其它結點。于是， 我們把它放到雙向連結清單的頭部。當我們往雙向連結清單裡插入一個結點， 我們也有可能很快就會使用到它，同樣把它插入到頭部。 我們使用這種方式不斷地調整着雙向連結清單，連結清單尾部的結點自然也就是最近一段時間， 最久沒有使用到的結點。那麼，當我們的Cache滿了， 需要替換掉的就是雙向連結清單中最後的那個結點(不是尾結點，頭尾結點不存儲實際内容)。

如下是雙向連結清單示意圖，注意頭尾結點不存儲實際内容：

假如上圖Cache已滿了，我們要替換的就是結點3。

哈希表的作用是什麼呢？如果沒有哈希表，我們要通路某個結點，就需要順序地一個個找， 時間複雜度是O(n)。使用哈希表可以讓我們在O(1)的時間找到想要通路的結點， 或者傳回未找到。

java實作

假定現有一程序所通路的頁面序列為：

4，7，0，7，1，0，1，2，1，2，6

随着程序的通路，棧中頁面号的變化情況如圖所示。在通路頁面6時發生了缺頁，此時頁面4是最近最久未被通路的頁，應将它置換出去。

<a href="http://cdn.acmerblog.com/wp-content/uploads/2014/04/28151727-5c27ca2146414bbe889397fcfc855863.png"></a>

題目的要求是實作下面三個方法：

C++實作

參考：http://hawstein.com/posts/lru-cache-impl.html；http://www.cnblogs.com/LZYY/p/3447785.html