LRU快取機制，全稱Least Recently Used，字面意思就是最近最少使用，是一種快取淘汰策略，換句話說，LRU機制就是認為最近使用的資料是有用的，很久沒用過的資料是無用的，當記憶體滿了就優先洗掉很久沒有使用的資料，
基于LeetCode146，可以使用哈希鏈表或者自定義雙端鏈表類+哈希表兩種方法來實作LRU快取機制，
它應該支持以下操作：獲取資料get和 寫入資料put，
獲取資料get(key)：如果密鑰 (key) 存在于快取中，則獲取密鑰的值（總是正數），否則回傳-1，
寫入資料put(key, value)：如果密鑰不存在，則寫入其資料值，當快取容量達到上限時，它應該在寫入新資料之前洗掉最近最少使用的資料值，從而為新的資料值留出空間，
1. 基于LinkedHashMap實作LRU快取機制
class LRUCache {
Map<Integer, Integer> map;
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new LinkedHashMap<>();
}
public int get(int key) {
// 若key不存在回傳-1
if(!map.containsKey(key)) return -1;
// 若key存在則獲取key對應的val
int val = map.get(key);
// 更新位置
put(key, val);
return val;
}
public void put(int key, int val) {
// 若快取命中則先洗掉資料在重新放入以更新位置
if(map.containsKey(key)) {
map.remove(key);
map.put(key, val);
} else {
// 若快取未命中則先判斷是否達到最大容量
// 超出容量則洗掉最久沒有使用的資料（利用迭代器洗掉第一個）
if (capacity == map.size()) map.remove(map.keySet().iterator().next());
// 洗掉完成后存放新資料
map.put(key, val);
}
}
}
2. 基于DoubleList與HashMap實作LRU快取機制
如果不使用LinkedHashMap，可以自己造輪子，自定義DoubleList類并結合HashMap實作與LinkedHashMap相同的功能，
class LRUCache {
int capacity;
DoubleList cache;
Map<Integer, Node> map;
public LRUCache(int capacity) {
this.capacity = capacity;
cache = new DoubleList();
map = new HashMap<>();
}
public int get(int key) {
if(!map.containsKey(key)) return -1;
int val = map.get(key).val;
put(key, val);
return val;
}
public void put(int key, int val) {
Node node = new Node(key, val);
if(map.containsKey(key)) {
cache.remove(map.get(key));
cache.addFirst(node);
map.put(key, node);
} else {
if(capacity == cache.size) map.remove(cache.removeLast().key);
cache.addFirst(node);
map.put(key, node);
}
}
}
class DoubleList {
Node head, tail;
int size;
public DoubleList() {
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
size = 0;
}
public void addFirst(Node node) {
Node temp = head.next;
node.next = temp;
temp.prev = node;
head.next = node;
node.prev = head;
size++;
}
public void remove(Node node) {
Node temp = node.prev;
temp.next = node.next;
temp.next.prev = temp;
size--;
}
public Node removeLast() {
if (size == 0) return null;
Node del = tail.prev;
remove(del);
return del;
}
}
class Node {
int key, val;
Node prev, next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/55055.html
標籤：Java
上一篇：Java成員內部類、靜態內部類、區域內部類、匿名內部類詳解
下一篇：C語言