LRU算法
LRU(Least Recently Used)，即最近最少使用算法。常用于實(shí)現(xiàn)一個(gè)簡(jiǎn)單的緩存功能颤陶，就是把很久未使用的直接移除掉幔托，只保留最近使用的穴亏。
LRU主要功能
LRU主要需要實(shí)現(xiàn)兩個(gè)功能
- 添加緩存(涉及到刪除緩存)
- 獲取緩存
實(shí)現(xiàn)原理
其實(shí)用一個(gè)單鏈表就能實(shí)現(xiàn)簡(jiǎn)單的LRU算法蜂挪，但是鏈表的查找時(shí)間復(fù)雜度比較高了，是O(n)嗓化。其實(shí)用一個(gè)散列表+雙鏈表就可以實(shí)現(xiàn)一個(gè)O(1)復(fù)雜度的LRU算法棠涮。用散列表就可以直接定位某個(gè)緩存，時(shí)間復(fù)雜度O(1)刺覆，但是散列表插入緩存之后严肪，就沒有了順序，所以才需要一個(gè)鏈表來維護(hù)這個(gè)緩存的順序隅津，這樣才能知道哪些緩存一直未使用诬垂，超過緩存最大容量之后需要?jiǎng)h除未使用的緩存。而如果單鏈表刪除某個(gè)緩存的話伦仍，又需要先遍歷這個(gè)元素（時(shí)間復(fù)雜度O(n)）才行结窘。所以這里用雙鏈表，那么就可以通過散列表直接定位到這個(gè)緩存節(jié)點(diǎn)充蓝，然后知道這個(gè)緩存節(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)就可以在O(1)時(shí)間復(fù)雜度內(nèi)刪除這個(gè)緩存了隧枫。
show me your code
package com.program;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
/**
* LRUCache算法：最近最少使用算法
* 核心算法實(shí)現(xiàn)：散列表+雙向鏈表
* 算法核心功能：
* 1.添加緩存(先判斷散列表中是否存在該緩存，如果存在谓苟，則將該緩存移動(dòng)到鏈尾官脓。
* 如果不存在，則先判斷鏈表是否已經(jīng)滿了涝焙，如果滿了則先把頭結(jié)點(diǎn)刪除卑笨，未滿則直接插到鏈尾)
* 2.查找緩存(因?yàn)槭巧⒘斜恚詴r(shí)間復(fù)雜度仑撞，接近O(1))
* 3.刪除緩存
*/
public class LRUCache {
private int cacheSize = 10;
private HashMap<String, Node> map = new HashMap<>();
private Node head;
private Node tail;
public void LRUCache(int cacheSize) {
this.cacheSize = cacheSize;
}
/**
* 添加緩存
* 先判斷是否已有該緩存赤兴，如果有則直接放到鏈尾取出，
* 如果沒有隧哮，則判斷是否已滿桶良，如果滿了，刪除鏈頭數(shù)據(jù)沮翔，否則直接插到鏈尾
*/
public void addCache(String key, String value) {
if (map.containsKey(key)) {
Node node = map.get(key);
if (node.next != null) {
if (node.pre == null) {
head = node.next;
} else {
node.pre.next = node.next;
node.next.pre = node.pre;
}
tail.next = node;
node.pre = tail;
node.next = null;
tail = node;
}
} else {
Node node = new Node(key, value);
if (map.size() == cacheSize) {
Node temp = head;
head = head.next;
map.remove(temp.key);
node.pre = tail;
tail.next = node;
tail = node;
} else {
if (head == null) {
head = node;
tail = node;
} else {
node.pre = tail;
tail.next = node;
tail = node;
}
}
map.put(key, node);
}
}
/**
* 獲取緩存
* 先判斷是否有緩存陨帆，如果有，需要把該緩存移動(dòng)到鏈尾返回
*/
public String getCache(String key) {
if (map.containsKey(key)) {
Node node = map.get(key);
if (node.next == null) {
return node.value;
}
if (node.pre == null) {
head = node.next;
} else {
node.pre.next = node.next;
node.next.pre = node.pre;
}
tail.next = node;
node.pre = tail;
node.next = null;
tail = node;
return node.value;
} else {
return null;
}
}
public void test() {
Iterator<Map.Entry<String, Node>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Node> entry = iterator.next();
System.out.println(entry.getKey() + "--" + entry.getValue().value);
}
}
public void test2() {
Node temp = head;
while (temp != null) {
System.out.println(temp.key);
temp = temp.next;
}
}
public static void main(String[] args) {
LRUCache cache = new LRUCache();
cache.addCache("key0", "value0");
cache.addCache("key1", "value1");
cache.addCache("key2", "value2");
cache.addCache("key3", "value3");
cache.addCache("key4", "value4");
cache.addCache("key5", "value5");
cache.addCache("key6", "value6");
cache.addCache("key7", "value7");
cache.addCache("key8", "value8");
cache.addCache("key9", "value9");
cache.getCache("key9");
cache.test2();
}
class Node {
String key;
String value;
Node pre;
Node next;
public Node(String key, String value) {
this.key = key;
this.value = value;
}
}
}
免責(zé)聲明：代碼未經(jīng)充分測(cè)試采蚀，如果發(fā)現(xiàn)問題還請(qǐng)不吝賜教疲牵，謝謝。
