在之前的文章，我們介紹過常用緩存淘汰算法（文末有連結）。常見的緩存淘汰算法有先進先出淘汰算法（FIFO），最近最少使用淘汰算法（LSU），最近最久未使用算法（LRU），MRU（最近最常使用算法）。今天我們來討論其中的一種，也是最常用的LRU算法，看看它是如何實現的。
我們使用例子是谷歌開源的kv存儲LevelDB的經典LRUCache實現。LRUCache一般採用雙鏈進行實現，第一個是一個開散列，第二個是雙向鍊表，我們先簡單介紹下這兩個數據結構。首先是開散列。
開散列（Open Hashing）,如果你是個Java開發，那對此肯定不陌生，也就是HashMap。我們先算出一個Key的Hash值，然後在存到對應的列裡面。如果同一個開散列有兩個key的Hash值一樣，我們稱之為衝突。怎麼解決衝突呢？一般我們使用鍊表解決，相同hash值的key在同一列。這裡，我們不難想到一個經典的java面試題，為什麼java的類的hash函數要設計成儘可能不同的類返回不同的值。如果元素的個數大於散列的列數，我們對散列進行擴大一杯，重新哈希，我們稱之為Rehash。好了，這裡我們不難想到另外一個經典的面試題目，為什麼Java開發中，如果已知key的數量，要在在聲明HashMap的時候就把大小傳進去，相信聰明的你現在已經有了答案。
第二個數據結構是雙向鍊表，在我們還在學習數據結構的年代，我們學習了鍊表，雙向鍊表只是鍊表的一個進化版，擁有兩個指針，一個指向前一個節點，一個指向後一個節點。這種數據結果有什麼特點呢？就是在刪除的P的時候，我們只要把P的前置結點的後置結點置為P的後置結點，把P的後置結點置的前置結點置為P的前置結點，就能夠把一個元素刪除。
兩種數據結構的複雜度如下：
雙向列表，查詢比較慢，但是插入很快，而且非常 容易維護先後使用順序。開散列，查詢很快，插入很快，但是很難維護先後順序，需要給每個元素加上時間戳再去遍歷。我們發現當兩種數據結構巧妙結合起來，用雙向鍊表維護最近未使用，用開散列來查詢，並且在開散列的值上面記錄元素在雙向鍊表中的位置，就能能夠大大的降低複雜度。
每次插入的流程如下：
1.當我們插入一個元素的時候，我們首先去開散列中找到這個元素
2.如果這個元素已經存在，則開散列中的值找到元素所在的雙向鍊表的位置，把它提到最新使用。
3.如果這個元素不存在，那麼開散列中插入這個元素，並且判斷是否要重新擴展。雙向鍊表中插入這個元素，並且判斷是否要淘汰掉最舊元素，如果要，那麼同時在開散列中刪除該元素。
好了，今天的內容我們就講到這裡，如果覺得我講的還不錯，歡迎關注我。