LeetCode題解： LRU Cache 緩存設計
題目描述：
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
設計並實現最近最久未使用的緩存數據結構，支持 get 和 set 操作.
get()-如果 key 存在，返回對應的 value 值，否則返回 -1.
set()-插入 key 對應的 value 到緩存中，如果緩存已滿，將最近最久未使用的元素從緩存中移除。
要實現這個設計，我們先回顧一下大學課堂上的知識。
LRU，即最近最少使用，是操作系統內存管理的一種頁面置換算法，
常見的頁面置換算法，最佳置換算法（OPT，理想置換算法），先進先出置換算法(FIFO)，
最近最久未使用算法(LRU),最少使用算法。
其中，最佳置換算法是一種理想情況下的頁面置換算法，實際上不可能實現。該算法的基本思想是發生缺頁時，有些頁面在內存中，其中有一頁將很快被訪問（也包含緊接著的下一條指令的那頁），而其他頁面則可能要到10、100或者1000條指令後才會被訪問，每個頁面都可以用在該頁面首次被訪問前所要執行的指令數進行標記。最佳頁面置換算法規定標記最大的頁應該被置換。但當缺頁發生時，操作系統無法知道各個頁面下一次是在什麼時候被訪問。這個算法無法實現，但可以用於對可實現算法的性能進行衡量。
另外兩種主要算法，LFU算法-實現緩存，FIFO算法-實現緩存，可以查看這裡。
LRU的實現方法有很多，傳統的LRU實現方法:
1.計數器。最簡單的情況是使每個頁表項對應一個使用時間字段，並給CPU增加一個邏輯時鐘或計數器。每次存儲訪問，該時鐘都加1。每當訪問一個頁面時，時鐘寄存器的內容就被復制到相應頁表項的使用時間字段中。這樣我們就可以始終保留著每個頁面最後訪問的“時間”。在置換頁面時，選擇該時間值最小的頁面。
2.棧。用一個棧保留頁號。每當訪問一個頁面時，就把它從棧中取出放在棧頂上。這樣一來，棧頂總是放有目前使用最多的頁，而棧底放著目前最少使用的頁。由於要從棧的中間移走一項，所以要用具有頭尾指針的雙向鏈連起來。
Java語言可以利用 LinkedHashMap， LinkedHashMap 是有序的哈希表，可以保存記錄的插入順序，並且按使用順序排列。
重寫其中的removeEldestEntry(Map.Entry)方法，就可以實現LRU算法。
我看了一下，在Mysql Jdbc Util和Apache的很多Jar包中，都是使用LinkedHashMap實現LRUCache。
下面的代碼來自mysql-connector-java-5.1.18-bin.jar。
package com.mysql.jdbc.util;
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache extends LinkedHashMap
{
public LRUCache(int maxSize)
{
super(maxSize, 0.75F, true);
maxElements = maxSize;
}
protected boolean removeEldestEntry(java.util.Map.Entry eldest)
{
return size() > maxElements;
}
private static final long serialVersionUID = 1L;
protected int maxElements;
}
不過LeetCode的OJ不支持這樣實現，將上面的代碼修改後提交，提示 Comoile Error .
我們來看一下，LinkedHashMap是通過繼承HashMap，維護一個雙鏈表實現，
當某個Cache位置被命中，通過調整鏈表的指向將該位置調整到頭位置，新加入的內容直接放在鏈表頭，在多次進行Cache操作後，最近使用的Cache就會向鏈表頭部移動，鏈表尾部就是命中次數最少，最久未使用的Cache。空間充滿時，移除尾部的數據就可以了。
題目有幾點需要注意，一個是Key不存在的情況，一個是緩存設計要求Key唯一。
下面使用雙向鏈表(雙鏈表)實現LRU Cache，以下代碼提交AC。
import java.util.HashMap;
/**
* Design and implement a data structure for Least Recently Used (LRU) cache.
* It should support the following operations: get and set.
* get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
* set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity,
* it should invalidate the least recently used item before inserting a new item.
* 近期最少使用算法 設計緩存
*/
public class LRUCache {
private int cacheSize;//緩存容量
private int currentSize;//當前容量
private HashMap<Object, CacheNode> nodes;//緩存容器
private CacheNode head;//鏈表頭
private CacheNode last;//鏈表尾
class CacheNode{
CacheNode prev;//前一節點
CacheNode next;//後一節點
int value;//值
int key;//鍵
CacheNode() {
}
}
//初始化緩存
public LRUCache(int capacity) {
currentSize=0;
cacheSize=capacity;
nodes=new HashMap<Object, CacheNode>(capacity);
}
public Integer get(int key) {
CacheNode node = nodes.get(key);
if (node != null) {
move(node);
return node.value;
} else {
return -1;//error code
}
}
public void set(int key, int value) {
CacheNode node = nodes.get(key);
//重復Key
if(node!=null){
node.value=value;
move(node);
nodes.put(key, node);
}else
{//key未重復，正常流程
node =new CacheNode();
if(currentSize>=cacheSize){
if (last != null){//緩存已滿，進行淘汰
nodes.remove(last.key);}
removeLast();//移除鏈表尾部並後移
}else{
currentSize++;
}
node.key=key;
node.value=value;
move(node);
nodes.put(key, node);
}
}
//移動鏈表節點至頭部
private void move(CacheNode cacheNode){
if(cacheNode==head)
return;
//鏈接前後節點
if(cacheNode.prev!=null)
cacheNode.prev.next=cacheNode.next;
if(cacheNode.next!=null)
cacheNode.next.prev=cacheNode.prev;
//頭尾節點
if (last == cacheNode)
last = cacheNode.prev;
if (head != null) {
cacheNode.next = head;
head.prev = cacheNode;
}
//移動後的鏈表
head = cacheNode;
cacheNode.prev = null;
//節點唯一的情況
if (last == null)
last = head;
}
//移除指定緩存
public void remove(int key){
CacheNode cacheNode = nodes.get(key);
if (cacheNode != null) {
if (cacheNode.prev != null) {
cacheNode.prev.next = cacheNode.next;
}
if (cacheNode.next != null) {
cacheNode.next.prev = cacheNode.prev;
}
if (last == cacheNode)
last = cacheNode.prev;
if (head == cacheNode)
head = cacheNode.next;
}
}
//刪除尾部的結點，即去除最近最久未使用數據
private void removeLast(){
if(last!=null){
if(last.prev!=null){
last.prev.next=null;
}else{//空間大小為1的情況
head = null;
}
last = last.prev;
}
}
public void clear() {
head = null;
last = null;
}
//測試用例
// public static void main(String[] args){
// LRUCache lCache=new LRUCache(2);
// lCache.set(2, 1);
// lCache.set(1, 1);
// lCache.set(2, 3);
// lCache.set(4, 1);
// System.out.println(lCache.get(1));
// System.out.println(lCache.get(2));
//
// }
}
下面是提交中遇到的幾組測試用例：
Input: 2,[get(2),set(2,6),get(1),set(1,5),set(1,2),get(1),get(2)]
Expected: [-1,-1,2,6]
Input: 2,[set(2,1),set(1,1),set(2,3),set(4,1),get(1),get(2)]
Expected: [-1,3]
Input: 1,[get(0)]
Expected: [-1]
