lru（least recently used，最近最少使用）算法根據資料的曆史通路記錄來進行淘汰資料，其核心思想是“如果資料最近被通路過，那麼将來被通路的幾率也更高”。
最常見的實作是使用一個連結清單儲存緩存資料，詳細算法實作如下：
1. 新資料插入到連結清單頭部；
2. 每當緩存命中（即緩存資料被通路），則将資料移到連結清單頭部；
3. 當連結清單滿的時候，将連結清單尾部的資料丢棄。
【命中率】
當存在熱點資料時，lru的效率很好，但偶發性的、周期性的批量操作會導緻lru命中率急劇下降，緩存污染情況比較嚴重。
【複雜度】
實作簡單。
【代價】
命中時需要周遊連結清單，找到命中的資料塊索引，然後需要将資料移到頭部。
lru-k中的k代表最近使用的次數，是以lru可以認為是lru-1。lru-k的主要目的是為了解決lru算法“緩存污染”的問題，其核心思想是将“最近使用過1次”的判斷标準擴充為“最近使用過k次”。
相比lru，lru-k需要多元護一個隊列，用于記錄所有緩存資料被通路的曆史。隻有當資料的通路次數達到k次的時候，才将資料放入緩存。當需要淘汰資料時，lru-k會淘汰第k次通路時間距目前時間最大的資料。詳細實作如下：
1. 資料第一次被通路，加入到通路曆史清單；
2. 如果資料在通路曆史清單裡後沒有達到k次通路，則按照一定規則（fifo，lru）淘汰；
3. 當通路曆史隊列中的資料通路次數達到k次後，将資料索引從曆史隊列删除，将資料移到緩存隊列中，并緩存此資料，緩存隊列重新按照時間排序；
4. 緩存資料隊列中被再次通路後，重新排序；
5. 需要淘汰資料時，淘汰緩存隊列中排在末尾的資料，即：淘汰“倒數第k次通路離現在最久”的資料。
lru-k具有lru的優點，同時能夠避免lru的缺點，實際應用中lru-2是綜合各種因素後最優的選擇，lru-3或者更大的k值命中率會高，但适應性差，需要大量的資料通路才能将曆史通路記錄清除掉。
lru-k降低了“緩存污染”帶來的問題，命中率比lru要高。
lru-k隊列是一個優先級隊列，算法複雜度和代價比較高。
由于lru-k還需要記錄那些被通路過、但還沒有放入緩存的對象，是以記憶體消耗會比lru要多；當資料量很大的時候，記憶體消耗會比較可觀。
lru-k需要基于時間進行排序（可以需要淘汰時再排序，也可以即時排序），cpu消耗比lru要高。
two queues（以下使用2q代替）算法類似于lru-2，不同點在于2q将lru-2算法中的通路曆史隊列（注意這不是緩存資料的）改為一個fifo緩存隊列，即：2q算法有兩個緩存隊列，一個是fifo隊列，一個是lru隊列。
當資料第一次通路時，2q算法将資料緩存在fifo隊列裡面，當資料第二次被通路時，則将資料從fifo隊列移到lru隊列裡面，兩個隊列各自按照自己的方法淘汰資料。詳細實作如下：
1. 新通路的資料插入到fifo隊列；
2. 如果資料在fifo隊列中一直沒有被再次通路，則最終按照fifo規則淘汰；
3. 如果資料在fifo隊列中被再次通路，則将資料移到lru隊列頭部；
4. 如果資料在lru隊列再次被通路，則将資料移到lru隊列頭部；
5. lru隊列淘汰末尾的資料。
注：上圖中fifo隊列比lru隊列短，但并不代表這是算法要求，實際應用中兩者比例沒有硬性規定。
2q算法的命中率要高于lru。
需要兩個隊列，但兩個隊列本身都比較簡單。
fifo和lru的代價之和。
2q算法和lru-2算法命中率類似，記憶體消耗也比較接近，但對于最後緩存的資料來說，2q會減少一次從原始存儲讀取資料或者計算資料的操作。
mq算法根據通路頻率将資料劃分為多個隊列，不同的隊列具有不同的通路優先級，其核心思想是：優先緩存通路次數多的資料。
mq算法将緩存劃分為多個lru隊列，每個隊列對應不同的通路優先級。通路優先級是根據通路次數計算出來的，例如
詳細的算法結構圖如下，q0，q1....qk代表不同的優先級隊列，q-history代表從緩存中淘汰資料，但記錄了資料的索引和引用次數的隊列：
如上圖，算法較長的描述如下：
1. 新插入的資料放入q0；
2. 每個隊列按照lru管理資料；
3. 當資料的通路次數達到一定次數，需要提升優先級時，将資料從目前隊列删除，加入到高一級隊列的頭部；
4. 為了防止高優先級資料永遠不被淘汰，當資料在指定的時間裡通路沒有被通路時，需要降低優先級，将資料從目前隊列删除，加入到低一級的隊列頭部；
5. 需要淘汰資料時，從最低一級隊列開始按照lru淘汰；每個隊列淘汰資料時，将資料從緩存中删除，将資料索引加入q-history頭部；
6. 如果資料在q-history中被重新通路，則重新計算其優先級，移到目标隊列的頭部；
7. q-history按照lru淘汰資料的索引。
mq降低了“緩存污染”帶來的問題，命中率比lru要高。
mq需要維護多個隊列，且需要維護每個資料的通路時間，複雜度比lru高。
mq需要記錄每個資料的通路時間，需要定時掃描所有隊列，代價比lru要高。
注：雖然mq的隊列看起來數量比較多，但由于所有隊列之和受限于緩存容量的大小，是以這裡多個隊列長度之和和一個lru隊列是一樣的，是以隊列掃描性能也相近。
由于不同的通路模型導緻命中率變化較大，此處對比僅基于理論定性分析，不做定量分析。
對比點
對比
命中率
lru-2 > mq(2) > 2q > lru
複雜度
代價
lru-2 > mq(2) > 2q > lru
實際應用中需要根據業務的需求和對資料的通路情況進行選擇，并不是命中率越高越好。例如：雖然lru看起來命中率會低一些，且存在”緩存污染“的問題，但由于其簡單和代價小，實際應用中反而應用更多。
java中最簡單的lru算法實作，就是利用jdk的linkedhashmap，覆寫其中的removeeldestentry(map.entry)方法即可
如果你去看linkedhashmap的源碼可知，lru算法是通過雙向連結清單來實作，當某個位置被命中，通過調整連結清單的指向将該位置調整到頭位置，新加入的内容直接放在連結清單頭，如此一來，最近被命中的内容就向連結清單頭移動，需要替換時，連結清單最後的位置就是最近最少使用的位置。
基于雙連結清單 的lru實作:
傳統意義的lru算法是為每一個cache對象設定一個計數器，每次cache命中則給計數器+1，而cache用完，需要淘汰舊内容，放置新内容時，就檢視所有的計數器，并将最少使用的内容替換掉。
它的弊端很明顯，如果cache的數量少，問題不會很大， 但是如果cache的空間過大，達到10w或者100w以上，一旦需要淘汰，則需要周遊所有電腦，其性能與資源消耗是巨大的。效率也就非常的慢了。
它的原理： 将cache的所有位置都用雙連表連接配接起來，當一個位置被命中之後，就将通過調整連結清單的指向，将該位置調整到連結清單頭的位置，新加入的cache直接加到連結清單頭中。
這樣，在多次進行cache操作後，最近被命中的，就會被向連結清單頭方向移動，而沒有命中的，而想連結清單後面移動，連結清單尾則表示最近最少使用的cache。
當需要替換内容時候，連結清單的最後位置就是最少被命中的位置，我們隻需要淘汰連結清單最後的部分即可。
上面說了這麼多的理論， 下面用代碼來實作一個lru政策的緩存。
我們用一個對象來表示cache，并實作雙連結清單，
下面給出完整的實作，這個類也被tomcat所使用（ org.apache.tomcat.util.collections.lrucache），但是在tomcat6.x版本中，已經被棄用，使用另外其他的緩存類來替代它。