Java之理解Redis回收算法LRU案例講解
如何通俗易懂的理解LRU算法?
1.LRU是什么?
LRU全稱Least Recently Used,也就是最近最少使用的意思,是一種內(nèi)存管理算法,最早應(yīng)用于Linux操作系統(tǒng)。
LRU算法基于一種假設(shè):長期不被使用的數(shù)據(jù),在未來被用到的幾率也不大。因此,當(dāng)數(shù)據(jù)所占內(nèi)存達(dá)到一定閾值時(shí),我們要移除掉最近最少被使用的數(shù)據(jù)。
LRU算法應(yīng)用:可以在內(nèi)存不夠時(shí),從哈希表移除一部分很少訪問的用戶。
LRU是什么?按照英文的直接原義就是Least Recently Used,最近最久未使用法,它是按照一個(gè)非常著名的計(jì)算機(jī)操作系統(tǒng)基礎(chǔ)理論得來的:最近使用的頁面數(shù)據(jù)會(huì)在未來一段時(shí)期內(nèi)仍然被使用,已經(jīng)很久沒有使用的頁面很有可能在未來較長的一段時(shí)間內(nèi)仍然不會(huì)被使用?;谶@個(gè)思想,會(huì)存在一種緩存淘汰機(jī)制,每次從內(nèi)存中找到最久未使用的數(shù)據(jù)然后置換出來,從而存入新的數(shù)據(jù)!它的主要衡量指標(biāo)是使用的時(shí)間,附加指標(biāo)是使用的次數(shù)。在計(jì)算機(jī)中大量使用了這個(gè)機(jī)制,它的合理性在于優(yōu)先篩選熱點(diǎn)數(shù)據(jù),所謂熱點(diǎn)數(shù)據(jù),就是最近最多使用的數(shù)據(jù)!因?yàn)椋肔RU我們可以解決很多實(shí)際開發(fā)中的問題,并且很符合業(yè)務(wù)場(chǎng)景。
2.LRU的需求
首先考慮這樣的一個(gè)業(yè)務(wù)場(chǎng)景,小王在A公司上班,有一天產(chǎn)品提出了一個(gè)需求:“咱們系統(tǒng)的用戶啊,每天活躍的就那么多,有太多的僵尸用戶,根本不登錄,你能不能考慮做一個(gè)篩選機(jī)制把這些用戶刨出去,并且給活躍的用戶做一個(gè)排名,我們可以設(shè)計(jì)出一些獎(jiǎng)勵(lì)活動(dòng),提升咱們的用戶粘性,咱們只需要關(guān)注那些活躍的用戶就行了“”。小王連忙點(diǎn)頭,說可以啊,然而心里犯起嘀咕來了:這簡(jiǎn)單,按照常規(guī)思路,給用戶添加一個(gè)最近活躍時(shí)間長度和登錄次數(shù),然后按照這兩個(gè)數(shù)據(jù)計(jì)算他們的活躍度,最后直接排序就行了。嘿嘿,簡(jiǎn)直完美!不過!用戶表字段已經(jīng)很多了,又要加兩個(gè)字段,然后還得遍歷所有的數(shù)據(jù)排序?這樣查詢效率是不是會(huì)受影響???
3.LRU的實(shí)現(xiàn)方式
實(shí)現(xiàn) LRUCache 類:
- LRUCache(int capacity) 以正整數(shù)作為容量 capacity 初始化 LRU 緩存;
- int get(int key) 如果關(guān)鍵字 key 存在于緩存中,則返回關(guān)鍵字的值,否則返回 -1 。
- void put(int key, int value) 如果關(guān)鍵字已經(jīng)存在,則變更其數(shù)據(jù)值;如果關(guān)鍵字不存在,則插入該組「關(guān)鍵字-值」。當(dāng)緩存容量達(dá)到上限時(shí),它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值,從而為新的數(shù)據(jù)值留出空間。
3.1 直接繼承LinkedHashMap來實(shí)現(xiàn)
public class Code_LRU { class LRUCache extends LinkedHashMap<Integer,Integer>{ private int capacity; public LRUCache(int capacity) { super(capacity,0.75F,true); this.capacity = capacity; } public int get(int key) { return super.getOrDefault(key,-1); } public void put(int key,int value) { super.put(key, value); } // 重寫淘汰策略 protected boolean removeEldestEntry(Map.Entry<Integer, Integer> edlest) { return size()>capacity; } } }
3.2 用雙向鏈表+hashMap來實(shí)現(xiàn)
// 解題思路:雙向鏈表+hashmap來實(shí)現(xiàn) class LRUCache_2{ // 雙向鏈表 class DLinkedNode{ int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() { } public DLinkedNode(int key,int value) { this.key = key; this.value = value; } } // hashmap private HashMap<Integer,DLinkedNode> cache = new HashMap<>(); // 定義私有變量 private int size; private int capacity; private DLinkedNode head,tail; public LRUCache_2(int capacity) { this.size = 0; this.capacity = capacity; // 生成偽頭部和偽尾部結(jié)點(diǎn) head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.prev = head; } //獲得值 public int get(int key) { DLinkedNode node = cache.get(key); if(node==null) { return -1; }else { // 如果key存在,哈希表定位 結(jié)點(diǎn)移動(dòng)到頭部 moveToHead(node); return node.value; } } // 放入值的操作 public void put(int key,int value) { DLinkedNode node = cache.get(key); // 如果key不存在 if(node==null) { // 新創(chuàng)建一個(gè)結(jié)點(diǎn) DLinkedNode newNode = new DLinkedNode(key,value); // 添加 cache.put(key,newNode); // 添加到頭部 addToHead(newNode); ++size; // 判斷容量 if(size>capacity) { // 稱號(hào)出容量 DLinkedNode tail = removeTail(); // 刪除hash表中對(duì)應(yīng)的項(xiàng) cache.remove(tail.key); --size; } }else { node.value = value; // 移動(dòng) moveToHead(node); } } // 添加結(jié)點(diǎn)的操作 private void addToHead(DLinkedNode node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } // 刪除結(jié)點(diǎn) private void removeNode(DLinkedNode node) { node.prev.next = node.next; node.next.prev = node.prev; } // 移動(dòng)到頭結(jié)點(diǎn) 刪結(jié)點(diǎn) 填充結(jié)點(diǎn) private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } // 刪除尾部結(jié)點(diǎn) private DLinkedNode removeTail() { DLinkedNode res = tail.prev; removeNode(res); return res; } }
到此這篇關(guān)于Java之理解Redis回收算法LRU案例講解的文章就介紹到這了,更多相關(guān)Java之理解Redis回收算法LRU內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java多線程Future松獲取異步任務(wù)結(jié)果輕松實(shí)現(xiàn)
這篇文章主要為大家介紹了Java多線程Future松獲取異步任務(wù)結(jié)果輕松實(shí)現(xiàn)方法,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-04-04java集合Collection實(shí)現(xiàn)類解析ArrayList?LinkedList及Vector
這篇文章主要為大家介紹了java集合Collection實(shí)現(xiàn)類解析ArrayList?LinkedList及Vector,有需要的朋友可以借鑒參考下,希望能夠有所幫助2022-03-03Java動(dòng)態(tài)代理靜態(tài)代理實(shí)例分析
這篇文章主要介紹了Java動(dòng)態(tài)代理靜態(tài)代理實(shí)例分析,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-03-03Java數(shù)組常見應(yīng)用詳解【創(chuàng)建、遍歷、排序、查找】
這篇文章主要介紹了Java數(shù)組常見應(yīng)用,結(jié)合實(shí)例形式詳細(xì)分析了java數(shù)組的基本定義、創(chuàng)建、遍歷、排序、查找等相關(guān)操作技巧與使用注意事項(xiàng),需要的朋友可以參考下2020-02-02Java生成范圍內(nèi)隨機(jī)整數(shù)的三種方法
在Java中生成隨機(jī)數(shù)的場(chǎng)景有很多,下面這篇文章主要給大家介紹了關(guān)于Java生成范圍內(nèi)隨機(jī)整數(shù)的三種方法,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-07-07Spring Boot 集成 Kafkad的實(shí)現(xiàn)示例
這篇文章主要介紹了Spring Boot 集成 Kafkad的示例,幫助大家更好的理解和學(xué)習(xí)使用Spring Boot框架,感興趣的朋友可以了解下2021-04-04Spring Cloud 優(yōu)雅下線以及灰度發(fā)布實(shí)現(xiàn)
這篇文章主要介紹了Spring Cloud 優(yōu)雅下線以及灰度發(fā)布實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11