java基礎(chǔ)--自己動(dòng)手實(shí)現(xiàn)一個(gè)LRU
更新時(shí)間：2021年08月20日 16:22:26 作者：chenssy
這篇文章主要介紹了運(yùn)用方案如何實(shí)現(xiàn)LUR，文章中通過(guò)代碼講解的非常詳細(xì)，對(duì)大家的工作或?qū)W習(xí)有一定的參考價(jià)值，感興趣的朋友可以參考一下
LRU，即 Least Recently Use ，直譯為 “最近最少使用”。它是根據(jù)數(shù)據(jù)的歷史訪問(wèn)記錄來(lái)進(jìn)行數(shù)據(jù)淘汰的，淘汰掉最先訪問(wèn)的數(shù)據(jù)，其核心思想是 如果數(shù)據(jù)最近被訪問(wèn)過(guò)，那么將來(lái)被訪問(wèn)的幾率也會(huì)更加高。
要實(shí)現(xiàn) LRU，需要做到兩點(diǎn)：
- 查詢出最近最晚使用的項(xiàng)
- 給最近使用的項(xiàng)做一個(gè)標(biāo)記
實(shí)現(xiàn)的方案有多種，這里小編主要介紹兩種：
- LinkedHashMap
- 雙向鏈表 + HashMap
LinkedHashMap 實(shí)現(xiàn)
利用 LinkedHashMap 的原因就在于 LinkedHashMap 是有序的，默認(rèn)情況下是按照元素的添加順序存儲(chǔ)的，也可以調(diào)整為根據(jù)訪問(wèn)順序來(lái)調(diào)整內(nèi)部順序（設(shè)置參數(shù) accessOrder 進(jìn)行調(diào)整），即最近讀取的數(shù)據(jù)放在最前面，我們就是利用 LinkedHashMap 的這個(gè)特性來(lái)實(shí)現(xiàn) LRU。先來(lái)一個(gè)簡(jiǎn)單的例子吧：
public static void main(String[] args){
Map<String,String> map = new LinkedHashMap(10,0.75f,true);
map.put("1","a");
map.put("2","b");
map.put("3","c");
map.put("4","d");
System.out.println("原始順序?yàn)椋?);
for(Iterator<Map.Entry<String,String>> it = map.entrySet().iterator();it.hasNext();){
System.out.print(it.next().getKey() + " ");
}
System.out.println();
map.get("2");
System.out.println("訪問(wèn) 4 之后的順序?yàn)椋?);
for(Iterator<Map.Entry<String,String>> it = map.entrySet().iterator();it.hasNext();){
System.out.print(it.next().getKey() + " ");
}
}
運(yùn)行結(jié)果：
原始順序?yàn)椋? 1 2 3 4 訪問(wèn) 4 之后的順序?yàn)椋? 1 3 4 2
更多關(guān)于 LinkedHashMap，請(qǐng)看這篇文章：LinkedHashMap
LinkedHashMap 實(shí)現(xiàn) LRU 有兩種方式，一種是繼承 LinkedHashMap，一種是利用組合的方式，下面分別演示這兩種情況。
繼承 LinkedHashMap
采用繼承的方式實(shí)現(xiàn)起來(lái)是非常簡(jiǎn)單的，因?yàn)?LinkedHashMap 本身就已經(jīng)具備了 LRU 的特性，我們只需要實(shí)現(xiàn)一點(diǎn)：當(dāng)容器中元素個(gè)數(shù)超過(guò)我們?cè)O(shè)定的容量后，刪除第一個(gè)元素即可。同時(shí)由于 LinkedHashMap 本身不具備線程安全，我們需要確保他線程安全，這個(gè)也很簡(jiǎn)單，重寫 LinkedHashMap 的 get() 和 put() 方法即可，或者使用 Collections.synchronizedMap() 方法也可以。實(shí)現(xiàn)如下：
public class LRUCacheLinkedHashMap<K,V> extends LinkedHashMap<K,V> {
/**
* 定一緩存容量
*/
private int capacity;
LRUCacheLinkedHashMap(int capacity){
// AccessOrder = true
super(capacity,0.75f,true);
this.capacity = capacity;
}
/**
* 實(shí)現(xiàn)LRU的關(guān)鍵方法，如果 map 里面的元素個(gè)數(shù)大于了緩存最大容量，則刪除鏈表的頂端元素
*
* @param eldest
* @return
*/
@Override
public boolean removeEldestEntry(Map.Entry<K, V> eldest){
System.out.println(eldest.getKey() + "=" + eldest.getValue());
return size()>capacity;
}
@Override
public synchronized V get(Object key) {
return super.get(key);
}
@Override
public synchronized V put(K key, V value) {
return super.put(key, value);
}
}
驗(yàn)證
public static void main(String[] args){
LRUCacheLinkedHashMap cache = new LRUCacheLinkedHashMap(5);
cache.put("1","a");
cache.put("2","b");
cache.put("3","c");
cache.put("4","d");
cache.put("5","e");
System.out.println("插入 5 個(gè)元素后的順序");
printlnCache(cache);
// 插入第 6 個(gè)元素
cache.put("6","e");
System.out.println("插入第 6 個(gè)元素后的順序");
printlnCache(cache);
// 訪問(wèn) 第 3 個(gè)元素
cache.get("3");
System.out.println("訪問(wèn)元素 3 后的順序");
printlnCache(cache);
}
private static void printlnCache(LRUCacheLinkedHashMap cacheMap){
for(Iterator<Map.Entry<String,String>> it = cacheMap.entrySet().iterator(); it.hasNext();){
System.out.print(it.next().getKey() + " ");
}
System.out.println();
}
運(yùn)行結(jié)果：
插入 5 個(gè)元素后的順序 1 2 3 4 5 插入第 6 個(gè)元素后的順序 2 3 4 5 6 訪問(wèn)元素 3 后的順序 2 4 5 6 3
運(yùn)行結(jié)果完全符合我們的預(yù)期
組合 LinkedHashMap
使用組合的方式可能會(huì)更加優(yōu)雅些，但是由于沒(méi)有實(shí)現(xiàn) Map 接口，所以就不能使用 Collections.synchronizedMap() 方式來(lái)保證線程安全性了，所以需要在每個(gè)方法處增加 synchronized 來(lái)確保線程安全。實(shí)現(xiàn)方式如下：
public class LRUCache<K,V> {
private int capacity;
private Map<K,V> cacheMap;
public LRUCache(int capacity){
this.capacity = capacity;
cacheMap = new LinkedHashMap<>(capacity,0.75f,true);
}
public synchronized void put(K k,V v){
cacheMap.put(k,v);
// 移除第一個(gè)元素
if(cacheMap.size() > capacity){
K first = this.keyIterator().next();
cacheMap.remove(first);
}
}
public synchronized V get(K k){
return cacheMap.get(k);
}
public Iterator<K> keyIterator(){
return cacheMap.keySet().iterator();
}
}
驗(yàn)證：
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(5);
lruCache.put("1","a");
lruCache.put("2","b");
lruCache.put("3","c");
lruCache.put("4","d");
lruCache.put("5","e");
System.out.println("插入 5 個(gè)元素后的順序");
println(lruCache);
// 插入第 6 個(gè)元素
lruCache.put("6","e");
System.out.println("插入 第 6 個(gè)元素后的順序");
println(lruCache);
// 訪問(wèn) 第 3 個(gè)元素
lruCache.get("3");
System.out.println("訪問(wèn)元素 3 后的順序");
println(lruCache);
}
private static void println(LRUCache lruCache){
for(Iterator it = lruCache.keyIterator(); it.hasNext();){
System.out.print(it.next() + " ");
}
System.out.println();
}
運(yùn)行結(jié)果如下：
插入 5 個(gè)元素后的順序 1 2 3 4 5 插入 第 6 個(gè)元素后的順序 2 3 4 5 6 訪問(wèn)元素 3 后的順序 2 4 5 6 3
組合的方式也顯得非常簡(jiǎn)單，有兩點(diǎn)需要注意：
- 保證每個(gè)方法的線程安全
- put 時(shí)，需要查看當(dāng)前容量是否超過(guò)設(shè)置的容量，超過(guò)則需要?jiǎng)h除第一個(gè)元素。當(dāng)然小編這種是實(shí)現(xiàn)方式不是很優(yōu)雅，這么做知識(shí)為了能夠更加好闡述 LRU 的實(shí)現(xiàn)。更好的方案是在構(gòu)造 LinkedHashMap 時(shí)，重寫
removeEldestEntry(),如下：
cacheMap = new LinkedHashMap<K,V>(capacity,0.75f,true){
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size()>capacity;
}
};
鏈表 + HashMap 實(shí)現(xiàn)
我們想想，在不利用現(xiàn)存數(shù)據(jù)結(jié)構(gòu)的條件（如 LinkedHashMap）如何實(shí)現(xiàn)一個(gè) LRU 呢？緩存部分容易實(shí)現(xiàn)，我們都知道利用 HashMap 即可，但是如何實(shí)現(xiàn)緩存容量不足時(shí)丟棄最不常用的數(shù)據(jù)的功能？
- 利用時(shí)間戳。每一個(gè)訪問(wèn)，增加的元素我們都給其更新一個(gè)時(shí)間戳，在 put 的時(shí)候，檢查，刪除時(shí)間戳最小的就可以了。這種方法可以實(shí)現(xiàn)，但是代價(jià)較高，就是我們需要遍歷整個(gè)數(shù)據(jù)，得到最小的時(shí)間戳。
- 我們可以換位思考，我們其實(shí)不需要關(guān)注每個(gè)節(jié)點(diǎn)的增加或者遍歷時(shí)間，我們只需要知道那個(gè)節(jié)點(diǎn)是最先訪問(wèn)就可以了，所以我們可以利用鏈表記錄訪問(wèn)記錄，有新數(shù)據(jù)加入時(shí)放在鏈表的 head 節(jié)點(diǎn)，每次訪問(wèn)也將該數(shù)據(jù)放在 head 節(jié)點(diǎn)，那么鏈表的 tail 一定是最早訪問(wèn)的節(jié)點(diǎn)，所以每次當(dāng)容量不足的時(shí)候刪除 tail 節(jié)點(diǎn)數(shù)據(jù)并將它的前驅(qū)節(jié)點(diǎn)設(shè)置為 tail 就可以了。注意，這個(gè)鏈表是一個(gè)雙向鏈表。代碼如下：
public class LinkedLRUCache<K,V> {
private int capacity;
private Map<K,LRUNode> map;
private LRUNode head;
private LRUNode tail;
LinkedLRUCache(int capacity){
this.capacity = capacity;
this.map = new HashMap<>();
}
public synchronized void put(K k,V v){
LRUNode node = map.get(k);
// 存在該 key，將節(jié)點(diǎn)的設(shè)置為 head
if(node != null){
node.value = v;
remove(node,false);
}else{
/**
* 該節(jié)點(diǎn)不存在
* 1、將該節(jié)點(diǎn)加入緩存
* 2、設(shè)置該節(jié)點(diǎn)為 head
* 3、判斷是否超出容量
*/
node = new LRUNode(k,v);
if(map.size() >= capacity){
//刪除 tail 節(jié)點(diǎn)
remove(tail,true);
}
map.put(k,node);
setHead(node);
}
// 設(shè)置當(dāng)前節(jié)點(diǎn)為首節(jié)點(diǎn)
setHead(node);
}
public Object get(String key) {
LRUNode node = map.get(key);
if (node != null) {
// 將剛操作的元素放到head
remove(node, false);
setHead(node);
return node.value;
}
return null;
}
/**
* 設(shè)置頭結(jié)點(diǎn)
*
* @param node
*/
private void setHead(LRUNode node) {
if(head != null){
node.next = head;
head.prev = node;
}
head = node;
if(tail == null){
tail = node;
}
}
/**
* 從鏈表中刪除此Node
*
* @param node
* @param flag 為 true 就刪除該節(jié)點(diǎn)的 key
*/
private void remove(LRUNode node,boolean flag) {
if (node.prev != null) {
node.prev.next = node.next;
} else {
head = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
} else {
tail = node.prev;
}
node.next = null;
node.prev = null;
if (flag) {
map.remove(node.key);
}
}
private Iterator iterator(){
return map.keySet().iterator();
}
private class LRUNode<K,V> {
/**
* cache 的 key
*/
private K key;
/**
* cache 的 value
*/
private V value;
private LRUNode next;
private LRUNode prev;
LRUNode(K key, V value) {
this.key = key;
this.value = value;
}
}
}
驗(yàn)證
public static void main(String[] args){
LRUCache lruCache = new LRUCache(5);
lruCache.put("1","a");
lruCache.put("2","b");
lruCache.put("3","c");
lruCache.put("4","d");
lruCache.put("5","e");
System.out.println("插入 5 個(gè)元素");
println(lruCache);
System.out.println("插入 3 元素");
lruCache.put("3","c");
println(lruCache);
System.out.println("插入第 6 個(gè)元素");
lruCache.put("6","f");
println(lruCache);
System.out.println("訪問(wèn) 4 元素");
lruCache.get("4");
println(lruCache);
}
private static void println(LRUCache lruCache){
Iterator iterator = lruCache.keyIterator();
while (iterator.hasNext()){
System.out.print(iterator.next() + " ");
}
System.out.println();
}
執(zhí)行結(jié)果：
插入 5 個(gè)元素 1 2 3 4 5 插入 3 元素 1 2 4 5 3 插入第 6 個(gè)元素 2 4 5 3 6 訪問(wèn) 4 元素 2 5 3 6 4
到此這篇關(guān)于java基礎(chǔ)--自己動(dòng)手實(shí)現(xiàn)一個(gè)LRU的文章就介紹到這了,更多相關(guān)java LRU內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
一文學(xué)會(huì)處理SpringBoot統(tǒng)一返回格式
這篇文章主要介紹了一文學(xué)會(huì)處理SpringBoot統(tǒng)一返回格式，文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-08-08
下面小編就為大家?guī)?lái)一篇淺談hibernate之映射文件VS映射注解。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-07-07
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)貪吃蛇小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-07-07
這篇文章主要介紹了Java的面相對(duì)象編程思想,包括類對(duì)象方法和封裝繼承多態(tài)等各個(gè)方面的OOP基本要素,非常推薦,需要的朋友可以參考下，希望可以對(duì)你有所幫助2021-07-07
這篇文章主要介紹了Java 對(duì)象引用和對(duì)象本身的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)Java，感興趣的朋友可以了解下2020-08-08
Java基礎(chǔ)將Bean屬性值放入Map中的實(shí)例
這篇文章主要介紹了Java基礎(chǔ)將Bean屬性值放入Map中的實(shí)例的相關(guān)資料,需要的朋友可以參考下2017-07-07
java中HashMap.values()轉(zhuǎn)為ArrayList()問(wèn)題
這篇文章主要介紹了java中HashMap.values()轉(zhuǎn)為ArrayList()問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-03-03
Java+Swing實(shí)現(xiàn)五子棋游戲的示例代碼
本文將通過(guò)Java語(yǔ)言實(shí)現(xiàn)經(jīng)典游戲—五子棋游戲，文中采用了Swing制作游戲界面，具有開(kāi)始游戲，悔棋，認(rèn)輸，退出等功能。感興趣的可以跟隨小編一起動(dòng)手試一試2022-02-02
這篇文章主要介紹了Java編程中正則表達(dá)式的用法總結(jié),正則表達(dá)式是一種強(qiáng)大的字符串處理工具,Java對(duì)正則表達(dá)式的支持還是很不錯(cuò)的,我們先來(lái)整理一下正則表達(dá)式的一些基礎(chǔ)知識(shí):2016-05-05
mybatis Map查詢結(jié)果下劃線轉(zhuǎn)駝峰的實(shí)例
這篇文章主要介紹了mybatis Map查詢結(jié)果下劃線轉(zhuǎn)駝峰的實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-09-09