摘要:劍指緩存實(shí)現(xiàn)聲明文章均為本人技術(shù)筆記,轉(zhuǎn)載請(qǐng)注明出處解題思路緩存兩種功能獲取的對(duì)應(yīng),不存在返回版本版本設(shè)置緩存已滿,刪除最近最久未被使用的節(jié)點(diǎn),添加新節(jié)點(diǎn)進(jìn)緩存緩存未滿,節(jié)點(diǎn)存在,修改節(jié)點(diǎn)不存在,添加新節(jié)點(diǎn)進(jìn)緩存解題思路由于緩存插入和刪除
劍指offer/LeetCode146/LintCode134_LRU緩存實(shí)現(xiàn) 聲明
文章均為本人技術(shù)筆記,轉(zhuǎn)載請(qǐng)注明出處
[1] https://segmentfault.com/u/yzwall
[2] blog.csdn.net/j_dark/
get(key):獲取key的對(duì)應(yīng)value,不存在返回-1
set(key, value)(lintcode版本)/put(key, value)(leetcode版本):設(shè)置
緩存已滿,刪除最近最久未被使用的節(jié)點(diǎn),添加新節(jié)點(diǎn)進(jìn)緩存
緩存未滿,
節(jié)點(diǎn)存在,修改value;
節(jié)點(diǎn)不存在,添加新節(jié)點(diǎn)進(jìn)緩存;
解題思路由于LRU緩存插入和刪除操作頻繁,使用雙向鏈表維護(hù)緩存節(jié)點(diǎn),
“新節(jié)點(diǎn)”:凡是被訪問(wèn)(新建/修改命中/訪問(wèn)命中)過(guò)的節(jié)點(diǎn),一律在訪問(wèn)完成后移動(dòng)到雙向鏈表尾部,保證鏈表尾部始終為最“新”節(jié)點(diǎn);
“舊節(jié)點(diǎn)”:保證鏈表頭部始終為最“舊”節(jié)點(diǎn),LRU策略刪除時(shí)表現(xiàn)為刪除雙向鏈表頭部;
從鏈表頭部到尾部,節(jié)點(diǎn)訪問(wèn)熱度逐漸遞增
由于鏈表不支持隨機(jī)訪問(wèn),使用HashMap+雙向鏈表實(shí)現(xiàn)LRU緩存;
HashMap中鍵值對(duì):
雙向鏈表:維護(hù)緩存節(jié)點(diǎn)CacheNode
注意點(diǎn)使用雙向鏈表時(shí),時(shí)刻記得維護(hù)pre和next指針;
題目鏈接lintcode 134: http://www.lintcode.com/zh-cn/problem/lru-cache/
leetcode 146: https://leetcode.com/problems/lru-cache/#/description
Java代碼/** * HashMap+雙向鏈表實(shí)現(xiàn)LRU緩存 * http://www.lintcode.com/zh-cn/problem/lru-cache/ * https://leetcode.com/problems/lru-cache/#/description * @author yzwall */ import java.util.HashMap; class Solution { private HashMapmap; private int capacity; // head.next和tail.next指向鏈表頭尾,包起來(lái)防止null private CacheNode head = new CacheNode(-1, -1); private CacheNode tail = new CacheNode(-1, -1); // 緩存節(jié)點(diǎn) private class CacheNode { int key, value; CacheNode pre, next; CacheNode(int key, int value) { this.key = key; this.value = value; this.pre = null; this.next = null; } } public Solution(int capacity) { this.map = new HashMap<>(); this.capacity = capacity; } // 將已有節(jié)點(diǎn)或新建節(jié)點(diǎn)移動(dòng)到鏈表尾部 private void moveToTail(CacheNode target, boolean isNew) { // 尾部節(jié)點(diǎn)顯然不需要移動(dòng) if (target != tail.next) { if (!isNew) { // 修改舊節(jié)點(diǎn)的雙向鏈表指針 target.pre.next = target.next; target.next.pre = target.pre; } // 添加節(jié)點(diǎn)到鏈表尾部 tail.next.next = target; target.pre = tail.next; tail.next = target; } } // 命中節(jié)點(diǎn)添加到鏈表尾部,未命中返回-1 public int get(int key) { if (map.containsKey(key)) { CacheNode target = map.get(key); // 將已有節(jié)點(diǎn)移動(dòng)到鏈表尾部 moveToTail(target, false); // 此時(shí)鏈表尾部tail.next = target,更新next指向null,防止出現(xiàn)環(huán) tail.next.next = null; return target.value; } return -1; } /** * 1. 節(jié)點(diǎn)命中,修改節(jié)點(diǎn)并移動(dòng)到鏈表尾部tail.next * 2. 節(jié)點(diǎn)未命中, * 2.1 cache已滿,刪除鏈表頭部head.next * 2.2 cache未滿,新建節(jié)點(diǎn)并添加到鏈表尾部tail.next */ public void set(int key, int value) { // cache中存在節(jié)點(diǎn) if (map.containsKey(key)) { CacheNode target = map.get(key); target.value = value; map.put(key, target); // 將訪問(wèn)過(guò)的已有節(jié)點(diǎn)移動(dòng)到鏈表尾部 moveToTail(target, false); } else if(map.size() < capacity) { // cache未滿,添加節(jié)點(diǎn) CacheNode newNode = new CacheNode(key, value); map.put(key, newNode); if (head.next == null) { head.next = newNode; newNode.pre = head; tail.next = newNode; } else { // 將新建節(jié)點(diǎn)移動(dòng)到鏈表尾部 moveToTail(newNode, true); } } else { // cache已滿,淘汰鏈表鏈表頭部節(jié)點(diǎn),新節(jié)點(diǎn)加入到鏈表尾部 CacheNode newNode = new CacheNode(key, value); map.remove(head.next.key); map.put(key, newNode); // cache中只有一個(gè)元素 if (head.next == tail.next) { head.next = newNode; tail.next = newNode; } else { // cache中不止一個(gè)元素,刪除頭部 head.next.next.pre = head; // 更新新頭部.pre = head head.next = head.next.next;// 更新新頭部 // 將新建節(jié)點(diǎn)移動(dòng)到鏈表尾部 moveToTail(newNode, true); } } } }
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://systransis.cn/yun/67024.html
摘要:正如我標(biāo)題所說(shuō),簡(jiǎn)歷被拒??戳宋液?jiǎn)歷之后說(shuō)頭條競(jìng)爭(zhēng)激烈,我背景不夠,點(diǎn)到為止。。三準(zhǔn)備面試其實(shí)從三月份投遞簡(jiǎn)歷開(kāi)始準(zhǔn)備面試到四月份收,也不過(guò)個(gè)月的時(shí)間,但這都是建立在我過(guò)去一年的積累啊。 本文是 無(wú)精瘋 同學(xué)投稿的面試經(jīng)歷 關(guān)注微信公眾號(hào):進(jìn)擊的java程序員K,即可獲取最新BAT面試資料一份 在此感謝 無(wú)精瘋 同學(xué)的分享 目錄: 印象中的頭條 面試背景 準(zhǔn)備面試 ...
摘要:正如我標(biāo)題所說(shuō),簡(jiǎn)歷被拒??戳宋液?jiǎn)歷之后說(shuō)頭條競(jìng)爭(zhēng)激烈,我背景不夠,點(diǎn)到為止。。三準(zhǔn)備面試其實(shí)從三月份投遞簡(jiǎn)歷開(kāi)始準(zhǔn)備面試到四月份收,也不過(guò)個(gè)月的時(shí)間,但這都是建立在我過(guò)去一年的積累啊。 本文是 無(wú)精瘋 同學(xué)投稿的面試經(jīng)歷 關(guān)注微信公眾號(hào):進(jìn)擊的java程序員K,即可獲取最新BAT面試資料一份 在此感謝 無(wú)精瘋 同學(xué)的分享目錄:印象中的頭條面試背景準(zhǔn)備面試頭條一面(Java+項(xiàng)目)頭條...
摘要:在閱讀的源代碼的時(shí)候,發(fā)現(xiàn)其中的類正是一個(gè)線程安全的實(shí)現(xiàn),代碼非常優(yōu)雅。至此一個(gè)線程安全的類就已經(jīng)全部實(shí)現(xiàn),在中使用的緩存是,其實(shí)就是聚合多個(gè)實(shí)例,真正的邏輯都在類中。 緩存是計(jì)算機(jī)的每一個(gè)層次中都是一個(gè)非常重要的概念,緩存的存在可以大大提高軟件的運(yùn)行速度。Least Recently Used(lru) cache 即最近最久未使用的緩存,多見(jiàn)與頁(yè)面置換算法,lru 緩存算法在緩存的...
摘要:雙向鏈表用于管理緩存數(shù)據(jù)結(jié)點(diǎn)的順序,新增數(shù)據(jù)和緩存命中最近被訪問(wèn)的數(shù)據(jù)被放置在結(jié)點(diǎn),尾部的結(jié)點(diǎn)根據(jù)內(nèi)存大小進(jìn)行淘汰。 了解 LRU 之前,我們應(yīng)該了解一下緩存,大家都知道計(jì)算機(jī)具有緩存內(nèi)存,可以臨時(shí)存儲(chǔ)最常用的數(shù)據(jù),當(dāng)緩存數(shù)據(jù)超過(guò)一定大小時(shí),系統(tǒng)會(huì)進(jìn)行回收,以便釋放出空間來(lái)緩存新的數(shù)據(jù),但從系統(tǒng)中檢索數(shù)據(jù)的成本...
摘要:最近在看的源碼,不得不說(shuō)的是,的源碼十分優(yōu)雅簡(jiǎn)潔,下面就來(lái)分享下的緩存利用的算法算法。關(guān)于算法的具體流程,可以來(lái)看下這個(gè),這個(gè)可視化過(guò)程,模擬了算法進(jìn)行調(diào)度的過(guò)程。 最近在看Vue的源碼,不得不說(shuō)的是,Vue的源碼十分優(yōu)雅簡(jiǎn)潔,下面就來(lái)分享下Vue的緩存利用的算法LRU算法。 LRU算法 LRU是Least recently used的簡(jiǎn)寫,主要原理是根據(jù)歷史訪問(wèn)記錄來(lái)淘汰數(shù)據(jù),說(shuō)白了...
閱讀 1608·2023-04-26 01:54
閱讀 1637·2021-09-30 09:55
閱讀 2658·2021-09-22 16:05
閱讀 1873·2021-07-25 21:37
閱讀 2633·2019-08-29 18:45
閱讀 1900·2019-08-29 16:44
閱讀 1895·2019-08-29 12:34
閱讀 1359·2019-08-23 14:02