LRU：最近最少使用快取

LRU是Least Recently Used的縮寫，即最近最少使用，是一種常用的頁面置換演算法，選擇最近最久未使用的頁面予以淘汰，該演算法賦予每個頁面一個訪問欄位，用來記錄一個頁面自上次被訪問以來所經歷的時間 t，當須淘汰一個頁面時，選擇現有頁面中其 t 值最大的，即最近最少使用的頁面予以淘汰，（引自百度百科）

運用所掌握的資料結構，設計和實作一個 LRU (Least Recently Used，最近最少使用) 快取機制 ，

實作 LRUCache 類：

• LRUCache(int capacity) 以正整數作為容量 capacity 初始化 LRU 快取
• int get(int key) 如果關鍵字 key 存在于快取中，則回傳關鍵字的值，否則回傳 -1 ，
• void put(int key, int value) 如果關鍵字已經存在，則變更其資料值；如果關鍵字不存在，則插入該組「關鍵字-值」，當快取容量達到上限時，它應該在寫入新資料之前洗掉最久未使用的資料值，從而為新的資料值留出空間，

解題思路

LRU快取機制對應的結構其實就是一個雙向鏈表，由于get和put方法必須是\(O(1)\)的時間復雜度，可以使用一個哈希表快速定位，找出快取項在雙向鏈表中的位置，隨后將其移動到雙向鏈表的頭部（最近使用的排在隊頭，最久未使用的排在隊尾），即可在 \(O(1)\) 的時間內完成 get 或者 put 操作，

因此，LRU 演算法的核心資料結構就是哈希鏈表，即雙向鏈表和哈希表的結合體，

對于get操作，首先在哈希map中判斷key是否存在：

• 如果key不存在，直接回傳-1；
• 如果key存在，則 key 對應的節點就是最近被使用的節點，通過哈希表定位到該節點在雙向鏈表中的位置，并將其移動到雙向鏈表的頭部，最后回傳該節點的值，

對于put操作，首先也要在哈希 map 中判斷 key 是否存在：

• 如果 key 不存在，使用 key 和 value 創建一個新的節點，在雙向鏈表的頭部添加該節點，并將 key 和該節點添加進哈希表中，然后判斷雙向鏈表是否滿了，如果超出了容量，則洗掉雙向鏈表的尾部節點（把最久未使用的尾部結點給刪了，給新節點騰地兒），并洗掉哈希表中對應的鍵值，最后把新加入的key添加到雙向鏈表的頭部和哈希表中；
• 如果 key 存在，則與 get 操作類似，通過查詢哈希表得到key在雙向鏈表的位置，洗掉該結點，最后把新加入的key添加到雙向鏈表的頭部和哈希表中；

在雙向鏈表初始化時，使用一個啞元頭部（dummy head）和啞元尾部（dummy tail）標記占位，這樣在添加節點和洗掉節點的時候就不需要檢查相鄰的節點是否存在，防止空指標，

代碼實作

自定義雙向鏈表結構（面試推薦?）

class LRUCache {
    
    // 自定義結點型別
    static class Node {
        private int key, val;
        private Node next, prev;
        
        public Node(int k, int v) {
            this.key = k;
            this.val = v;
        }
    }
    
    // 自定義雙向鏈表
    static class DoubleList {
        private Node head, tail;
        // 構造雙向鏈表（head和tail是啞元結點，占位用的）
        public DoubleList() {
            this.head = new Node(-1, -1);
            this.tail = new Node(-1, -1);
            head.next = tail;
            tail.prev = head;
        }
        
        // 在鏈表頭部添加結點（頭插法）
        public void addFirst(Node node) {
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }
        
        // 洗掉指定結點Node
        public void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        
        // 洗掉鏈表尾節點，并回傳該結點
        public Node removeLast() {
            Node node = tail.prev;
            remove(node);
            return node;
        }
    }
    
    private HashMap<Integer, Node> map;		// 輔助map
    private DoubleList cache;
    private int cap;	// 雙向鏈表的最大容量

    public LRUCache(int capacity) {
		map = new HashMap<>();
        cache = new DoubleList();
        this.cap = capacity;
    }
    
    public int get(int key) {
		if(! map.containsKey(key))	return -1;	// map中不存在key，get不到了
        Node node = map.get(key);
        cache.remove(node);
        cache.addFirst(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        // 要添加的結點封裝成一個node
        Node node = new Node(key, value);
        if(map.containsKey(key)) {
            cache.remove(map.get(key));		// 已經有這個key了，舊值刪了，新值頭部添加操作在底下
        } else if(map.size() >= cap) {
            // 雙端鏈表滿了，則把最久未使用的尾部結點給刪了，給新節點騰地兒
            Node lastNode = cache.removeLast();
            map.remove(lastNode.key);
        }
        // 鏈表和map同步添加
        cache.addFirst(node);
        map.put(key, node);
    }
    
    // 測驗
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);	// 初始化雙向鏈表和map
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.get(1);
        lruCache.put(3, 3);
        lruCache.get(2);
        System.out.println(lruCache.map);
    }
}

在 Java 語言中，同樣有類似的資料結構 LinkedHashMap，內部已經封裝好添加查詢的方法，但是面試時不推薦使用，還是推薦使用上面這種方式，

class LRUCache {

    private int cap;
    private LinkedHashMap<Integer, Integer> cache;

    public LRUCache(int capacity) {
        this.cap = capacity;
        this.cache = new LinkedHashMap<>()
    }

    // 使用了key，就得設這個key為最近使用
    public int get(int key) {
        if(! cache.containsKey(key)) {
            return -1;
        }
        makeRecently(key);
        return cache.get(key);
    }

    public void put(int key, int value) {
        // key 存在于鏈表中
        if(cache.containsKey(key)) {
            cache.put(key, value);    // 修改 key 的值
            makeRecently(key);      // 將 key 變為最近使用
            return;
        }
        // 插入元素前需要判斷鏈表容量是否已滿，淘汰最久未使用的key
        if(cache.size() >= this.cap) {
            // 鏈表頭部就是最久未使用的 key
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        // 將新的 key 添加鏈表尾部
        cache.put(key, value);
    }

    // 設定key為最近使用，key先刪了移到鏈表尾
    private void makeRecently(int key) {
        int val = cache.get(key);
        // 洗掉 key，重新插入到隊尾
        cache.remove(key);
        cache.put(key, val);
    }

    // 測驗
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.get(1);
        lruCache.put(3,3);
        lruCache.get(2);
        System.out.println(cache);
    }

}

復雜度

• 時間復雜度：put 和 get 操作的平均時間復雜度都為\(O(1)\)；
• 空間復雜度：\(O(capacity)\)，哈希表和雙向鏈表中最多存盤 capacity 個元素，

參考

labuladong：https://leetcode.cn/problems/lru-cache/solutions/12711/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/

標籤：其他

上一篇：過濾組件、排序組件、全域例外處理、自己封裝的response物件

下一篇：Scala-集合