[Leetcode] LRU Cache 最近使用緩存

Render 發布于2019-08-14 12:31 / 3251人閱讀

摘要：但是哈希表無序的，我們沒辦法在緩存滿時，將最早更新的元素給刪去。所以雙向鏈表是最好的選擇。我們用雙向鏈表實現一個隊列用來記錄每個元素的順序，用一個哈希表來記錄鍵和值的關系，就行了。

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. 
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

雙向鏈表加哈希表 復雜度

時間 Get O(1) Set O(1) 空間 O(N)

思路

緩存講究的就是快，所以我們必須做到O(1)的獲取速度，這樣看來只有哈希表可以勝任。但是哈希表無序的，我們沒辦法在緩存滿時，將最早更新的元素給刪去。那么是否有一種數據結構，可以將先進的元素先出呢？那就是隊列。所以我們將元素存在隊列中，并用一個哈希表記錄下鍵值和元素的映射，就可以做到O(1)獲取速度，和先進先出的效果。然而，當我們獲取一個元素時，還需要把這個元素再次放到隊列頭，這個元素可能在隊列的任意位置，可是隊列并不支持對任意位置的增刪操作。而最適合對任意位置增刪操作的數據結構又是什么呢？是鏈表。我可以用鏈表來實現一個隊列，這樣就同時擁有鏈表和隊列的特性了。不過，如果僅用單鏈表的話，在任意位置刪除一個節點還是很麻煩的，要么記錄下該節點的上一個節點，要么遍歷一遍。所以雙向鏈表是最好的選擇。我們用雙向鏈表實現一個隊列用來記錄每個元素的順序，用一個哈希表來記錄鍵和值的關系，就行了。

注意

這題更多的是考察用數據結構進行設計的能力，再寫代碼時盡量將子函數拆分出來，先寫個整體的框架。

移出鏈表最后一個節點時，要記得在鏈表和哈希表中都移出該元素，所以節點中也要記錄Key的信息，方便在哈希表中移除

代碼

public class LRUCache {
    
    int size;
    int capacity;
    ListNode tail;
    ListNode head;
    Map map;
    
    public LRUCache(int capacity) {
        this.head = new ListNode(-1,-1);
        this.tail = new ListNode(-1,-1);
        head.next = tail;
        tail.prev = head;
        this.size = 0;
        this.capacity = capacity;
        this.map = new HashMap();
    }
    
    public int get(int key) {
        ListNode n = map.get(key);
        if(n != null){
            moveToHead(n);
            return n.val;
        } else {
            return -1;
        }
    }
    
    public void set(int key, int value) {
        ListNode n = map.get(key);
        if(n == null){
            n = new ListNode(value, key);
            attachToHead(n);
            size++;
        } else {
            n.val = value;
            moveToHead(n);
        }
        // 如果更新節點后超出容量，刪除最后一個
        if(size > capacity){
            removeLast();
            size--;
        }
        map.put(key, n);
    }
    
    // 將一個孤立節點放到頭部
    private void attachToHead(ListNode n){
        n.next = head.next;
        n.next.prev = n;
        head.next = n;
        n.prev = head;
    }
    
    // 將一個鏈表中的節點放到頭部
    private void moveToHead(ListNode n){
        n.prev.next = n.next;
        n.next.prev = n.prev;
        attachToHead(n);
    }
    
    // 移出鏈表最后一個節點
    private void removeLast(){
        ListNode last = tail.prev;
        last.prev.next = tail;
        tail.prev = last.prev;
        map.remove(last.key);
    }
    
    public class ListNode {
        ListNode prev;
        ListNode next;
        int val;
        int key;
        public ListNode(int v, int k){
            this.val = v;
            this.prev = null;
            this.next = null;
            this.key = k;
        }
    }
}

云服務器 GPU云服務器最近最多使用算法最近最少使用算法java實現最近最久未使用算法博客最近最久未使用算法程序

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

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

劍指offer/LeetCode146/LintCode134_LRU緩存實現

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

you_De 2019-08-14 18:08 評論0 收藏0
力扣(LeetCode)146

摘要：當緩存容量達到上限時，它應該在寫入新數據之前刪除最近最少使用的數據值，從而為新的數據值留出空間。但是無法保證是，也無法保證更新數據時是，因為這兩個操作必然要遍歷隊列。因為可以通過來判斷是否有這個節點。題目地址：https://leetcode-cn.com/probl...題目描述：運用你所掌握的數據結構，設計和實現一個 LRU (最近最少使用) 緩存機制。它應該支持以下操作：獲...

zr_hebo 2019-08-16 15:22 評論0 收藏0
筆記｜緩存

摘要：緩存算法我是，我會統計每一個緩存數據的使用頻率，我會把使用最少的緩存替換出緩存區。瀏覽器就是使用了我作為緩存算法。在緩存系統中找出最少最近的對象是需要較高的時空成本。再來一次機會的緩存算法，是對的優化。直到新的緩存對象被放入。緩存什么是緩存？ showImg(https://segmentfault.com/img/bVusZg); 存貯數據（使用頻繁的數據）的臨時地方，因為取原始...

elliott_hu 2019-08-06 13:15 評論0 收藏0
NPM酷庫：lru-cache 基于內存的緩存管理

摘要：酷庫，每天兩分鐘，了解一個流行庫。而直接將數據保存在程序變量中，最經濟快捷。但是這樣就會帶來一些其他問題，比如緩存更新緩存過期等。用于在內存中管理緩存數據，并且支持算法。可以讓程序不依賴任何外部數據庫實現緩存管理。 NPM酷庫，每天兩分鐘，了解一個流行NPM庫。為了優化程序性能，我們常常需要獎數據緩存起來，根據實際情況，我們可以將數據存儲到磁盤、數據庫、redis等。但是有時候要緩...

Yumenokanata 2019-08-06 13:29 評論0 收藏0