劍指offer/LeetCode146/LintCode134_LRU緩存實現

you_De 發布于2019-08-14 18:08 / 1409人閱讀

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

劍指offer/LeetCode146/LintCode134_LRU緩存實現 聲明

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

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

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

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

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

緩存未滿，

節點存在，修改value；

節點不存在，添加新節點進緩存；

解題思路

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

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

“舊節點”：保證鏈表頭部始終為最“舊”節點，LRU策略刪除時表現為刪除雙向鏈表頭部；

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

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

HashMap中鍵值對：

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

GPU云服務器云服務器 LintCode134_LRU lru用c語言實現劍指 cdn緩存如何實現

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/67024.html

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

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

tracymac7 2019-08-15 17:57 評論0 收藏0
從簡歷被拒到收割今日頭條 offer，我用一年時間破繭成蝶！

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

wdzgege 2019-08-19 11:43 評論0 收藏0
一個線程安全的 lrucache 實現 --- 讀 leveldb 源碼

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

widuu 2019-08-06 13:30 評論0 收藏0
web技術分享| LRU 緩存淘汰算法

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

graf 2021-11-24 09:39 評論0 收藏0
Vue的緩存算法—LRU算法

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

elina 2019-08-21 14:30 評論0 收藏0