使用雙向鏈表來實現LRU 這篇文章已經用雙向鏈表來實現過LRU算法了，但是基於雙向鏈表的特性，使得該算法的時間復雜度為O(n)，顯然不是最優的算法，那麽有沒有算法，可以達到O(1)，當然是有的，早早的計算機科學家已經想到，並且已經實現了。
在筆者介紹接下來的內容時，還是希望先了解壹下兩篇博文：
壹、 圖解HashMap原理
二、 圖解LinkedHashMap
之前使用雙向鏈表去實現LRU算法時，時間復雜度沒有達到O(1)，主要原因在於遍歷結點時，帶來的時間開銷，那麽換句話說，要實現遍歷結點時，時間復雜度為O(1)，第壹時間想到的應該是hash數組，但是hash算法可能會存在不同的key值，產生相同的hash值，那麽可以將不同key，但是相同hash值的結點，以單鏈表的形式存放。這樣僅僅是實現了存取時間復雜度為O(1)，如何實現數據能夠按訪問順序存放呢？並且增刪的時間復雜度為O(1)，這個可以使用雙向鏈表來實現，所以綜合來講，就是實現散列數組+雙向鏈表來使用LRU，可以達到時間復雜度為O(1)。
邏輯視圖如下:
咋壹看這個圖亂的很，稍微解釋壹下，如果感覺理解上有點困難，可以先去了解壹下之前推薦的兩篇博文，那裏會介紹的更加詳細壹點。
1.最左側其實就是壹個普通的數組，數組的大小必須是2的倍數，這個原因是什麽呢？因為這個數組的存放方式是散列的，意思就是需要key.hashcode & (length -1)才能得出存放位置的方式，hash的好處是可以根據key值，在時間復雜度為O(1)的前提找到對應的存放位置，這也是我們的初衷，說到這裏其實還沒有解釋為什麽壹定要是2的倍數，因為2的倍數-1，這個數的二進制，壹定全是1，比如16-1=15，二進制表示就是1111，&運算符其實就是將值全部化成二進制逐位與，比如10111011 & 1111 = 1011 = 11，但是如果不是2的倍數，比如7-1=6，化成二進制就是0110，由於末位是0，不管什麽二進制值與0110做&運算，壹定是偶數，這樣會導致散列分布不均勻。
2.不同key值，相同hash值，如何存放呢？相同的hash值做與運算壹定能夠得到相同的數組腳標，這些結點，以單鏈表的形式存在，就是圖中數組右側的單鏈表。
3.如何實現按訪問順序？上圖除去數組和掛在數組右側的單鏈表，還有綠色和黃色的單向箭頭，在右上角還有壹個雙向鏈表的頭指針。其實這些箭頭就是維護不同結點的訪問順序，即雙向鏈表。
總上所述，這種數據結構定義的結構體如下：
class Node{
Object key; //存放key值，用於計算存放數組腳標位置
Object value;//存放元素值
int hash;//存放key.hashcode
Node next;//維護單鏈表順序
Node before;//維護雙向鏈表順序
Node after;
}
筆者用java實現如下，感興趣可以用自己喜歡的語言去實現壹遍，加深理解：
其實以上實現底層原理就是LinkedHashMap的實現原理，只不過筆者做了壹些簡化，去掉了繁瑣的繼承，擴容等，突出了算法核心，如果讀者感興趣也可以去研究壹下LinkedHashMap的源碼。
使用LinkedHashMap來實現LRU算法：
看起來是不是簡單了很多，因為LinkedHashMap底層已經封裝好了，我們直接調用就好，但是作為壹個想要變優秀的碼農，壹定要知其然知其所以然。
使用散列+雙向鏈表的方式是如何實現O(1)復雜度的？在實現LRU算法過程中，無非兩種操作，查找和修改，使用散列數組實現查找時間復雜度為O(1)，使用雙向鏈表實現修改復雜度為O(1)，並且雙向鏈表還可以維護訪問順序，所以使用這種方式，可以達到O(1)。