10 行 Java 代碼實(shí)現(xiàn) LRU 緩存 （整理自網(wǎng)絡(luò)）

最近最少使用緩存的回收

為了實(shí)現(xiàn)緩存回收，我們需要很容易做到：

• 查詢出最近最晚使用的項(xiàng)
• 給最近最少使用的項(xiàng)做一個(gè)標(biāo)記

鏈表可以實(shí)現(xiàn)這兩個(gè)操作。檢測(cè)使用最近最少使用的項(xiàng)只需要返回鏈表的尾部。標(biāo)記一項(xiàng)為最近最少使用的項(xiàng)只需要從當(dāng)前位置移除而后將該項(xiàng)放置到鏈表頭部。比較困難的事情是怎么快速的在鏈表中找到該項(xiàng)。

哈希表的幫助

看一下我們工具箱中的數(shù)據(jù)結(jié)構(gòu)，哈希表可以在（消耗）常量的時(shí)間內(nèi)索引到某個(gè)對(duì)象。如果我們創(chuàng)建一個(gè)形如 key -> 鏈表節(jié)點(diǎn) 的哈希表，我們就能在常量時(shí)間內(nèi)找到最近使用的節(jié)點(diǎn)。更甚的是，我們也能夠在常量時(shí)間內(nèi)判斷節(jié)點(diǎn)是否存在。找到這個(gè)節(jié)點(diǎn)后，我們就能將這個(gè)節(jié)點(diǎn)移動(dòng)到鏈表的最前端了，標(biāo)記為最近使用的項(xiàng)。

Java 捷徑

很少有一種編程語(yǔ)言的標(biāo)準(zhǔn)庫(kù)中有通用的數(shù)據(jù)結(jié)構(gòu)能提供上述功能的。這是一種混合的數(shù)據(jù)結(jié)構(gòu)，我們需要在哈希表的基礎(chǔ)上建立一個(gè)鏈表。但是 Java 已經(jīng)為我們提供了這種形式的數(shù)據(jù)結(jié)構(gòu)LinkedHashMap，它甚至提供可覆蓋回收策略的方法 removeEldestEntry。唯一需要我們注意的事情是，該鏈表的順序是插入的順序，而不是訪問(wèn)的順序。但是，有一個(gè)構(gòu)造函數(shù)提供了一個(gè)選項(xiàng)，可以使用訪問(wèn)順序。

代碼示例：

import java.util.LinkedHashMap; import java.util.Map;public LRUCache extends LinkedHashMap {private int cacheSize;public LRUCache(int cacheSize) {super(16, 0.75, true);this.cacheSize = cacheSize;}protected boolean removeEldestEntry(Map.Entry eldest) {return size() >= cacheSize;} }

示例完畢。

轉(zhuǎn)載于:https://www.cnblogs.com/flotang/p/9962111.html

總結(jié)

以上是生活随笔為你收集整理的10 行 Java 代码实现 LRU 缓存的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。