0. 前情提要
面試官： 你能手寫個LRU快取嗎？
你： LRU是什么東西？（一臉懵逼狀）
面試官： LRU全稱Least Recently Used（最近最少使用），用來淘汰不常用資料，保留熱點資料，
你寫了5分鐘，然而只寫了個get和put方法體，里面邏輯實在不知道咋寫，
面試官： 今天的面試先到這吧，有其他面試我們會再聯系你，
我信你個鬼，你個糟老頭子壞滴很，還聯系啥，涼涼了，
別擔心，再有人問你LRU，就把這篇文章丟給他，保證當場發offer，
1. 實作思路
目的是把最不常用的資料淘汰掉，所以需要記錄一下每個元素的訪問次數，最簡單的方法就是把所有元素按使用情況排序，最近使用的，移到末尾，快取滿了，就從頭部洗掉，
2. 使用哪種資料結構實作？
常用的資料結構有陣列、鏈表、堆疊、佇列，考慮到要從兩端操作元素，就不能使用堆疊和佇列，
每次使用一個元素，都要把這個元素移到末尾，包含一次洗掉和一次添加操作，使用陣列會有大量的拷貝操作，不適合，
又考慮到洗掉一個元素，要把這個元素的前一個節點指向下一個節點，使用雙鏈接最合適，
鏈表不適合查詢，因為每次都要遍歷所有元素，可以和HashMap配合使用，
雙鏈表 + HashMap
3. 代碼實作
import java.util.HashMap;
import java.util.Map;
/**
* @author yideng
*/
public class LRUCache<K, V> {
/**
* 雙鏈表的元素節點
*/
private class Entry<K, V> {
Entry<K, V> before;
Entry<K, V> after;
private K key;
private V value;
}
/**
* 快取容量大小
*/
private Integer capacity;
/**
* 頭結點
*/
private Entry<K, V> head;
/**
* 尾節點
*/
private Entry<K, V> tail;
/**
* 用來存盤所有元素
*/
private Map<K, Entry<K, V>> caches = new HashMap<>();
public LRUCache(int capacity) {
this.capacity = capacity;
}
public V get(K key) {
final Entry<K, V> node = caches.get(key);
if (node != null) {
// 有訪問，就移到鏈表末尾
afterNodeAccess(node);
return node.value;
}
return null;
}
/**
* 把該元素移到末尾
*/
private void afterNodeAccess(Entry<K, V> e) {
Entry<K, V> last = tail;
// 如果e不是尾節點，才需要移動
if (last != e) {
// 洗掉該該節點與前一個節點的聯系，判斷是不是頭結點
if (e.before == null) {
head = e.after;
} else {
e.before.after = e.after;
}
// 洗掉該該節點與后一個節點的聯系
if (e.after == null) {
last = e.before;
} else {
e.after.before = e.before;
}
// 把該節點添加尾節點，判斷尾節點是否為空
if (last == null) {
head = e;
} else {
e.before = last;
last.after = e;
}
e.after = null;
tail = e;
}
}
public V put(K key, V value) {
Entry<K, V> entry = caches.get(key);
if (entry == null) {
entry = new Entry<>();
entry.key = key;
entry.value = https://www.cnblogs.com/yidengjiagou/p/value;
// 新節點添加到末尾
linkNodeLast(entry);
caches.put(key, entry);
// 節點數大于容量，就洗掉頭節點
if (this.caches.size() > this.capacity) {
this.caches.remove(head.key);
afterNodeRemoval(head);
}
return null;
}
entry.value = value;
// 節點有更新就移動到未節點
afterNodeAccess(entry);
caches.put(key, entry);
return entry.value;
}
/**
* 把該節點添加到尾節點
*/
private void linkNodeLast(Entry e) {
final Entry last = this.tail;
if (head == null) {
head = e;
} else {
e.before = last;
last.after = e;
}
tail = e;
}
/**
* 洗掉該節點
*/
void afterNodeRemoval(Entry e) {
if (e.before == null) {
head = e.after;
} else {
e.before.after = e.after;
}
if (e.after == null) {
tail = e.before;
} else {
e.after.before = e.before;
}
}
}
4. 其實還有更簡單的實作
import java.util.LinkedHashMap;
import java.util.Map;
/**
* @author yideng
*/
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
// 最大容量
private final int maximumSize;
public LRUCache(final int maximumSize) {
// true代表按訪問順序排序，false代表按插入順序
super(maximumSize, 0.75f, true);
this.maximumSize = maximumSize;
}
/**
* 當節點數大于最大容量時，就洗掉最舊的元素
*/
@Override
protected boolean removeEldestEntry(final Map.Entry eldest) {
return size() > this.maximumSize;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/491777.html
標籤：Java