算法詳解
LRU 緩存機制可以通過哈希表輔以雙向鏈表實現(xiàn)，我們用一個哈希表和一個雙向鏈表維護(hù)所有在緩存中的鍵值對。
雙向鏈表按照被使用的順序存儲了這些鍵值對，靠近頭部的鍵值對是最近使用的，而靠近尾部的鍵值對是最久未使用的。
哈希表即為普通的哈希映射（HashMap），通過緩存數(shù)據(jù)的鍵映射到其在雙向鏈表中的位置。
這樣以來，我們首先使用哈希表進(jìn)行定位，找出緩存項在雙向鏈表中的位置，隨后將其移動到雙向鏈表的頭部，即可在 O(1) 的時間內(nèi)完成 get 或者 put 操作。具體的方法如下：
對于 get 操作，首先判斷 key 是否存在：
如果 key 不存在，則返回 ?1；
如果 key 存在，則 key 對應(yīng)的節(jié)點是最近被使用的節(jié)點。通過哈希表定位到該節(jié)點在雙向鏈表中的位置，并將其移動到雙向鏈表的頭部，最后返回該節(jié)點的值。
對于 put 操作，首先判斷 key 是否存在：
如果 key 不存在，使用 key 和 value 創(chuàng)建一個新的節(jié)點，在雙向鏈表的頭部添加該節(jié)點，并將 key 和該節(jié)點添加進(jìn)哈希表中。然后判斷雙向鏈表的節(jié)點數(shù)是否超出容量，如果超出容量，則刪除雙向鏈表的尾部節(jié)點，并刪除哈希表中對應(yīng)的項；
如果 key 存在，則與 get 操作類似，先通過哈希表定位，再將對應(yīng)的節(jié)點的值更新為 value，并將該節(jié)點移到雙向鏈表的頭部。
上述各項操作中，訪問哈希表的時間復(fù)雜度為 O(1)，在雙向鏈表的頭部添加節(jié)點、在雙向鏈表的尾部刪除節(jié)點的復(fù)雜度也為O(1)。而將一個節(jié)點移到雙向鏈表的頭部，可以分成「刪除該節(jié)點」和「在雙向鏈表的頭部添加節(jié)點」兩步操作，都可以在 O(1) 時間內(nèi)完成。
小貼士
在雙向鏈表的實現(xiàn)中，使用一個偽頭部（dummy head）和偽尾部（dummy tail）標(biāo)記界限，這樣在添加節(jié)點和刪除節(jié)點的時候就不需要檢查相鄰的節(jié)點是否存在。
Java源代碼：
```java
public class LRUCache {
? ? class DLinkedNode {
? ? ? ? int key;
? ? ? ? int value;
? ? ? ? DLinkedNode prev;
? ? ? ? DLinkedNode next;
? ? ? ? public DLinkedNode() {}
? ? ? ? public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
? ? }
? ? private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
? ? private int size;
? ? private int capacity;
? ? private DLinkedNode head, tail;
? ? public LRUCache(int capacity) {
? ? ? ? this.size = 0;
? ? ? ? this.capacity = capacity;
? ? ? ? // 使用偽頭部和偽尾部節(jié)點
? ? ? ? head = new DLinkedNode();
? ? ? ? tail = new DLinkedNode();
? ? ? ? head.next = tail;
? ? ? ? tail.prev = head;
? ? }
? ? public int get(int key) {
? ? ? ? DLinkedNode node = cache.get(key);
? ? ? ? if (node == null) {
? ? ? ? ? ? return -1;
? ? ? ? }
? ? ? ? // 如果 key 存在，先通過哈希表定位，再移到頭部
? ? ? ? moveToHead(node);
? ? ? ? return node.value;
? ? }
? ? public void put(int key, int value) {
? ? ? ? DLinkedNode node = cache.get(key);
? ? ? ? if (node == null) {
? ? ? ? ? ? // 如果 key 不存在，創(chuàng)建一個新的節(jié)點
? ? ? ? ? ? DLinkedNode newNode = new DLinkedNode(key, value);
? ? ? ? ? ? // 添加進(jìn)哈希表
? ? ? ? ? ? cache.put(key, newNode);
? ? ? ? ? ? // 添加至雙向鏈表的頭部
? ? ? ? ? ? addToHead(newNode);
? ? ? ? ? ? ++size;
? ? ? ? ? ? if (size > capacity) {
? ? ? ? ? ? ? ? // 如果超出容量，刪除雙向鏈表的尾部節(jié)點
? ? ? ? ? ? ? ? DLinkedNode tail = removeTail();
? ? ? ? ? ? ? ? // 刪除哈希表中對應(yīng)的項
? ? ? ? ? ? ? ? cache.remove(tail.key);
? ? ? ? ? ? ? ? --size;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? else {
? ? ? ? ? ? // 如果 key 存在，先通過哈希表定位，再修改 value，并移到頭部
? ? ? ? ? ? node.value = value;
? ? ? ? ? ? moveToHead(node);
? ? ? ? }
? ? }
? ? private void addToHead(DLinkedNode node) {
? ? ? ? node.prev = head;
? ? ? ? node.next = head.next;
? ? ? ? head.next.prev = node;
? ? ? ? head.next = node;
? ? }
? ? private void removeNode(DLinkedNode node) {
? ? ? ? node.prev.next = node.next;
? ? ? ? node.next.prev = node.prev;
? ? }
? ? private void moveToHead(DLinkedNode node) {
? ? ? ? removeNode(node);
? ? ? ? addToHead(node);
? ? }
? ? private DLinkedNode removeTail() {
? ? ? ? DLinkedNode res = tail.prev;
? ? ? ? removeNode(res);
? ? ? ? return res;
? ? }
}
```
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
