1.雙向鏈表
package LRU;
import java.util.Iterator;
import java.util.LinkedList;
/**
* LRU: 最近最少使用算法 唇辨。 最近最少使用的元素，在接下來一段時(shí)間內(nèi)，被訪問的概率也很低。
* 即最近被使用的元素，在接下來一段時(shí)間內(nèi)盆赤，被訪問概率較高霉祸。
* <p>
* 用鏈表的結(jié)構(gòu)：
* 鏈表尾表示最近被訪問的元素脐湾，越靠近鏈表頭表示越早之前被訪問的元素
* <p>
* 插入一個(gè)元素乳乌，cache 不滿捧韵，插到鏈表尾，滿汉操，移除cache鏈頭元素再插入鏈表尾
* 訪問一個(gè)元素再来，從鏈表尾部開始遍歷, 訪問到之后，將其從原位置刪除磷瘤，重新加入鏈表尾部
* <p>
* 實(shí)現(xiàn)1：用雙向鏈表實(shí)現(xiàn)芒篷。
* put、get 時(shí)間復(fù)雜度:O(n) 效率低
* <p>
* created by Ethan-Walker on 2019/2/16
*/
public class LRUCache {
LinkedList<Node> cache;
int capacity;
public LRUCache(int capacity) {
this.cache = new LinkedList<>();
this.capacity = capacity;
}
// -1 表示沒找到
public int get(int key) {
Iterator<Node> iterator = cache.descendingIterator();
int result = -1;
while (iterator.hasNext()) {
Node node = iterator.next();
if (node.key == key) {
result = node.val;
iterator.remove();
put(key, result); //添加到鏈表尾部
break;
}
}
return result;
}
public void put(int key, int value) {
//先遍歷查找是否有key 的元素, 有則刪除采缚，重新添加到鏈尾
Iterator<Node> iterator = cache.iterator();
while (iterator.hasNext()) {
Node node = iterator.next();
if (node.key == key) {
iterator.remove();
break;
}
}
if (capacity == cache.size()) {
//緩存已滿针炉，刪除一個(gè) 最近最少訪問的元素（鏈表頭）
cache.removeFirst();
}
cache.add(new Node(key, value));
}
class Node {
int key;
int val;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
}
2. LinkedHashMap
package LRU;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Set;
/**
* LinkedHashMap 實(shí)現(xiàn)
* put /get 操作 O(1)
* 特殊情況：緩存已滿，需要?jiǎng)h除鏈表頭
* created by Ethan-Walker on 2019/2/16
*/
public class LRUCache2 {
LinkedHashMap<Integer, Integer> cache;
int capacity;
public LRUCache2(int capacity) {
cache = new LinkedHashMap<>(capacity);
this.capacity = capacity;
}
public int get(int key) {
if (!cache.containsKey(key)) return -1;
int val = cache.get(key);
cache.remove(key); // 從鏈表中刪除
cache.put(key, val); // 添加到鏈尾
return val;
}
public void put(int key, int value) {
if (cache.containsKey(key)) {
cache.remove(key); // 已經(jīng)存在扳抽，鏈表中刪除
}
if (capacity == cache.size()) {
// cache 已滿,刪除鏈表頭
Set<Integer> keySet = cache.keySet();
Iterator<Integer> iterator = keySet.iterator();
cache.remove(iterator.next());
}
cache.put(key, value);// 添加到鏈尾
}
}
借助 LinkedHashMap 已經(jīng)實(shí)現(xiàn)的 刪除最近最少使用的元素 方法 removeEldestEntry
/**
* LinkedHashMap 本身內(nèi)部有一個(gè)觸發(fā)條件則自動(dòng)執(zhí)行的方法：刪除最老元素（最近最少使用的元素）
* 由于最近最少使用元素是 LinkedHashMap 內(nèi)部處理
* 故我們不再需要維護(hù) 最近訪問元素放在鏈尾篡帕，get 時(shí)直接訪問/ put 時(shí)直接存儲(chǔ)
* created by Ethan-Walker on 2019/2/16
*/
class LRUCache3 {
private Map<Integer, Integer> map;
private final int capacity;
public LRUCache3(int capacity) {
this.capacity = capacity;
map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > capacity; // 容量大于capacity 時(shí)就刪除
}
};
}
public int get(int key) {
return map.getOrDefault(key, -1);
}
public void put(int key, int value) {
map.put(key, value);
}
}
3. 手動(dòng)實(shí)現(xiàn)
- HashMap 中存儲(chǔ)每個(gè)key 對應(yīng)的節(jié)點(diǎn)Node<key，value>贸呢， Node節(jié)點(diǎn)之間再通過 prev镰烧、next 鏈接，實(shí)現(xiàn)有序的雙向鏈表
package LRU;
import java.util.HashMap;
/**
* created by Ethan-Walker on 2019/2/16
*/
public class LRUCacheByself {
// 雙向鏈表節(jié)點(diǎn)結(jié)構(gòu)
private class Node {
public Node pre;
public Node next;
public int key;
public int val;
public Node(int k, int v) {
this.key = k;
this.val = v;
this.pre = null;
this.next = null;
}
}
// 雙向鏈表 頭部是最老的
private class DoublyLinkedList {
public Node head;
public Node tail;
public DoublyLinkedList() {
this.head = null;
this.tail = null;
}
public void moveToTail(Node n) {
// 將節(jié)點(diǎn)移動(dòng)至尾部
if (n == null || n == tail) return;
if (head == n) {
head = n.next;
head.pre = null;
} else {
n.pre.next = n.next;
n.next.pre = n.pre;
}
tail.next = n;
n.pre = tail;
n.next = null;
tail = tail.next;
}
public void addToTail(Node n) {
if (n == null) return;
// 添加新的節(jié)點(diǎn)
if (head == null) {
head = n;
tail = n;
} else {
tail.next = n;
n.pre = tail;
tail = n;
}
}
public Node removeHead() {
// 刪除頭部（最老的）節(jié)點(diǎn)
if (head == null) return null;
Node n = head;
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
head.pre = null;
}
return n;
}
}
private DoublyLinkedList list;
private HashMap<Integer, Node> map;
private int capacity;
public LRUCacheByself(int capacity) {
this.list = new DoublyLinkedList();
this.map = new HashMap<>();
this.capacity = capacity;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
Node n = map.get(key);
list.moveToTail(n);
return n.val;
}
public void put(int key, int value) {
if (!map.containsKey(key)) {
Node n = new Node(key, value);
map.put(key, n);
list.addToTail(n);
if (map.size() > capacity) {
Node rmv = list.removeHead();
map.remove(rmv.key);
}
} else {
Node n = map.get(key);
n.val = value;
list.moveToTail(n);
}
}
}
