寫在前
LRU緩存機(jī)制（Least Recently Used）（看時間）
- 在緩存滿的時候开瞭，刪除緩存里最久未使用的數(shù)據(jù)穆端，然后再放入新元素闹蒜；
- 數(shù)據(jù)的訪問時間很重要，訪問時間距離現(xiàn)在越近沸呐，就越不容易被刪除；
- 就是喜新厭舊悠就，淘汰在緩存里呆的時間最久的元素站叼。在刪除元素的時候，只看「時間」這一個維度朽肥。
LFU緩存機(jī)制（Least Frequently Used）（看訪問次數(shù)）
- 在緩存滿的時候禁筏，刪除緩存里使用次數(shù)最少的元素，然后在緩存中放入新元素衡招；
- 數(shù)據(jù)的訪問次數(shù)很重要篱昔，訪問次數(shù)越多，就越不容易被刪除始腾，即淘汰訪問次數(shù)最少的州刽；
- 核心思想：先考慮訪問次數(shù)，在訪問次數(shù)相同的情況下浪箭，再考慮緩存的時間穗椅。
算法描述
請你為 最不經(jīng)常使用（LFU）緩存算法設(shè)計并實現(xiàn)數(shù)據(jù)結(jié)構(gòu)。
實現(xiàn) LFUCache 類：
- LFUCache(int capacity) - 用數(shù)據(jù)結(jié)構(gòu)的容量 capacity 初始化對象
- int get(int key) - 如果鍵存在于緩存中奶栖，則獲取鍵的值匹表，否則返回 -1门坷。
- void put(int key, int value) - 如果鍵已存在，則變更其值袍镀；如果鍵不存在默蚌，請插入鍵值對。當(dāng)緩存達(dá)到其容量時苇羡，則應(yīng)該在插入新項之前绸吸，使最不經(jīng)常使用的項無效。在此問題中设江，當(dāng)存在平局（即兩個或更多個鍵具有相同使用頻率）時锦茁，應(yīng)該去除 最近最久未使用 的鍵。
注意「項的使用次數(shù)」就是自插入該項以來對其調(diào)用 get 和 put 函數(shù)的次數(shù)之和叉存。使用次數(shù)會在對應(yīng)項被移除后置為 0 蜻势。
為了確定最不常使用的鍵，可以為緩存中的每個鍵維護(hù)一個 使用計數(shù)器 鹉胖。使用計數(shù)最小的鍵是最久未使用的鍵握玛。
當(dāng)一個鍵首次插入到緩存中時，它的使用計數(shù)器被設(shè)置為 1 (由于 put 操作)甫菠。對緩存中的鍵執(zhí)行 get 或 put 操作挠铲，使用計數(shù)器的值將會遞增。
注意哦寂诱，get 和 put 方法必須都是 O(1) 的時間復(fù)雜度拂苹！
示例：
輸入：
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
輸出：
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
解釋：
// cnt(x) = 鍵 x 的使用計數(shù)
// cache=[] 將顯示最后一次使用的順序（最左邊的元素是最近的）
LFUCache lFUCache = new LFUCache(2);
lFUCache.put(1, 1); // cache=[1,_], cnt(1)=1
lFUCache.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lFUCache.get(1); // 返回 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lFUCache.put(3, 3); // 去除鍵 2 ，因為 cnt(2)=1 痰洒，使用計數(shù)最小
// cache=[3,1], cnt(3)=1, cnt(1)=2
lFUCache.get(2); // 返回 -1（未找到）
lFUCache.get(3); // 返回 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lFUCache.put(4, 4); // 去除鍵 1 瓢棒，1 和 3 的 cnt 相同，但 1 最久未使用
// cache=[4,3], cnt(4)=1, cnt(3)=2
lFUCache.get(1); // 返回 -1（未找到）
lFUCache.get(3); // 返回 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lFUCache.get(4); // 返回 4
// cache=[3,4], cnt(4)=2, cnt(3)=3
算法設(shè)計
首先需要維護(hù)一個鏈表丘喻，鏈表的結(jié)構(gòu)如下脯宿。ps：注意是雙端鏈表，圖示有誤泉粉，但意思明確连霉，具體見代碼。
image
注意：
- 首先我們在LRU中定義兩個永久節(jié)點嗡靡，head作為頭節(jié)點跺撼、tail作為尾節(jié)點，就作為了我們鏈表的頭節(jié)點和尾節(jié)點讨彼。我們插入的每一個緩存都是鏈表中的一個Node節(jié)點歉井。
- 因為鏈表頻數(shù)大的靠近head，頻數(shù)小的靠近tail哈误。這種情況實際上是將我們的鏈表按照頻數(shù)劃分成了不同的區(qū)域如下圖
image
算法需要實現(xiàn)的三個操作：
新增節(jié)點：如果新增節(jié)點的頻數(shù)為1哩至，所以我們需要找到當(dāng)前鏈表頻數(shù)為1的部分的第一個節(jié)點（頭結(jié)點）躏嚎，在他前面插入新元素(如果不存在頻數(shù)為1那么就是在tail節(jié)點前插入)
-
修改節(jié)點（刪除+移動）：首先需要將節(jié)點的值進(jìn)行修改這個很簡單，然后就是移動節(jié)點在鏈表中的位置了憨募，假設(shè)節(jié)點的頻數(shù)為 a ，那么節(jié)點首先需要從頻數(shù)為a的區(qū)域中刪除袁辈，這就分為了以下幾種情況：
- 頻數(shù)為a的區(qū)域只有一個節(jié)點菜谣，那么a節(jié)點頻數(shù)修改后，頻數(shù)為a的區(qū)域?qū)?/strong>(注意這個說法晚缩，后面會講實現(xiàn))尾膊，然后將當(dāng)前暫時從鏈表中移除
- 頻數(shù)為a的區(qū)域的頭節(jié)點是當(dāng)前節(jié)點，那么將頻數(shù)為a的節(jié)點的頭節(jié)點改為當(dāng)前節(jié)點的后一個元素即可荞彼，然后將當(dāng)前節(jié)點暫時從鏈表中移除
- 頻數(shù)為a的區(qū)域的頭節(jié)點不是當(dāng)前節(jié)點冈敛，那么直接將當(dāng)前節(jié)點暫時從頻數(shù)為a的區(qū)域刪除即可。
從頻數(shù)為a的區(qū)域刪除后鸣皂，下面一步就是插入到頻數(shù)為a+1的區(qū)域的頭部：
- 頻數(shù)為a+1的區(qū)域不存在抓谴，那么將當(dāng)前節(jié)點插入到上一步更新后的頻數(shù)為a的頭節(jié)點的前面即可
- 頻數(shù)為a+1的區(qū)域存在，直接插入到頻數(shù)為a+1的區(qū)域的頭部即可
刪除節(jié)點：因為tail節(jié)點的前一個就是我們使用次數(shù)最少且最不常使用的緩存寞缝，我們直接刪除tail節(jié)點的前一個節(jié)點即可癌压，單數(shù)刪除的時候需要注意。假設(shè)需要刪除的節(jié)點的頻數(shù)為a荆陆，這個操作相當(dāng)于將指定節(jié)點從頻數(shù)為a的區(qū)域刪除滩届，這和我們修改階段的第一步是類似的。
總結(jié)：上述算法實現(xiàn)的重點被啼，如何獲得頻數(shù)為a的區(qū)域的頭節(jié)點（使用一個Map來維護(hù)鏈表中頻數(shù)為a的區(qū)域的頭節(jié)點）帜消。
代碼實現(xiàn)
- 首先定義雙端鏈表類（包括數(shù)據(jù)和記錄前驅(qū)/后繼節(jié)點的指針）
class DLinkedNode {
int key;
int value;
// 記錄當(dāng)前key被調(diào)用的次數(shù)
int count;
DLinkedNode pre;
DLinkedNode next;
public DLinkedNode() {};
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
this.count = count;
}
}
- 雙向鏈表需要提供一些接口api，便于我們操作浓体，主要就是鏈表的一些操作泡挺，畫圖理解！
private void renewNode(DLinkedNode node) {
int oldCnt = node.count;
int newCnt = oldCnt + 1;
DLinkedNode next = null;
if (cntMap.get(oldCnt) == node) {
//當(dāng)前節(jié)點是oldCnt頻數(shù)的頭結(jié)點（兩種情況：還有其他節(jié)點/只有一個節(jié)點）
// 更新oldCnt頻數(shù)頭結(jié)點的映射
if (node.next.count == node.count) {
cntMap.put(oldCnt, node.next);
} else {
cntMap.remove(oldCnt);
}
// 更新newCnt頻數(shù)頭結(jié)點的映射（不存在直接加入命浴，存在找到對應(yīng)頻數(shù)的頭結(jié)點）
if (cntMap.get(newCnt) == null) {
cntMap.put(newCnt, node);
node.count++;
return;
} else {
removeFromList(node);
next = cntMap.get(newCnt);
}
} else {
// 當(dāng)前節(jié)點不是某個頻數(shù)的頭結(jié)點（我們不需要維護(hù)頻數(shù)頭結(jié)點的映射粘衬，直接找到對應(yīng)頻數(shù)的頭結(jié)點即可）
removeFromList(node);
if (cntMap.get(newCnt) == null) {
next = cntMap.get(oldCnt);
} else {
next = cntMap.get(newCnt);
}
}
node.count++;
cntMap.put(newCnt, node);
// 插入節(jié)點（連接節(jié)點），其中next是頻數(shù)的頭結(jié)點
insertToList(node, next);
}
private void removeFromList(DLinkedNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void insertToList(DLinkedNode node, DLinkedNode next) {
next.pre.next = node;
node.pre = next.pre;
node.next = next;
next.pre = node;
}
// 緩存容量滿了咳促，刪除一個最少且最久沒使用的節(jié)點
private void deleteCache() {
DLinkedNode delNode = tail.pre;
DLinkedNode pre = delNode.pre;
if (cntMap.get(delNode.count) == delNode) {
// 刪除節(jié)點是某個頻數(shù)的頭結(jié)點
cntMap.remove(delNode.count);
}
// 實際刪除的節(jié)點
pre.next = tail;
tail.pre = pre;
cache.remove(delNode.key);
--size;
}
- 確定LRU緩存類的成員變量（鏈表長度稚新、緩存容量和map映射等）和構(gòu)造函數(shù)。注意：定義虛擬頭尾結(jié)點便于在頭部插入元素或者尋找尾部元素跪腹！并在構(gòu)造函數(shù)初始化褂删。
// cnt - node : 增加了頻數(shù)與頭節(jié)點的映射
private Map<Integer, DLinkedNode> cntMap = new HashMap<>();
// key - node
private Map<Integer, DLinkedNode> cache = new HashMap<>();
// 緩存中目前存儲的數(shù)據(jù)量
private int size;
private int capacity;
private DLinkedNode head, tail;
public LFUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.pre = head;
}
-
核心代碼：get和put方法，都是先根據(jù)key獲取這個映射冲茸，根據(jù)映射節(jié)點的情況（有無）進(jìn)行操作屯阀。注意：
- get和put都在使用缅帘，所以數(shù)據(jù)要提前！
- put操作如果改變了雙端鏈表長度（不是僅改變值）难衰，需要先判斷是否達(dá)到最大容量钦无！
public int get(int key) {
DLinkedNode node = cache.get(key);
if (capacity == 0 || node == null) {
return -1;
}
// node節(jié)點的調(diào)用次數(shù)+1,應(yīng)該更新他的位置
renewNode(node);
return node.value;
}
public void put(int key, int value) {
if (capacity == 0) {
return;
}
DLinkedNode node = cache.get(key);
if (node != null) {
node.value = value;
// 將這個節(jié)點的頻數(shù)cnt+1，更新位置
renewNode(node);
} else {
if (cache.size() == capacity) {
deleteCache();
--size;
}
DLinkedNode newNode = new DLinkedNode(key, value, 1);
DLinkedNode next = cntMap.get(1);
if (next == null) {
next = tail;
}
// 將新建的節(jié)點插入到鏈表盖袭，并更新映射
insertToList(newNode, next);
cntMap.put(1, newNode);
cache.put(key, newNode);
++size;
}
}
完整代碼如下：
class LFUCache {
class DLinkedNode {
int key;
int value;
// 記錄當(dāng)前key被調(diào)用的次數(shù)(即node節(jié)點的頻數(shù))
int count;
DLinkedNode pre;
DLinkedNode next;
public DLinkedNode() {};
public DLinkedNode(int key, int value, int count) {
this.key = key;
this.value = value;
this.count = count;
}
}
// cnt - node : 增加了頻數(shù)與頭節(jié)點的映射
private Map<Integer, DLinkedNode> cntMap = new HashMap<>();
// key - node
private Map<Integer, DLinkedNode> cache = new HashMap<>();
// 緩存中目前存儲的數(shù)據(jù)量
private int size;
private int capacity;
private DLinkedNode head, tail;
public LFUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.pre = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (capacity == 0 || node == null) {
return -1;
}
// node節(jié)點的調(diào)用次數(shù)+1,應(yīng)該更新他的位置
renewNode(node);
return node.value;
}
public void put(int key, int value) {
if (capacity == 0) {
return;
}
DLinkedNode node = cache.get(key);
if (node != null) {
node.value = value;
// 將這個節(jié)點的頻數(shù)cnt+1失暂，更新位置
renewNode(node);
} else {
if (cache.size() == capacity) {
deleteCache();
--size;
}
DLinkedNode newNode = new DLinkedNode(key, value, 1);
DLinkedNode next = cntMap.get(1);
if (next == null) {
next = tail;
}
// 將新建的節(jié)點插入到鏈表，并更新映射
insertToList(newNode, next);
cntMap.put(1, newNode);
cache.put(key, newNode);
++size;
}
}
private void renewNode(DLinkedNode node) {
int oldCnt = node.count;
int newCnt = oldCnt + 1;
DLinkedNode next = null;
if (cntMap.get(oldCnt) == node) {
//當(dāng)前節(jié)點是oldCnt頻數(shù)的頭結(jié)點（兩種情況：還有其他節(jié)點/只有一個節(jié)點）
// 更新oldCnt頻數(shù)頭結(jié)點的映射
if (node.next.count == node.count) {
cntMap.put(oldCnt, node.next);
} else {
cntMap.remove(oldCnt);
}
// 更新newCnt頻數(shù)頭結(jié)點的映射（不存在直接加入鳄虱，存在找到對應(yīng)頻數(shù)的頭結(jié)點）
if (cntMap.get(newCnt) == null) {
cntMap.put(newCnt, node);
node.count++;
return;
} else {
removeFromList(node);
next = cntMap.get(newCnt);
}
} else {
// 當(dāng)前節(jié)點不是某個頻數(shù)的頭結(jié)點（我們不需要維護(hù)頻數(shù)頭結(jié)點的映射弟塞，直接找到對應(yīng)頻數(shù)的頭結(jié)點即可）
removeFromList(node);
if (cntMap.get(newCnt) == null) {
next = cntMap.get(oldCnt);
} else {
next = cntMap.get(newCnt);
}
}
node.count++;
cntMap.put(newCnt, node);
// 插入節(jié)點（連接節(jié)點），其中next是頻數(shù)的頭結(jié)點
insertToList(node, next);
}
private void removeFromList(DLinkedNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void insertToList(DLinkedNode node, DLinkedNode next) {
next.pre.next = node;
node.pre = next.pre;
node.next = next;
next.pre = node;
}
// 緩存容量滿了拙已，刪除一個最少且最久沒使用的節(jié)點
private void deleteCache() {
DLinkedNode delNode = tail.pre;
DLinkedNode pre = delNode.pre;
if (cntMap.get(delNode.count) == delNode) {
// 刪除節(jié)點是某個頻數(shù)的頭結(jié)點
cntMap.remove(delNode.count);
}
// 實際刪除的節(jié)點
pre.next = tail;
tail.pre = pre;
cache.remove(delNode.key);
--size;
}
}
總結(jié)與補(bǔ)充
- 上述代碼在LRU基礎(chǔ)上進(jìn)行的决记。主要區(qū)別是：
- 節(jié)點類中引入了count變量，記錄key出現(xiàn)的頻數(shù)
- LFU成員變量中增加了cntMap：key的頻數(shù)與這個頻數(shù)區(qū)間頭結(jié)點的映射
- 注意：同樣的倍踪，我們要注意維護(hù)cntMap映射和節(jié)點的頻數(shù)
作者：_code_x
鏈接：http://www.reibang.com/p/56c732eeb5c7
來源：簡書
著作權(quán)歸作者所有系宫。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處建车。
