前言
緩存是一種提高數(shù)據(jù)讀取性能的技術(shù)佑笋，在計(jì)算機(jī)中cpu和主內(nèi)存之間讀取數(shù)據(jù)存在差異，CPU和主內(nèi)存之間有CPU緩存印颤，而且在內(nèi)存和硬盤有內(nèi)存緩存请祖。當(dāng)主存容量遠(yuǎn)大于CPU緩存订歪，或磁盤容量遠(yuǎn)大于主存時(shí)，哪些數(shù)據(jù)應(yīng)該被應(yīng)該被清理肆捕，哪些數(shù)據(jù)應(yīng)該被保留刷晋，這就需要緩存淘汰策略來決定。常見的策略有三種：先進(jìn)先出策略FIFO(First In,First Out)、最少使用策略LFU(Least Frequently Used)眼虱、最近最少使用策略LRU(Least Recently Used)喻奥。
LRU描述
設(shè)計(jì)和實(shí)現(xiàn)一個(gè) LRU (最近最少使用) 緩存機(jī)制 。
實(shí)現(xiàn) LRUCache 類：
- LRUCache(int capacity) 以正整數(shù)作為容量 capacity 初始化 LRU 緩存
- int get(int key) 如果關(guān)鍵字 key 存在于緩存中捏悬，則返回關(guān)鍵字的值撞蚕，否則返回 -1 。
- void put(int key, int value) 如果關(guān)鍵字已經(jīng)存在过牙，則變更其數(shù)據(jù)值甥厦；如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字-值」寇钉。當(dāng)緩存容量達(dá)到上限時(shí)刀疙，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間扫倡。
解題思路 哈希表 + 雙向鏈表
- 針對(duì)LRU的特點(diǎn)谦秧，選擇使用雙鏈表實(shí)現(xiàn)。
- 使用 gut 方法獲取數(shù)據(jù)撵溃，如果有數(shù)據(jù)疚鲤，把返回?cái)?shù)據(jù)，并且把數(shù)據(jù)放在鏈表頭部缘挑。
- 使用 put 方法存放數(shù)據(jù)集歇，如果數(shù)據(jù)存在，直接覆蓋新值卖哎；如果數(shù)據(jù)不存在鬼悠，添加新值。新值都放在鏈表頭部亏娜。此外，還需要判斷緩存有沒有超出容量 capacity蹬挺，如果有超出维贺，刪除鏈表的尾結(jié)點(diǎn)。
- 因?yàn)槭菃捂湵戆桶铮看潍@取數(shù)據(jù)溯泣，或者刪除數(shù)據(jù)，都需要遍歷一遍鏈表榕茧，時(shí)間復(fù)雜度是O(n),這里使用hash來記錄每個(gè)數(shù)據(jù)的位置垃沦，將數(shù)據(jù)訪問的時(shí)間復(fù)雜度降到O(1)。
class LRUCache {
class DLinkedNode{
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {}
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private int size;
private int capacity;
private DLinkedNode head;
private DLinkedNode tail;
private Map<Integer,DLinkedNode> cache = new HashMap<>();
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
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;
}
//找到并移動(dòng)到首位
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
//不存在就創(chuàng)建一個(gè)新的節(jié)點(diǎn)
DLinkedNode newNode = new DLinkedNode(key,value);
cache.put(key,newNode);
addToHead(newNode);
size++;
if (size > capacity) {
//超出容量用押，移除最后節(jié)點(diǎn)
DLinkedNode tail = removeTail();
cache.remove(tail.key);
size--;
}
} else {
//key存在肢簿，覆蓋value，并移到頭部
if (node.value != value) {
node.value = value;
}
moveToHead(node);
}
}
private DLinkedNode removeTail() {
DLinkedNode node = tail.prev;
removeNode(node);
return node;
}
private DLinkedNode removeNode(DLinkedNode node) {
node.next.prev = node.prev;
node.prev.next = node.next;
return node;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
}
