亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

劍指offer/LeetCode146/LintCode134_LRU緩存實現(xiàn)

you_De / 1472人閱讀

摘要：劍指緩存實現(xiàn)聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處解題思路緩存兩種功能獲取的對應(yīng)，不存在返回版本版本設(shè)置緩存已滿，刪除最近最久未被使用的節(jié)點，添加新節(jié)點進緩存緩存未滿，節(jié)點存在，修改節(jié)點不存在，添加新節(jié)點進緩存解題思路由于緩存插入和刪除

劍指offer/LeetCode146/LintCode134_LRU緩存實現(xiàn) 聲明

文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處
[1] https://segmentfault.com/u/yzwall
[2] blog.csdn.net/j_dark/

解題思路 LRU緩存兩種功能：

get(key)：獲取key的對應(yīng)value，不存在返回-1

set(key, value)（lintcode版本）/put(key, value)（leetcode版本）：設(shè)置

緩存已滿，刪除最近最久未被使用的節(jié)點，添加新節(jié)點進緩存

緩存未滿，

節(jié)點存在，修改value；

節(jié)點不存在，添加新節(jié)點進緩存；

解題思路

由于LRU緩存插入和刪除操作頻繁，使用雙向鏈表維護緩存節(jié)點，

“新節(jié)點”：凡是被訪問（新建/修改命中/訪問命中）過的節(jié)點，一律在訪問完成后移動到雙向鏈表尾部，保證鏈表尾部始終為最“新”節(jié)點；

“舊節(jié)點”：保證鏈表頭部始終為最“舊”節(jié)點，LRU策略刪除時表現(xiàn)為刪除雙向鏈表頭部；

從鏈表頭部到尾部，節(jié)點訪問熱度逐漸遞增

由于鏈表不支持隨機訪問，使用HashMap+雙向鏈表實現(xiàn)LRU緩存；

HashMap中鍵值對：

雙向鏈表：維護緩存節(jié)點CacheNode

注意點

使用雙向鏈表時，時刻記得維護pre和next指針；

題目鏈接

lintcode 134: http://www.lintcode.com/zh-cn/problem/lru-cache/

leetcode 146: https://leetcode.com/problems/lru-cache/#/description

Java代碼 
/**
 * HashMap+雙向鏈表實現(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 HashMap map;
    private int capacity;
    // head.next和tail.next指向鏈表頭尾，包起來防止null
    private CacheNode head = new CacheNode(-1, -1);
    private CacheNode tail = new CacheNode(-1, -1);
    
    // 緩存節(jié)點
    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é)點或新建節(jié)點移動到鏈表尾部
    private void moveToTail(CacheNode target, boolean isNew) {
        // 尾部節(jié)點顯然不需要移動
        if (target != tail.next) {
            if (!isNew) {
                // 修改舊節(jié)點的雙向鏈表指針
                target.pre.next = target.next; 
                target.next.pre = target.pre;
            }
            // 添加節(jié)點到鏈表尾部
            tail.next.next = target;
            target.pre = tail.next;
            tail.next = target;
        }
    }
    
    // 命中節(jié)點添加到鏈表尾部，未命中返回-1
    public int get(int key) {
        if (map.containsKey(key)) {
            CacheNode target = map.get(key);
            // 將已有節(jié)點移動到鏈表尾部
            moveToTail(target, false);
            // 此時鏈表尾部tail.next = target，更新next指向null，防止出現(xiàn)環(huán)
            tail.next.next = null;
            return target.value;
        }
        return -1;
    }
    
    /**
     * 1. 節(jié)點命中，修改節(jié)點并移動到鏈表尾部tail.next
     * 2. 節(jié)點未命中，
     *    2.1 cache已滿，刪除鏈表頭部head.next
     *    2.2 cache未滿，新建節(jié)點并添加到鏈表尾部tail.next
     */
    public void set(int key, int value) {
        // cache中存在節(jié)點
        if (map.containsKey(key)) {
            CacheNode target = map.get(key);
            target.value = value;
            map.put(key, target);
            // 將訪問過的已有節(jié)點移動到鏈表尾部
            moveToTail(target, false);
        } else if(map.size() < capacity) {    // cache未滿，添加節(jié)點
            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é)點移動到鏈表尾部
                moveToTail(newNode, true);
            }
        } else {    // cache已滿，淘汰鏈表鏈表頭部節(jié)點，新節(jié)點加入到鏈表尾部
            CacheNode newNode = new CacheNode(key, value);
            map.remove(head.next.key);
            map.put(key, newNode);
            // cache中只有一個元素
            if (head.next == tail.next) {
                head.next = newNode;
                tail.next = newNode;
            } else {    // cache中不止一個元素，刪除頭部
                head.next.next.pre = head; // 更新新頭部.pre = head
                head.next = head.next.next;// 更新新頭部
                // 將新建節(jié)點移動到鏈表尾部
                moveToTail(newNode, true);
            }
        }
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/67024.html

相關(guān)文章

  • 從簡歷被拒到收割今日頭條 offer，我用一年時間破繭成蝶！

    摘要：正如我標題所說，簡歷被拒。看了我簡歷之后說頭條競爭激烈，我背景不夠，點到為止。。三準備面試其實從三月份投遞簡歷開始準備面試到四月份收，也不過個月的時間，但這都是建立在我過去一年的積累啊。 本文是 無精瘋 同學(xué)投稿的面試經(jīng)歷 關(guān)注微信公眾號：進擊的java程序員K，即可獲取最新BAT面試資料一份 在此感謝 無精瘋 同學(xué)的分享 目錄： 印象中的頭條 面試背景 準備面試 ...

    tracymac7 評論0 收藏0

  • 從簡歷被拒到收割今日頭條 offer，我用一年時間破繭成蝶！

    摘要：正如我標題所說，簡歷被拒?？戳宋液啔v之后說頭條競爭激烈，我背景不夠，點到為止。。三準備面試其實從三月份投遞簡歷開始準備面試到四月份收，也不過個月的時間，但這都是建立在我過去一年的積累啊。 本文是 無精瘋 同學(xué)投稿的面試經(jīng)歷 關(guān)注微信公眾號：進擊的java程序員K，即可獲取最新BAT面試資料一份 在此感謝 無精瘋 同學(xué)的分享目錄：印象中的頭條面試背景準備面試頭條一面（Java+項目）頭條...

    wdzgege 評論0 收藏0

  • 一個線程安全的 lrucache 實現(xiàn) --- 讀 leveldb 源碼

    摘要：在閱讀的源代碼的時候，發(fā)現(xiàn)其中的類正是一個線程安全的實現(xiàn)，代碼非常優(yōu)雅。至此一個線程安全的類就已經(jīng)全部實現(xiàn)，在中使用的緩存是，其實就是聚合多個實例，真正的邏輯都在類中。 緩存是計算機的每一個層次中都是一個非常重要的概念，緩存的存在可以大大提高軟件的運行速度。Least Recently Used(lru) cache 即最近最久未使用的緩存，多見與頁面置換算法，lru 緩存算法在緩存的...

    widuu 評論0 收藏0

  • web技術(shù)分享| LRU 緩存淘汰算法

    摘要：雙向鏈表用于管理緩存數(shù)據(jù)結(jié)點的順序，新增數(shù)據(jù)和緩存命中最近被訪問的數(shù)據(jù)被放置在結(jié)點，尾部的結(jié)點根據(jù)內(nèi)存大小進行淘汰。 了解 LRU 之前，我們應(yīng)該了解一下緩存，大家都知道計算機具有緩存內(nèi)存，可以臨時存儲最常用的數(shù)據(jù)，當(dāng)緩存數(shù)據(jù)超過一定大小時，系統(tǒng)會進行回收，以便釋放出空間來緩存新的數(shù)據(jù)，但從系統(tǒng)中檢索數(shù)據(jù)的成本...

    graf 評論0 收藏0

  • Vue的緩存算法—LRU算法

    摘要：最近在看的源碼，不得不說的是，的源碼十分優(yōu)雅簡潔，下面就來分享下的緩存利用的算法算法。關(guān)于算法的具體流程，可以來看下這個，這個可視化過程，模擬了算法進行調(diào)度的過程。 最近在看Vue的源碼，不得不說的是，Vue的源碼十分優(yōu)雅簡潔，下面就來分享下Vue的緩存利用的算法LRU算法。 LRU算法 LRU是Least recently used的簡寫，主要原理是根據(jù)歷史訪問記錄來淘汰數(shù)據(jù)，說白了...

    elina 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<