Java實(shí)現(xiàn)LRU緩存的代碼詳解
一、LRU 緩存的基本思想
LRU 緩存是一個(gè)有限大小的緩存,每當(dāng)緩存的容量達(dá)到上限時(shí),系統(tǒng)會(huì)自動(dòng)刪除最近最少使用的緩存項(xiàng)。LRU 緩存常常用于數(shù)據(jù)存儲(chǔ)、圖形處理、操作系統(tǒng)等領(lǐng)域。
LRU 緩存的關(guān)鍵點(diǎn):
- 使用最近使用的數(shù)據(jù):緩存會(huì)保存最近訪問(wèn)過(guò)的數(shù)據(jù)。
- 淘汰最少使用的數(shù)據(jù):當(dāng)緩存空間滿時(shí),刪除最近最少使用的項(xiàng)。
- 維護(hù)訪問(wèn)順序:通常通過(guò)鏈表來(lái)維護(hù)緩存項(xiàng)的訪問(wèn)順序。
二、LRU 緩存實(shí)現(xiàn)的核心步驟
- 緩存容量限制:緩存大小固定,當(dāng)容量達(dá)到上限時(shí),需要?jiǎng)h除最少使用的緩存項(xiàng)。
- 快速的查找與刪除操作:使用
Map
數(shù)據(jù)結(jié)構(gòu)提供快速的查找和刪除功能,同時(shí)使用雙向鏈表來(lái)維護(hù)元素的訪問(wèn)順序。 - 操作順序:每次訪問(wèn)緩存時(shí),將該元素移動(dòng)到鏈表的頭部,表示它是最近使用的。超出容量時(shí),將鏈表尾部的元素刪除。
三、LRU 緩存的 Java 實(shí)現(xiàn)
我們將使用 LinkedHashMap
來(lái)實(shí)現(xiàn) LRU 緩存。LinkedHashMap
保持了元素的插入順序,可以通過(guò)設(shè)置其 accessOrder
為 true
來(lái)確保按訪問(wèn)順序維護(hù)元素。
四、實(shí)現(xiàn)代碼
import java.util.*; public class LRUCache<K, V> { private final int capacity; private final Map<K, V> cache; // 構(gòu)造函數(shù),初始化容量并創(chuàng)建一個(gè)LinkedHashMap public LRUCache(int capacity) { this.capacity = capacity; // LinkedHashMap 允許通過(guò)訪問(wèn)順序來(lái)維護(hù)插入順序 this.cache = new LinkedHashMap<>(capacity, 0.75f, true); } // 獲取緩存中的值 public V get(K key) { if (!cache.containsKey(key)) { return null; // 如果緩存中沒(méi)有該項(xiàng),返回null } return cache.get(key); // 如果緩存中有該項(xiàng),返回其值,并將其移動(dòng)到末尾(表示最近使用) } // 將元素添加到緩存中 public void put(K key, V value) { if (cache.size() >= capacity) { // 如果緩存已滿,移除最少使用的元素(即鏈表頭部的元素) Iterator<Map.Entry<K, V>> iterator = cache.entrySet().iterator(); if (iterator.hasNext()) { iterator.next(); iterator.remove(); } } cache.put(key, value); // 將新的元素放入緩存 } // 打印緩存中的內(nèi)容 public void printCache() { System.out.println(cache); } public static void main(String[] args) { LRUCache<Integer, String> lruCache = new LRUCache<>(3); // 向緩存添加元素 lruCache.put(1, "A"); lruCache.put(2, "B"); lruCache.put(3, "C"); // 打印緩存內(nèi)容 lruCache.printCache(); // 輸出: {1=A, 2=B, 3=C} // 訪問(wèn)一些緩存項(xiàng) lruCache.get(1); // 訪問(wèn)了 1 lruCache.put(4, "D"); // 插入新的元素,容量已滿 // 打印緩存內(nèi)容 lruCache.printCache(); // 輸出: {3=C, 1=A, 4=D} (2 被移除,最少使用) // 繼續(xù)訪問(wèn)一些緩存項(xiàng) lruCache.get(3); // 訪問(wèn)了 3 lruCache.put(5, "E"); // 插入新的元素 // 打印緩存內(nèi)容 lruCache.printCache(); // 輸出: {1=A, 3=C, 5=E} (4 被移除) } }
五、代碼解讀
LRUCache
類:- 使用
LinkedHashMap
來(lái)保存緩存數(shù)據(jù)。其構(gòu)造函數(shù)使用true
作為第三個(gè)參數(shù)accessOrder
,以確保緩存按訪問(wèn)順序排列。 get
方法用于獲取緩存中的數(shù)據(jù)。如果數(shù)據(jù)存在,它會(huì)自動(dòng)將該數(shù)據(jù)移動(dòng)到最近使用的位置(鏈表的末尾)。put
方法用于將數(shù)據(jù)添加到緩存中。如果緩存已滿,則刪除最少使用的數(shù)據(jù)(鏈表頭部元素)。
- 使用
緩存容量控制:
- 當(dāng)緩存的元素?cái)?shù)量達(dá)到指定容量時(shí),
put
方法會(huì)通過(guò)迭代器移除鏈表頭部的元素,保證緩存不會(huì)超出最大容量。
- 當(dāng)緩存的元素?cái)?shù)量達(dá)到指定容量時(shí),
printCache
方法:- 用于打印當(dāng)前緩存的內(nèi)容,幫助調(diào)試和查看緩存狀態(tài)。
main
方法:- 通過(guò)示例演示如何使用 LRU 緩存。
- 向緩存添加了多個(gè)元素,然后訪問(wèn)了一些元素并查看緩存中剩余的內(nèi)容。
六、LRU 緩存的工作原理
- 緩存初始化:當(dāng)初始化
LRUCache
時(shí),指定緩存的最大容量。 - 緩存添加:通過(guò)
put
方法向緩存添加元素。如果緩存已滿,會(huì)刪除最少使用的元素。 - 緩存訪問(wèn):通過(guò)
get
方法訪問(wèn)緩存中的元素,訪問(wèn)后元素會(huì)被標(biāo)記為最近使用。 - LRU 刪除機(jī)制:當(dāng)容量達(dá)到上限時(shí),刪除鏈表頭部的元素,即最近最少使用的元素。
七、總結(jié)
- LRU 緩存 是一種常見(jiàn)的緩存替換策略,用于處理有限大小緩存中的數(shù)據(jù)。它通過(guò)追蹤元素的使用順序來(lái)確保刪除最少使用的元素。
- 本文介紹了如何使用
LinkedHashMap
在 Java 中實(shí)現(xiàn) LRU 緩存。通過(guò)合理利用LinkedHashMap
的順序特性,能夠在訪問(wèn)緩存時(shí)保持元素的順序,確保我們能夠在緩存滿時(shí)刪除最少使用的元素。
這個(gè)實(shí)現(xiàn)是一個(gè)簡(jiǎn)化版本,適合用于小型緩存場(chǎng)景,若需要更復(fù)雜的緩存控制(如并發(fā)支持等),可以進(jìn)一步優(yōu)化和擴(kuò)展。
以上就是Java實(shí)現(xiàn)LRU緩存的代碼詳解的詳細(xì)內(nèi)容,更多關(guān)于Java LRU緩存的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
教你怎么用java實(shí)現(xiàn)客戶端與服務(wù)器一問(wèn)一答
這篇文章主要介紹了教你怎么用java實(shí)現(xiàn)客戶端與服務(wù)器一問(wèn)一答,文中有非常詳細(xì)的代碼示例,對(duì)正在學(xué)習(xí)java的小伙伴們有非常好的幫助,需要的朋友可以參考下2021-04-04Springboot2.0自適應(yīng)效果錯(cuò)誤響應(yīng)過(guò)程解析
這篇文章主要介紹了Springboot2.0自適應(yīng)效果錯(cuò)誤響應(yīng)過(guò)程解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-11-11詳解Mybatis多參數(shù)傳遞入?yún)⑺姆N處理方式
這篇文章主要介紹了詳解Mybatis多參數(shù)傳遞入?yún)⑺姆N處理方式,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04Invalid bound statement(not found):錯(cuò)誤的解決方案
本文介紹了在開(kāi)發(fā)Java SpringBoot應(yīng)用程序時(shí)出現(xiàn)的"Invalidboundstatement(notfound)"錯(cuò)誤的原因及解決方法,該錯(cuò)誤通常與MyBatis或其他持久化框架相關(guān),可能是由于配置錯(cuò)誤、拼寫(xiě)錯(cuò)誤或其他問(wèn)題引起的,解決方法包括檢查SQL映射文件2025-01-01Java Math類的三個(gè)方法ceil,floor,round用法
這篇文章主要介紹了Java Math類的三個(gè)方法ceil,floor,round用法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-07-07java開(kāi)發(fā)MyBatis中常用plus實(shí)體類注解符詳解
這篇文章主要為大家介紹了java開(kāi)發(fā)MyBatis常用的plus實(shí)體類注解符示例應(yīng)用詳解有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步2021-10-10