前言
LRU 是 <code>Least Recently Used/<code> 的簡寫，字面意思則是<code>最近最少使用/<code>。
通常用於緩存的淘汰策略實現，由於緩存的內存非常寶貴，所以需要根據某種規則來剔除數據保證內存不被撐滿。
如常用的 Redis 就有以下幾種策略：
<table><thead>實現一
之前也有接觸過一道面試題，大概需求是：
實現一個 LRU 緩存，當緩存數據達到 N 之後需要淘汰掉最近最少使用的數據。
N 小時之內沒有被訪問的數據也需要淘汰掉。
以下是我的實現：
public class LRUAbstractMap extends java.util.AbstractMap { private final static Logger LOGGER = LoggerFactory.getLogger(LRUAbstractMap.class); /**
* 檢查是否超期線程
*/
private ExecutorService checkTimePool ; /**
* map 最大size
*/
private final static int MAX_SIZE = 1024 ; private final static ArrayBlockingQueue<node> QUEUE = new ArrayBlockingQueue<>(MAX_SIZE) ; /**
* 默認大小
*/
private final static int DEFAULT_ARRAY_SIZE =1024 ; /**
* 數組長度
*/
private int arraySize ; /**
* 數組
*/
private Object[] arrays ; /**
* 判斷是否停止 flag
*/
private volatile boolean flag = true ; /**
* 超時時間
*/
private final static Long EXPIRE_TIME = 60 * 60 * 1000L ; /**
* 整個 Map 的大小
*/
private volatile AtomicInteger size ; public LRUAbstractMap() {
arraySize = DEFAULT_ARRAY_SIZE;
arrays = new Object[arraySize] ; //開啟一個線程檢查最先放入隊列的值是否超期
executeCheckTime();
} /**
* 開啟一個線程檢查最先放入隊列的值是否超期 設置為守護線程
*/
private void executeCheckTime() {
ThreadFactory namedThreadFactory = new ThreadFactoryBuilder()
.setNameFormat("check-thread-%d")
.setDaemon(true)
.build();
checkTimePool = new ThreadPoolExecutor(1, 1, 0L, TimeUnit.MILLISECONDS, new ArrayBlockingQueue<>(1),namedThreadFactory,new ThreadPoolExecutor.AbortPolicy());
checkTimePool.execute(new CheckTimeThread()) ;
} @Override
public Set<entry> entrySet() { return super.keySet();
} @Override
public Object put(Object key, Object value) { int hash = hash(key); int index = hash % arraySize ;
Node currentNode = (Node) arrays[index] ; if (currentNode == null){
arrays[index] = new Node(null,null, key, value); //寫入隊列
QUEUE.offer((Node) arrays[index]) ;
sizeUp();
}else {
Node cNode = currentNode ;
Node nNode = cNode ; //存在就覆蓋
if (nNode.key == key){
cNode.val = value ;
} while (nNode.next != null){ //key 存在 就覆蓋 簡單判斷
if (nNode.key == key){
nNode.val = value ; break ;
}else { //不存在就新增鏈表
sizeUp();
Node node = new Node(nNode,null,key,value) ; //寫入隊列
QUEUE.offer(currentNode) ;
cNode.next = node ;
}
nNode = nNode.next ;
}
} return null ;
} @Override
public Object get(Object key) { int hash = hash(key) ; int index = hash % arraySize ;
Node currentNode = (Node) arrays[index] ; if (currentNode == null){ return null ;
} if (currentNode.next == null){ //更新時間
currentNode.setUpdateTime(System.currentTimeMillis()); //沒有衝突
return currentNode ;
}
Node nNode = currentNode ; while (nNode.next != null){ if (nNode.key == key){ //更新時間
currentNode.setUpdateTime(System.currentTimeMillis()); return nNode ;
}
nNode = nNode.next ;
} return super.get(key);
} @Override
public Object remove(Object key) { int hash = hash(key) ; int index = hash % arraySize ;
Node currentNode = (Node) arrays[index] ; if (currentNode == null){ return null ;
} if (currentNode.key == key){
sizeDown();
arrays[index] = null ; //移除隊列
QUEUE.poll(); return currentNode ;
}
Node nNode = currentNode ; while (nNode.next != null){ if (nNode.key == key){
sizeDown(); //在鏈表中找到了 把上一個節點的 next 指向當前節點的下一個節點
nNode.pre.next = nNode.next ;
nNode = null ; //移除隊列
QUEUE.poll(); return nNode;
}
nNode = nNode.next ;
} return super.remove(key);
} /**
* 增加size
*/
private void sizeUp(){ //在put值時候認為裡邊已經有數據了
flag = true ; if (size == null){
size = new AtomicInteger() ;
} int size = this.size.incrementAndGet(); if (size >= MAX_SIZE) { //找到隊列頭的數據
Node node = QUEUE.poll() ; if (node == null){ throw new RuntimeException("data error") ;
} //移除該 key
Object key = node.key ;
remove(key) ;
lruCallback() ;
}
} /**
* 數量減小
*/
private void sizeDown(){ if (QUEUE.size() == 0){
flag = false ;
} this.size.decrementAndGet() ;
} @Override
public int size() { return size.get() ;
} /**
* 鏈表
*/
private class Node{ private Node next ; private Node pre ; private Object key ; private Object val ; private Long updateTime ; public Node(Node pre,Node next, Object key, Object val) { this.pre = pre ; this.next = next; this.key = key; this.val = val; this.updateTime = System.currentTimeMillis() ;
} public void setUpdateTime(Long updateTime) { this.updateTime = updateTime;
} public Long getUpdateTime() { return updateTime;
} @Override
public String toString() { return "Node{" + "key=" + key + ", val=" + val + '}';
}
} /**
* copy HashMap 的 hash 實現
* @param key
* @return
*/
public int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} private void lruCallback(){
LOGGER.debug("lruCallback");
} private class CheckTimeThread implements Runnable{ @Override
public void run() { while (flag){ try {
Node node = QUEUE.poll(); if (node == null){ continue ;
}
Long updateTime = node.getUpdateTime() ; if ((updateTime - System.currentTimeMillis()) >= EXPIRE_TIME){
remove(node.key) ;
}
} catch (Exception e) {
LOGGER.error("InterruptedException");
}
}
}
}
}/<entry>/<node>感興趣的朋友可以直接從:
https://github.com/crossoverJie/Java-Interview/blob/master/src/main/java/com/crossoverjie/actual/LRUAbstractMap.java
下載代碼本地運行。
代碼看著比較多，其實實現的思路還是比較簡單：
採用了與 HashMap 一樣的保存數據方式，只是自己手動實現了一個簡易版。
內部採用了一個隊列來保存每次寫入的數據。
寫入的時候判斷緩存是否大於了閾值 N，如果滿足則根據隊列的 FIFO 特性將隊列頭的數據刪除。因為隊列頭的數據肯定是最先放進去的。
再開啟了一個守護線程用於判斷最先放進去的數據是否超期（因為就算超期也是最先放進去的數據最有可能滿足超期條件。）
設置為守護線程可以更好的表明其目的（最壞的情況下，如果是一個用戶線程最終有可能導致程序不能正常退出，因為該線程一直在運行，守護線程則不會有這個情況。）
以上代碼大體功能滿足了，但是有一個致命問題。
就是最近最少使用沒有滿足，刪除的數據都是最先放入的數據。
不過其中的 <code>put get/<code> 流程算是一個簡易的 HashMap 實現，可以對 HashMap 加深一些理解。實現二
因此如何來實現一個完整的 LRU 緩存呢，這次不考慮過期時間的問題。
其實從上一個實現也能想到一些思路：
要記錄最近最少使用，那至少需要一個有序的集合來保證寫入的順序。
-
在使用了數據之後能夠更新它的順序。
基於以上兩點很容易想到一個常用的數據結構：鏈表。
每次寫入數據時將數據放入鏈表頭結點。
使用數據時候將數據移動到頭結點。
緩存數量超過閾值時移除鏈表尾部數據。
因此有了以下實現：
public class LRUMap{ private final Map cacheMap = new HashMap<>(); /**
* 最大緩存大小
*/
private int cacheSize; /**
* 節點大小
*/
private int nodeCount; /**
* 頭結點
*/
private Nodeheader; /**
* 尾結點
*/
private Nodetailer; public LRUMap(int cacheSize) { this.cacheSize = cacheSize; //頭結點的下一個結點為空
header = new Node<>();
header.next = null; //尾結點的上一個結點為空
tailer = new Node<>();
tailer.tail = null; //雙向鏈表 頭結點的上結點指向尾結點
header.tail = tailer; //尾結點的下結點指向頭結點
tailer.next = header;
} public void put(K key, V value) {
cacheMap.put(key, value); //雙向鏈表中添加結點
addNode(key, value);
} public V get(K key){
Nodenode = getNode(key); //移動到頭結點
moveToHead(node) ; return cacheMap.get(key);
} private void moveToHead(Nodenode){ //如果是最後的一個節點
if (node.tail == null){
node.next.tail = null ;
tailer = node.next ;
nodeCount -- ;
} //如果是本來就是頭節點 不作處理
if (node.next == null){ return ;
} //如果處於中間節點
if (node.tail != null && node.next != null){ //它的上一節點指向它的下一節點 也就刪除當前節點
node.tail.next = node.next ;
nodeCount -- ;
} //最後在頭部增加當前節點
//注意這裡需要重新 new 一個對象，不然原本的node 還有著下面的引用，會造成內存溢出。
node = new Node<>(node.getKey(),node.getValue()) ;
addHead(node) ;
} /**
* 鏈表查詢 效率較低
* @param key
* @return
*/
private NodegetNode(K key){
Nodenode = tailer ; while (node != null){ if (node.getKey().equals(key)){ return node ;
}
node = node.next ;
} return null ;
} /**
* 寫入頭結點
* @param key
* @param value
*/
private void addNode(K key, V value) {
Nodenode = new Node<>(key, value); //容量滿了刪除最後一個
if (cacheSize == nodeCount) { //刪除尾結點
delTail();
} //寫入頭結點
addHead(node);
} /**
* 添加頭結點
*
* @param node
*/
private void addHead(Nodenode) { //寫入頭結點
header.next = node;
node.tail = header;
header = node;
nodeCount++; //如果寫入的數據大於2個 就將初始化的頭尾結點刪除
if (nodeCount == 2) {
tailer.next.next.tail = null;
tailer = tailer.next.next;
}
}
private void delTail() { //把尾結點從緩存中刪除
cacheMap.remove(tailer.getKey()); //刪除尾結點
tailer.next.tail = null;
tailer = tailer.next;
nodeCount--;
} private class Node{ private K key; private V value;
Nodetail;
Nodenext; public Node(K key, V value) { this.key = key; this.value = value;
} public Node() {
} public K getKey() { return key;
} public void setKey(K key) { this.key = key;
} public V getValue() { return value;
} public void setValue(V value) { this.value = value;
}
} @Override
public String toString() {
StringBuilder sb = new StringBuilder() ;
Nodenode = tailer ; while (node != null){
sb.append(node.getKey()).append(":")
.append(node.getValue())
.append("-->") ;
node = node.next ;
} return sb.toString();
}
}
源碼：
https://github.com/crossoverJie/Java-Interview/blob/master/src/main/java/com/crossoverjie/actual/LRUMap.java
實際效果，寫入時：
@Test
public void put() throws Exception {
LRUMap<string> lruMap = new LRUMap(3) ;
lruMap.put("1",1) ;
lruMap.put("2",2) ;
lruMap.put("3",3) ;
System.out.println(lruMap.toString());
lruMap.put("4",4) ;
System.out.println(lruMap.toString());
lruMap.put("5",5) ;
System.out.println(lruMap.toString());
}//輸出：1:1-->2:2-->3:3-->2:2-->3:3-->4:4-->3:3-->4:4-->5:5-->/<string>
使用時：
@Test
public void get() throws Exception {
LRUMap<string> lruMap = new LRUMap(3) ;
lruMap.put("1",1) ;
lruMap.put("2",2) ;
lruMap.put("3",3) ;
System.out.println(lruMap.toString());
System.out.println("==============");
Integer integer = lruMap.get("1");
System.out.println(integer);
System.out.println("==============");
System.out.println(lruMap.toString());
}
//輸出1:1-->2:2-->3:3-->
==============1==============2:2-->3:3-->1:1-->/<string>
實現思路和上文提到的一致，說下重點：
數據是直接利用 HashMap 來存放的。
內部使用了一個雙向鏈表來存放數據，所以有一個頭結點 header，以及尾結點 tailer。
每次寫入頭結點，刪除尾結點時都是依賴於 header tailer，如果看著比較懵建議自己實現一個鏈表熟悉下，或結合下文的對象關係圖一起理解。
使用數據移動到鏈表頭時，第一步是需要在雙向鏈表中找到該節點。這裡就體現出鏈表的問題了。查找效率很低，最差需要 <code>O(N)/<code>。之後依賴於當前節點進行移動。
在寫入頭結點時有判斷鏈表大小等於 2 時需要刪除初始化的頭尾結點。這是因為初始化時候生成了兩個雙向節點，沒有數據只是為了形成一個數據結構。當真實數據進來之後需要刪除以方便後續的操作（這點可以繼續優化）。
以上的所有操作都是線程不安全的，需要使用者自行控制。
下面是對象關係圖：
初始化時
寫入數據時
LRUMap<string> lruMap = new LRUMap(3) ;
lruMap.put("1",1) ;/<string>
lruMap.put("2",2) ;
lruMap.put("3",3) ;
lruMap.put("4",4) ;
獲取數據時
數據和上文一樣：
Integer integer = lruMap.get("2");
通過以上幾張圖應該是很好理解數據是如何存放的了。
實現三
其實如果對 Java 的集合比較熟悉的話，會發現上文的結構和 LinkedHashMap 非常類似。
對此不太熟悉的朋友可以先了解下 LinkedHashMap 底層分析 。
所以我們完全可以藉助於它來實現：
public class LRULinkedMap{ /**
* 最大緩存大小
*/
private int cacheSize; private LinkedHashMapcacheMap ; public LRULinkedMap(int cacheSize) { this.cacheSize = cacheSize;
cacheMap = new LinkedHashMap(16,0.75F,true){ @Override
protected boolean removeEldestEntry(Map.Entry eldest) { if (cacheSize + 1 == cacheMap.size()){ return true ;
}else { return false ;
}
}
};
} public void put(K key,V value){
cacheMap.put(key,value) ;
} public V get(K key){ return cacheMap.get(key) ;
} public Collection<map.entry>> getAll() { return new ArrayList<map.entry>>(cacheMap.entrySet());
}
}/<map.entry>/<map.entry>
源碼：
https://github.com/crossoverJie/Java-Interview/blob/master/src/main/java/com/crossoverjie/actual/LRULinkedMap.java
這次就比較簡潔了，也就幾行代碼（具體的邏輯 LinkedHashMap 已經幫我們實現好了）
實際效果:
@Test
public void put() throws Exception {
LRULinkedMap<string> map = new LRULinkedMap(3) ;
map.put("1",1);
map.put("2",2);
map.put("3",3); for (Map.Entry<string> e : map.getAll()){
System.out.print(e.getKey() + " : " + e.getValue() + "\\t");
}
System.out.println("");
map.put("4",4); for (Map.Entry<string> e : map.getAll()){
System.out.print(e.getKey() + " : " + e.getValue() + "\\t");
}
}
//輸出1 : 1 2 : 2 3 : 3 2 : 2 3 : 3 4 : 4 /<string>/<string>/<string>
使用時：
@Test
public void get() throws Exception {
LRULinkedMap<string> map = new LRULinkedMap(4) ;
map.put("1",1);
map.put("2",2);
map.put("3",3);
map.put("4",4); for (Map.Entry<string> e : map.getAll()){
System.out.print(e.getKey() + " : " + e.getValue() + "\\t");
}
System.out.println("");
map.get("1") ; for (Map.Entry<string> e : map.getAll()){
System.out.print(e.getKey() + " : " + e.getValue() + "\\t");
}
}
}//輸出1 : 1 2 : 2 3 : 3 4 : 4 2 : 2 3 : 3 4 : 4 1 : 1/<string>/<string>/<string>
LinkedHashMap 內部也有維護一個雙向隊列，在初始化時也會給定一個緩存大小的閾值。初始化時自定義是否需要刪除最近不常使用的數據，如果是則會按照實現二中的方式管理數據。
其實主要代碼就是重寫了 LinkedHashMap 的 removeEldestEntry 方法:
protected boolean removeEldestEntry(Map.Entryeldest) { return false;
}
它默認是返回 false，也就是不會管有沒有超過閾值。
所以我們自定義大於了閾值時返回 true，這樣 LinkedHashMap 就會幫我們刪除最近最少使用的數據。
總結
以上就是對 LRU 緩存的實現，瞭解了這些至少在平時使用時可以知其所以然。
當然業界使用較多的還有 guava 的實現，並且它還支持多種過期策略。
分享到:
閱讀更多 一字咖啡屋 的文章
