LRU是Least Recently Used 的縮寫，翻譯過來就是“最近最少使用”，LRU緩存就是使用這種原理實(shí)現(xiàn)，簡(jiǎn)單的說就是緩存一定量的數(shù)據(jù)，當(dāng)超過設(shè)定的閾值時(shí)就把一些過期的數(shù)據(jù)刪除掉。
比如我們緩存10000條數(shù)據(jù)，當(dāng)數(shù)據(jù)小于10000時(shí)可以隨意添加，當(dāng)超過10000時(shí)就需要把新的數(shù)據(jù)添加進(jìn)來，同時(shí)要把過期數(shù)據(jù)刪除，以確保我們最大緩存10000條，那怎么確定刪除哪條過期數(shù)據(jù)呢，采用LRU算法實(shí)現(xiàn)的話就是將最老的數(shù)據(jù)刪掉。
下面來說下Java版的LRU緩存實(shí)現(xiàn)：（推薦：java視頻教程）
Java里面實(shí)現(xiàn)LRU緩存通常有兩種選擇，一種是使用LinkedHashMap，一種是自己設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，使用鏈表+HashMap
LRU Cache的LinkedHashMap實(shí)現(xiàn)
LinkedHashMap自身已經(jīng)實(shí)現(xiàn)了順序存儲(chǔ)，默認(rèn)情況下是按照元素的添加順序存儲(chǔ)，也可以啟用按照訪問順序存儲(chǔ)，即最近讀取的數(shù)據(jù)放在最前面，最早讀取的數(shù)據(jù)放在最后面，然后它還有一個(gè)判斷是否刪除最老數(shù)據(jù)的方法，默認(rèn)是返回false，即不刪除數(shù)據(jù)。
我們使用LinkedHashMap實(shí)現(xiàn)LRU緩存的方法就是對(duì)LinkedHashMap實(shí)現(xiàn)簡(jiǎn)單的擴(kuò)展，擴(kuò)展方式有兩種，一種是inheritance，一種是delegation。
//LinkedHashMap的一個(gè)構(gòu)造函數(shù)，當(dāng)參數(shù)accessOrder為true時(shí)，即會(huì)按照訪問順序排序，最近訪問的放在最前，最早訪問的放在后面
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//LinkedHashMap自帶的判斷是否刪除最老的元素方法，默認(rèn)返回false，即不刪除老數(shù)據(jù)
//我們要做的就是重寫這個(gè)方法，當(dāng)滿足一定條件時(shí)刪除老數(shù)據(jù)
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}LRU緩存LinkedHashMap(inheritance)實(shí)現(xiàn)
采用inheritance方式實(shí)現(xiàn)比較簡(jiǎn)單，而且實(shí)現(xiàn)了Map接口，在多線程環(huán)境使用時(shí)可以使用 Collections.synchronizedMap()方法實(shí)現(xiàn)線程安全操作
package cn.lzrabbit.structure.lru;
import java.util.LinkedHashMap;
import java.util.Map;
/**
* Created by liuzhao on 14-5-15.
*/
public class LRUCache2<K, V> extends LinkedHashMap<K, V> {
private final int MAX_CACHE_SIZE;
public LRUCache2(int cacheSize) {
super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
MAX_CACHE_SIZE = cacheSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_CACHE_SIZE;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (Map.Entry<K, V> entry : entrySet()) {
sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
}
return sb.toString();
}
}這樣算是比較標(biāo)準(zhǔn)的實(shí)現(xiàn)吧，實(shí)際使用中這樣寫還是有些繁瑣，更實(shí)用的方法時(shí)像下面這樣寫，省去了單獨(dú)見一個(gè)類的麻煩
final int cacheSize = 100;
Map<String, String> map = new LinkedHashMap<String, String>((int) Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
return size() > cacheSize;
}
};LRU緩存LinkedHashMap(delegation)實(shí)現(xiàn)
delegation方式實(shí)現(xiàn)更加優(yōu)雅一些，但是由于沒有實(shí)現(xiàn)Map接口，所以線程同步就需要自己搞定了
package cn.lzrabbit.structure.lru;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
/**
* Created by liuzhao on 14-5-13.
*/
public class LRUCache3<K, V> {
private final int MAX_CACHE_SIZE;
private final float DEFAULT_LOAD_FACTOR = 0.75f;
LinkedHashMap<K, V> map;
public LRUCache3(int cacheSize) {
MAX_CACHE_SIZE = cacheSize;
//根據(jù)cacheSize和加載因子計(jì)算hashmap的capactiy，+1確保當(dāng)達(dá)到cacheSize上限時(shí)不會(huì)觸發(fā)hashmap的擴(kuò)容，
int capacity = (int) Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTOR) + 1;
map = new LinkedHashMap(capacity, DEFAULT_LOAD_FACTOR, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_CACHE_SIZE;
}
};
}
public synchronized void put(K key, V value) {
map.put(key, value);
}
public synchronized V get(K key) {
return map.get(key);
}
public synchronized void remove(K key) {
map.remove(key);
}
public synchronized Set<Map.Entry<K, V>> getAll() {
return map.entrySet();
}
public synchronized int size() {
return map.size();
}
public synchronized void clear() {
map.clear();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (Map.Entry entry : map.entrySet()) {
sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
}
return sb.toString();
}
}LRU Cache的鏈表+HashMap實(shí)現(xiàn)
注：此實(shí)現(xiàn)為非線程安全，若在多線程環(huán)境下使用需要在相關(guān)方法上添加synchronized以實(shí)現(xiàn)線程安全操作
package cn.lzrabbit.structure.lru;
import java.util.HashMap;
/**
* Created by liuzhao on 14-5-12.
*/
public class LRUCache1<K, V> {
private final int MAX_CACHE_SIZE;
private Entry first;
private Entry last;
private HashMap<K, Entry<K, V>> hashMap;
public LRUCache1(int cacheSize) {
MAX_CACHE_SIZE = cacheSize;
hashMap = new HashMap<K, Entry<K, V>>();
}
public void put(K key, V value) {
Entry entry = getEntry(key);
if (entry == null) {
if (hashMap.size() >= MAX_CACHE_SIZE) {
hashMap.remove(last.key);
removeLast();
}
entry = new Entry();
entry.key = key;
}
entry.value = value;
moveToFirst(entry);
hashMap.put(key, entry);
}
public V get(K key) {
Entry<K, V> entry = getEntry(key);
if (entry == null) return null;
moveToFirst(entry);
return entry.value;
}
public void remove(K key) {
Entry entry = getEntry(key);
if (entry != null) {
if (entry.pre != null) entry.pre.next = entry.next;
if (entry.next != null) entry.next.pre = entry.pre;
if (entry == first) first = entry.next;
if (entry == last) last = entry.pre;
}
hashMap.remove(key);
}
private void moveToFirst(Entry entry) {
if (entry == first) return;
if (entry.pre != null) entry.pre.next = entry.next;
if (entry.next != null) entry.next.pre = entry.pre;
if (entry == last) last = last.pre;
if (first == null || last == null) {
first = last = entry;
return;
}
entry.next = first;
first.pre = entry;
first = entry;
entry.pre = null;
}
private void removeLast() {
if (last != null) {
last = last.pre;
if (last == null) first = null;
else last.next = null;
}
}
private Entry<K, V> getEntry(K key) {
return hashMap.get(key);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Entry entry = first;
while (entry != null) {
sb.append(String.format("%s:%s ", entry.key, entry.value));
entry = entry.next;
}
return sb.toString();
}
class Entry<K, V> {
public Entry pre;
public Entry next;
public K key;
public V value;
}
}LinkedHashMap的FIFO實(shí)現(xiàn)
FIFO是First Input First Output的縮寫，也就是常說的先入先出，默認(rèn)情況下LinkedHashMap就是按照添加順序保存，我們只需重寫下removeEldestEntry方法即可輕松實(shí)現(xiàn)一個(gè)FIFO緩存，簡(jiǎn)化版的實(shí)現(xiàn)代碼如下
final int cacheSize = 5;
LinkedHashMap<Integer, String> lru = new LinkedHashMap<Integer, String>() {
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
return size() > cacheSize;
}
};調(diào)用示例
測(cè)試代碼
package cn.lzrabbit.structure.lru;
import cn.lzrabbit.ITest;
import java.util.LinkedHashMap;
import java.util.Map;
/**
* Created by liuzhao on 14-5-15.
*/
public class LRUCacheTest {
public static void main(String[] args) throws Exception {
System.out.println("start...");
lruCache1();
lruCache2();
lruCache3();
lruCache4();
System.out.println("over...");
}
static void lruCache1() {
System.out.println();
System.out.println("===========================LRU 鏈表實(shí)現(xiàn)===========================");
LRUCache1<Integer, String> lru = new LRUCache1(5);
lru.put(1, "11");
lru.put(2, "11");
lru.put(3, "11");
lru.put(4, "11");
lru.put(5, "11");
System.out.println(lru.toString());
lru.put(6, "66");
lru.get(2);
lru.put(7, "77");
lru.get(4);
System.out.println(lru.toString());
System.out.println();
}
static <T> void lruCache2() {
System.out.println();
System.out.println("===========================LRU LinkedHashMap(inheritance)實(shí)現(xiàn)===========================");
LRUCache2<Integer, String> lru = new LRUCache2(5);
lru.put(1, "11");
lru.put(2, "11");
lru.put(3, "11");
lru.put(4, "11");
lru.put(5, "11");
System.out.println(lru.toString());
lru.put(6, "66");
lru.get(2);
lru.put(7, "77");
lru.get(4);
System.out.println(lru.toString());
System.out.println();
}
static void lruCache3() {
System.out.println();
System.out.println("===========================LRU LinkedHashMap(delegation)實(shí)現(xiàn)===========================");
LRUCache3<Integer, String> lru = new LRUCache3(5);
lru.put(1, "11");
lru.put(2, "11");
lru.put(3, "11");
lru.put(4, "11");
lru.put(5, "11");
System.out.println(lru.toString());
lru.put(6, "66");
lru.get(2);
lru.put(7, "77");
lru.get(4);
System.out.println(lru.toString());
System.out.println();
}
static void lruCache4() {
System.out.println();
System.out.println("===========================FIFO LinkedHashMap默認(rèn)實(shí)現(xiàn)===========================");
final int cacheSize = 5;
LinkedHashMap<Integer, String> lru = new LinkedHashMap<Integer, String>() {
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
return size() > cacheSize;
}
};
lru.put(1, "11");
lru.put(2, "11");
lru.put(3, "11");
lru.put(4, "11");
lru.put(5, "11");
System.out.println(lru.toString());
lru.put(6, "66");
lru.get(2);
lru.put(7, "77");
lru.get(4);
System.out.println(lru.toString());
System.out.println();
}
}運(yùn)行結(jié)果
"C:\Program Files (x86)\Java\jdk1.6.0_10\bin\java" -Didea.launcher.port=7535 "-Didea.launcher.bin.path=C:\Program Files (x86)\JetBrains\IntelliJ IDEA 13.0.2\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\charsets.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\deploy.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\javaws.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\jce.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\jsse.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\management-agent.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\plugin.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\resources.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\rt.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\dnsns.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\localedata.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\sunjce_provider.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\sunmscapi.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\sunpkcs11.jar;D:\SVN\projects\Java\Java.Algorithm\target\test-classes;D:\SVN\projects\Java\Java.Algorithm\target\classes;C:\Program Files (x86)\JetBrains\IntelliJ IDEA 13.0.2\lib\idea_rt.jar" com.intellij.rt.execution.application.AppMain Main
start...
===========================LRU 鏈表實(shí)現(xiàn)===========================
5:11 4:11 3:11 2:11 1:11
4:11 7:77 2:11 6:66 5:11
===========================LRU LinkedHashMap(inheritance)實(shí)現(xiàn)===========================
1:11 2:11 3:11 4:11 5:11
5:11 6:66 2:11 7:77 4:11
===========================LRU LinkedHashMap(delegation)實(shí)現(xiàn)===========================
1:11 2:11 3:11 4:11 5:11
5:11 6:66 2:11 7:77 4:11
===========================FIFO LinkedHashMap默認(rèn)實(shí)現(xiàn)===========================
{1=11, 2=11, 3=11, 4=11, 5=11}
{3=11, 4=11, 5=11, 6=66, 7=77}
over...
Process finished with exit code 0更多java知識(shí)請(qǐng)關(guān)注java基礎(chǔ)教程欄目。
以上是java中LRU緩存實(shí)現(xiàn)的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！
熱AI工具
Undress AI Tool
免費(fèi)脫衣服圖片
Undresser.AI Undress
人工智能驅(qū)動(dòng)的應(yīng)用程序，用于創(chuàng)建逼真的裸體照片
AI Clothes Remover
用于從照片中去除衣服的在線人工智能工具。
Clothoff.io
AI脫衣機(jī)
Video Face Swap
使用我們完全免費(fèi)的人工智能換臉工具輕松在任何視頻中換臉！
熱門文章
熱工具
記事本++7.3.1
好用且免費(fèi)的代碼編輯器
SublimeText3漢化版
中文版，非常好用
禪工作室 13.0.1
功能強(qiáng)大的PHP集成開發(fā)環(huán)境
Dreamweaver CS6
視覺化網(wǎng)頁開發(fā)工具
SublimeText3 Mac版
神級(jí)代碼編輯軟件(SublimeText3)
如何使用JDBC處理Java的交易？
Aug 02, 2025 pm 12:29 PM
要正確處理JDBC事務(wù)，必須先關(guān)閉自動(dòng)提交模式，再執(zhí)行多個(gè)操作，最后根據(jù)結(jié)果提交或回滾；1.調(diào)用conn.setAutoCommit(false)以開始事務(wù)；2.執(zhí)行多個(gè)SQL操作，如INSERT和UPDATE；3.若所有操作成功則調(diào)用conn.commit()，若發(fā)生異常則調(diào)用conn.rollback()確保數(shù)據(jù)一致性；同時(shí)應(yīng)使用try-with-resources管理資源，妥善處理異常并關(guān)閉連接，避免連接泄漏；此外建議使用連接池、設(shè)置保存點(diǎn)實(shí)現(xiàn)部分回滾，并保持事務(wù)盡可能短以提升性能。
了解Java虛擬機(jī)（JVM）內(nèi)部
Aug 01, 2025 am 06:31 AM
TheJVMenablesJava’s"writeonce,runanywhere"capabilitybyexecutingbytecodethroughfourmaincomponents:1.TheClassLoaderSubsystemloads,links,andinitializes.classfilesusingbootstrap,extension,andapplicationclassloaders,ensuringsecureandlazyclassloa
如何使用Java的日歷？
Aug 02, 2025 am 02:38 AM
使用java.time包中的類替代舊的Date和Calendar類；2.通過LocalDate、LocalDateTime和LocalTime獲取當(dāng)前日期時(shí)間；3.使用of()方法創(chuàng)建特定日期時(shí)間；4.利用plus/minus方法不可變地增減時(shí)間；5.使用ZonedDateTime和ZoneId處理時(shí)區(qū)；6.通過DateTimeFormatter格式化和解析日期字符串；7.必要時(shí)通過Instant與舊日期類型兼容；現(xiàn)代Java中日期處理應(yīng)優(yōu)先使用java.timeAPI，它提供了清晰、不可變且線
比較Java框架：Spring Boot vs Quarkus vs Micronaut
Aug 04, 2025 pm 12:48 PM
前形式攝取，quarkusandmicronautleaddueTocile timeProcessingandGraalvSupport，withquarkusoftenpernperforminglightbetterine nosserless notelless centarios.2。
垃圾收集如何在Java工作？
Aug 02, 2025 pm 01:55 PM
Java的垃圾回收（GC）是自動(dòng)管理內(nèi)存的機(jī)制，通過回收不可達(dá)對(duì)象釋放堆內(nèi)存，減少內(nèi)存泄漏風(fēng)險(xiǎn)。1.GC從根對(duì)象（如棧變量、活動(dòng)線程、靜態(tài)字段等）出發(fā)判斷對(duì)象可達(dá)性，無法到達(dá)的對(duì)象被標(biāo)記為垃圾。2.基于標(biāo)記-清除算法，標(biāo)記所有可達(dá)對(duì)象，清除未標(biāo)記對(duì)象。3.采用分代收集策略：新生代（Eden、S0、S1）頻繁執(zhí)行MinorGC；老年代執(zhí)行較少但耗時(shí)較長(zhǎng)的MajorGC；Metaspace存儲(chǔ)類元數(shù)據(jù)。4.JVM提供多種GC器：SerialGC適用于小型應(yīng)用；ParallelGC提升吞吐量；CMS降
了解網(wǎng)絡(luò)端口和防火墻
Aug 01, 2025 am 06:40 AM
NetworkPortSandFireWallsworkTogetHertoEnableCommunication whereSeringSecurity.1.NetWorkPortSareVirtualendPointSnumbered0-655 35，with-Well-with-Newonportslike80（HTTP），443（https），22（SSH）和25（smtp）sindiessingspefificservices.2.portsoperateervertcp（可靠，c
以身作則，解釋說明
Aug 02, 2025 am 06:26 AM
defer用于在函數(shù)返回前執(zhí)行指定操作，如清理資源；參數(shù)在defer時(shí)立即求值，函數(shù)按后進(jìn)先出（LIFO）順序執(zhí)行；1.多個(gè)defer按聲明逆序執(zhí)行；2.常用于文件關(guān)閉等安全清理；3.可修改命名返回值；4.即使發(fā)生panic也會(huì)執(zhí)行，適合用于recover；5.避免在循環(huán)中濫用defer，防止資源泄漏；正確使用可提升代碼安全性和可讀性。
比較Java構(gòu)建工具：Maven vs. Gradle
Aug 03, 2025 pm 01:36 PM
Gradleisthebetterchoiceformostnewprojectsduetoitssuperiorflexibility,performance,andmoderntoolingsupport.1.Gradle’sGroovy/KotlinDSLismoreconciseandexpressivethanMaven’sverboseXML.2.GradleoutperformsMaveninbuildspeedwithincrementalcompilation,buildcac
