當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

动手实现一个 LRU cache

發(fā)布時間：2025/3/21 编程问答 40 豆豆

生活随笔收集整理的這篇文章主要介紹了动手实现一个 LRU cache 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

前言

LRU 是?LeastRecentlyUsed?的簡寫，字面意思則是?最近最少使用。

通常用于緩存的淘汰策略實現，由于緩存的內存非常寶貴，所以需要根據某種規(guī)則來剔除數據保證內存不被撐滿。

如常用的 Redis 就有以下幾種策略：

策略描述

volatile-lru	從已設置過期時間的數據集中挑選最近最少使用的數據淘汰
volatile-ttl	從已設置過期時間的數據集中挑選將要過期的數據淘汰
volatile-random	從已設置過期時間的數據集中任意選擇數據淘汰
allkeys-lru	從所有數據集中挑選最近最少使用的數據淘汰
allkeys-random	從所有數據集中任意選擇數據進行淘汰
no-envicition	禁止驅逐數據

摘抄自:https://github.com/CyC2018/Interview-Notebook/blob/master/notes/Redis.md#%E5%8D%81%E4%B8%89%E6%95%B0%E6%8D%AE%E6%B7%98%E6%B1%B0%E7%AD%96%E7%95%A5

?

實現一

之前也有接觸過一道面試題，大概需求是：

實現一個 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()) ;}@Overridepublic Set<Entry> entrySet() {return super.keySet();}@Overridepublic 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 ;}@Overridepublic 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);}@Overridepublic 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();//在鏈表中找到了把上一個節(jié)點的 next 指向當前節(jié)點的下一個節(jié)點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") ;}//移除該 keyObject key = node.key ;remove(key) ;lruCallback() ;}}/*** 數量減小*/private void sizeDown(){if (QUEUE.size() == 0){flag = false ;}this.size.decrementAndGet() ;}@Overridepublic 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;}@Overridepublic 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{@Overridepublic 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");}}}}}

感興趣的朋友可以直接從:

https://github.com/crossoverJie/Java-Interview/blob/master/src/main/java/com/crossoverjie/actual/LRUAbstractMap.java

下載代碼本地運行。

代碼看著比較多，其實實現的思路還是比較簡單：

采用了與 HashMap 一樣的保存數據方式，只是自己手動實現了一個簡易版。
內部采用了一個隊列來保存每次寫入的數據。
寫入的時候判斷緩存是否大于了閾值 N，如果滿足則根據隊列的 FIFO 特性將隊列頭的數據刪除。因為隊列頭的數據肯定是最先放進去的。
再開啟了一個守護線程用于判斷最先放進去的數據是否超期（因為就算超期也是最先放進去的數據最有可能滿足超期條件。）
設置為守護線程可以更好的表明其目的（最壞的情況下，如果是一個用戶線程最終有可能導致程序不能正常退出，因為該線程一直在運行，守護線程則不會有這個情況。）

以上代碼大體功能滿足了，但是有一個致命問題。

就是最近最少使用沒有滿足，刪除的數據都是最先放入的數據。

不過其中的?putget?流程算是一個簡易的 HashMap 實現，可以對 HashMap 加深一些理解。

?

實現二

因此如何來實現一個完整的 LRU 緩存呢，這次不考慮過期時間的問題。

其實從上一個實現也能想到一些思路：

要記錄最近最少使用，那至少需要一個有序的集合來保證寫入的順序。
在使用了數據之后能夠更新它的順序。

基于以上兩點很容易想到一個常用的數據結構：鏈表。

每次寫入數據時將數據放入鏈表頭結點。

使用數據時候將數據移動到頭結點。

緩存數量超過閾值時移除鏈表尾部數據。

因此有了以下實現：

public class LRUMap<K, V> {private final Map<K, V> cacheMap = new HashMap<>();/*** 最大緩存大小*/private int cacheSize;/*** 節(jié)點大小*/private int nodeCount;/*** 頭結點*/private Node<K, V> header;/*** 尾結點*/private Node<K, V> tailer;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){Node<K, V> node = getNode(key);//移動到頭結點moveToHead(node) ;return cacheMap.get(key);}private void moveToHead(Node<K,V> node){//如果是最后的一個節(jié)點if (node.tail == null){node.next.tail = null ;tailer = node.next ;nodeCount -- ;}//如果是本來就是頭節(jié)點不作處理if (node.next == null){return ;}//如果處于中間節(jié)點if (node.tail != null && node.next != null){//它的上一節(jié)點指向它的下一節(jié)點也就刪除當前節(jié)點node.tail.next = node.next ;nodeCount -- ;}//最后在頭部增加當前節(jié)點//注意這里需要重新 new 一個對象，不然原本的node 還有著下面的引用，會造成內存溢出。node = new Node<>(node.getKey(),node.getValue()) ;addHead(node) ;}/*** 鏈表查詢效率較低* @param key* @return*/private Node<K,V> getNode(K key){Node<K,V> node = 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) {Node<K, V> node = new Node<>(key, value);//容量滿了刪除最后一個if (cacheSize == nodeCount) {//刪除尾結點delTail();}//寫入頭結點addHead(node);}/*** 添加頭結點** @param node*/private void addHead(Node<K, V> node) {//寫入頭結點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<K, V> {private K key;private V value;Node<K, V> tail;Node<K, V> next;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;}}@Overridepublic String toString() {StringBuilder sb = new StringBuilder() ;Node<K,V> node = 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

實際效果，寫入時：

? ?@Testpublic void put() throws Exception {LRUMap<String,Integer> 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-->

使用時：

? ?@Testpublic void get() throws Exception {LRUMap<String,Integer> 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-->

實現思路和上文提到的一致，說下重點：

數據是直接利用 HashMap 來存放的。
內部使用了一個雙向鏈表來存放數據，所以有一個頭結點 header，以及尾結點 tailer。
每次寫入頭結點，刪除尾結點時都是依賴于 header tailer，如果看著比較懵建議自己實現一個鏈表熟悉下，或結合下文的對象關系圖一起理解。
使用數據移動到鏈表頭時，第一步是需要在雙向鏈表中找到該節(jié)點。這里就體現出鏈表的問題了。查找效率很低，最差需要?O(N)。之后依賴于當前節(jié)點進行移動。
在寫入頭結點時有判斷鏈表大小等于 2 時需要刪除初始化的頭尾結點。這是因為初始化時候生成了兩個雙向節(jié)點，沒有數據只是為了形成一個數據結構。當真實數據進來之后需要刪除以方便后續(xù)的操作（這點可以繼續(xù)優(yōu)化）。
以上的所有操作都是線程不安全的，需要使用者自行控制。

下面是對象關系圖：

初始化時

寫入數據時

LRUMap<String,Integer> lruMap = new LRUMap(3) ; lruMap.put("1",1) ;

lruMap.put("2",2) ;

lruMap.put("3",3) ;

lruMap.put("4",4) ;

獲取數據時

數據和上文一樣：

Integer integer = lruMap.get("2");

通過以上幾張圖應該是很好理解數據是如何存放的了。

?

實現三

其實如果對 Java 的集合比較熟悉的話，會發(fā)現上文的結構和 LinkedHashMap 非常類似。

對此不太熟悉的朋友可以先了解下?LinkedHashMap 底層分析?。

所以我們完全可以借助于它來實現：

public class LRULinkedMap<K,V> {/*** 最大緩存大小*/private int cacheSize;private LinkedHashMap<K,V> cacheMap ;public LRULinkedMap(int cacheSize) {this.cacheSize = cacheSize;cacheMap = new LinkedHashMap(16,0.75F,true){@Overrideprotected 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<K, V>> getAll() {return new ArrayList<Map.Entry<K, V>>(cacheMap.entrySet());}}

源碼：?https://github.com/crossoverJie/Java-Interview/blob/master/src/main/java/com/crossoverjie/actual/LRULinkedMap.java

這次就比較簡潔了，也就幾行代碼（具體的邏輯 LinkedHashMap 已經幫我們實現好了）

實際效果:

? ?@Testpublic void put() throws Exception {LRULinkedMap<String,Integer> map = new LRULinkedMap(3) ;map.put("1",1);map.put("2",2);map.put("3",3);for (Map.Entry<String, Integer> e : map.getAll()){System.out.print(e.getKey() + " : " + e.getValue() + "\t");}System.out.println("");map.put("4",4);for (Map.Entry<String, Integer> e : map.getAll()){System.out.print(e.getKey() + " : " + e.getValue() + "\t");}}

//輸出

1 : 1 ? ?2 : 2 ? 3 : 3 ? 2 : 2 ? ?3 : 3 ? 4 : 4 ? ?

使用時：

? ?@Testpublic void get() throws Exception {LRULinkedMap<String,Integer> map = new LRULinkedMap(4) ;map.put("1",1);map.put("2",2);map.put("3",3);map.put("4",4);for (Map.Entry<String, Integer> e : map.getAll()){System.out.print(e.getKey() + " : " + e.getValue() + "\t");}System.out.println("");map.get("1") ;for (Map.Entry<String, Integer> 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

LinkedHashMap 內部也有維護一個雙向隊列，在初始化時也會給定一個緩存大小的閾值。初始化時自定義是否需要刪除最近不常使用的數據，如果是則會按照實現二中的方式管理數據。

其實主要代碼就是重寫了 LinkedHashMap 的 removeEldestEntry 方法:

? ?protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false;}

它默認是返回 false，也就是不會管有沒有超過閾值。

所以我們自定義大于了閾值時返回 true，這樣 LinkedHashMap 就會幫我們刪除最近最少使用的數據。