運用你所掌握的數(shù)據(jù)結(jié)構(gòu)构舟，設(shè)計和實現(xiàn)一個 LRU (最近最少使用) 緩存機制宇整。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 妙同。
獲取數(shù)據(jù) get(key) - 如果密鑰 (key) 存在于緩存中，則獲取密鑰的值（總是正數(shù)）场靴，否則返回 -1队丝。
寫入數(shù)據(jù) put(key, value) - 如果密鑰不存在玩祟，則寫入其數(shù)據(jù)值腹缩。當(dāng)緩存容量達(dá)到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)值空扎，從而為新的數(shù)據(jù)值留出空間藏鹊。
進(jìn)階:
你是否可以在 O(1) 時間復(fù)雜度內(nèi)完成這兩種操作？
LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );
cache.put(1, 1);
//cache [(1,1)]
cache.put(2, 2);
//cache[(2,2),(1,1)]
cache.get(1); // 返回 1
//cache[(1,1),(2,2)]
cache.put(3, 3); // 該操作會使得密鑰 2 作廢
//cache[(3,3),(1,1)]
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 該操作會使得密鑰 1 作廢
//cache [(4,4),(3,3)]
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
// cache[(3,3),(4,4)]
cache.get(4); // 返回 4
//cache[(4,4),(3,3)]
分析
LRU算法實際上是：最近操作的數(shù)據(jù)位于數(shù)據(jù)結(jié)構(gòu)的隊首转锈。并且put和get操作的時間復(fù)雜度均是O(1)盘寡。
實際上這個Cache的特點：查找快、刪除快撮慨、插入快竿痰、有順序。
- HashMap除了無序砌溺，其他3個特點均滿足影涉；
- 鏈表是有序的，并且刪除和插入的時間復(fù)雜度均為O(1)规伐。雖然HashMap可以快速定位到Node節(jié)點常潮，但單鏈表中只保存了一個指針，無法進(jìn)行刪除操作楷力。所以使用雙向鏈表，即使定位到一個節(jié)點孵户，也可以確定其前節(jié)點和后節(jié)點萧朝。
故最終的存儲結(jié)構(gòu)是哈希表與雙向鏈表的結(jié)合。
- 哈希表定位Node節(jié)點：解決鏈表的查找緩慢問題夏哭；
- 雙向鏈表存儲Value：解決哈希表的無序問題检柬；
哈希表存儲key，用于定位到鏈表匯總的value。那么Node中為什么還要存儲key呢何址？
因為Node自我刪除的時候里逆，要去Map中刪除對應(yīng)的key。但若是Node只保存Value用爪，沒有保存key原押。找不到對應(yīng)的Map數(shù)據(jù)。即Node節(jié)點也需要映射map偎血。
代碼實現(xiàn)
1. 創(chuàng)建Node節(jié)點诸衔。
public class LRUCache {
static class Node {
//鏈表數(shù)據(jù)域為key和val
private int key, val;
private Node next, prev;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
}
2. 創(chuàng)建雙向鏈表，并實現(xiàn)其中的API方法
public class LRUCache {
static class DoubleList {
private Node head, tail; //頭節(jié)點颇玷，尾節(jié)點
private int size;
//構(gòu)建雙向鏈表
public DoubleList() {
this.head = new Node(0, 0);
this.tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
this.size = 0;
}
//鏈表頭部插入數(shù)據(jù)
public void addFirst(Node node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
size++;
}
//刪除鏈表中的node節(jié)點
public void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
size--;
}
//刪除鏈表的最后一個節(jié)點，并返回該節(jié)點
public Node removeLast() {
if (tail.prev == head) {
return null;
}
//保存尾指針
Node lastNode = tail.prev;
tail.prev.prev.next = tail;
tail.prev = tail.prev.prev;
size--;
return lastNode;
}
//返回鏈表長度
public int size() {
return size;
}
}
}
3. 實現(xiàn)LRU緩存
public class LRUCache {
//記錄 節(jié)點的位置
HashMap<Integer, Node> map = new HashMap<>(16);
//真正的緩存
DoubleList cache = new DoubleList();
//最大容量
private int cap;
public LRUCache(int capacity) {
cap = capacity;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
int val = map.get(key).val;
//使用put方法將數(shù)據(jù)提前，先刪后頭插
put(key, val);
return val;
}
public void put(int key, int value) {
//先new出新節(jié)點
Node node = new Node(key, value);
//若包含節(jié)點持隧，則刪除節(jié)點后倔叼，插入到頭部
if (map.containsKey(key)) {
//刪除Node節(jié)點
cache.remove(map.get(key));
cache.addFirst(node);
//更新map中的值
map.put(key, node);
} else {
//若沒有包含頭節(jié)點
if (cap == cache.size()) {
//刪除鏈表的最后一個元素
Node last = cache.removeLast();
//注：若Node中值存儲value，那么此處不能映射到map空郊。
map.remove(last.key);
}
//插入鏈表頭部
cache.addFirst(node);
map.put(key, node);
}
}
}
實際上在Java中LinkedHashMap便是使用哈希表+雙向鏈表實現(xiàn)的LRU思想份招。
