基于LinkedHashMap實(shí)現(xiàn)LRU緩存
概述
LinkedHashMap是Java集合中一個(gè)常用的容器,它繼承了HashMap, 是一個(gè)有序的Hash表。那么該如何基于LinkedHashMap實(shí)現(xiàn)一個(gè)LRU緩存呢?這也是面試經(jīng)常被問到的題目,主要是考察你對(duì)Java集合容器的了解程度以及LinkedHashMap的實(shí)現(xiàn)原理。
分析
什么是LRU?
LRU(Least Recently Used)指的是最近最少使用,是一種緩存淘汰算法,淘汰掉那個(gè)最少使用的的數(shù)據(jù)。
- LinkedHashMap是有序的,它默認(rèn)通過雙向鏈表維護(hù)元素的插入順序,同時(shí),通過構(gòu)造函數(shù)設(shè)置accessOrder屬性為true的情況,維護(hù)元素的訪問順序,這里的訪問包括插入、修改、查詢等元素,每次操作都會(huì)記錄順序,所以LRU緩存其實(shí)是包括訪問的,所以我們需要通過構(gòu)造函數(shù)設(shè)置LinkedHashMap設(shè)置accessOrder為true。
- 已經(jīng)解決了順序的問題,也就是最近訪問的會(huì)在雙向鏈表的尾部,最老的數(shù)據(jù)會(huì)在頭部。那么如何刪除頭部的元素呢?其實(shí)LinkedHashMap也提供了一個(gè)回調(diào)函數(shù)removeEldestEntry,它也會(huì)在添加元素的時(shí)候調(diào)用, 默認(rèn)返回false,我們可以通過重寫這個(gè)方法的邏輯,如果LinkedHashMap大于緩存指定數(shù)量,就進(jìn)行淘汰。
LRU緩存實(shí)現(xiàn)
場(chǎng)景:我們需要設(shè)計(jì)一個(gè)緩存最多只能存儲(chǔ)10個(gè)元素,當(dāng)元素個(gè)數(shù)超過10的時(shí)候,刪除(淘汰)那些最近最少使用的數(shù)據(jù),僅保存熱點(diǎn)數(shù)據(jù)。
public class LRUCache<K, V> extends LinkedHashMap<K, V> { /** * 緩存允許的最大容量 */ private final int maxSize; public LRUCache(int initialCapacity, int maxSize) { // accessOrder必須為true super(initialCapacity, 0.75f, true); this.maxSize = maxSize; } // 重寫 @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { // 當(dāng)鍵值對(duì)個(gè)數(shù)超過最大容量時(shí),返回true,觸發(fā)刪除操作 return size() > maxSize; } public static void main(String[] args) { LRUCache<String, String> cache = new LRUCache<>(5, 5); cache.put("1", "1"); cache.put("2", "2"); cache.put("3", "3"); cache.put("4", "4"); // 做一次查詢 cache.get("1"); cache.put("5", "5"); cache.put("6", "6"); cache.put("7", "7"); System.out.println(cache); } }
運(yùn)行結(jié)果:
{4=4, 1=1, 5=5, 6=6, 7=7}
因?yàn)樽隽艘淮?code>cache.get("1"),相當(dāng)于操作了1這個(gè)元素,變"新"了,所以只能淘汰3, 4。
總結(jié)
通過本文想必大家對(duì)LinkedHashMap有了更深的了解,可以用它來實(shí)現(xiàn)一個(gè)LRU緩存,實(shí)際上,通過LinkedHashMap實(shí)現(xiàn)LRU還是挺常見的,比如logback框架的LRUMessageCache。
到此這篇關(guān)于基于LinkedHashMap實(shí)現(xiàn)LRU緩存的文章就介紹到這了,更多相關(guān)LinkedHashMap實(shí)現(xiàn)LRU緩存內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Spring Boot啟動(dòng)過程(五)之Springboot內(nèi)嵌Tomcat對(duì)象的start教程詳解
這篇文章主要介紹了Spring Boot啟動(dòng)過程(五)之Springboot內(nèi)嵌Tomcat對(duì)象的start的相關(guān)資料,需要的朋友可以參考下2017-04-04使用springMVC通過Filter實(shí)現(xiàn)防止xss注入
這篇文章主要介紹了使用springMVC通過Filter實(shí)現(xiàn)防止xss注入的操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-07-07深入了解Java核心類庫--Date,Calendar,DateFormat類
這篇文章主要為大家詳細(xì)介紹了javaDate,Calendar,DateFormat類定義與使用的相關(guān)資料,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能給你帶來幫助2021-07-07java中Memcached的使用實(shí)例(包括與Spring整合)
這篇文章主要介紹了java中Memcached的使用實(shí)例(包括與Spring整合),具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-07-07java實(shí)現(xiàn)字符串和數(shù)字轉(zhuǎn)換工具
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)字符串和數(shù)字轉(zhuǎn)換工具,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-04-04idea使用spring Initializr 快速搭建springboot項(xiàng)目遇到的坑
這篇文章主要介紹了idea使用spring Initializr 快速搭建springboot項(xiàng)目遇到的坑,本文通過圖文并茂的形式給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-11-11