LRU 快取淘汰演算法

Least Recently Used(LRU) 是快取淘汰一種常用的策略，記憶體滿了則優先洗掉最久沒被使用的資料，

LRU 演算法的需求

1. 接收一個引數 capacity 作為快取的最大容量
2. 實作一個函式 put() 添加資料到快取
3. 實作一個函式 get() 查詢快取中的資料
4. 以上函式應該在 \(O(1)\) 的時間內完成

滿足以上需求的資料結構 —— 哈希表 + 雙向鏈表，通過哈希表快速定位到鏈表中的節點，然后完成添加、洗掉等操作，

LRU 演算法的實作

節點定義

public class Node {
    public int key;
    public String data;
    public Node next;
    public Node prev;
    
    public Node(int key, String data) {
        this.key = key;
        this.value = https://www.cnblogs.com/ylyzty/archive/2023/06/28/value;
        this.next = null;
        this.prev = null;
    }
}

雙向鏈表

public class MyLinkedList {
    private Node head;    // 頭節點
    private Node tail;    // 尾節點
    private int size;
    
    public MyLinkedList() {
        this.head = new Node(-1, "head");
        this.tail = new Node(-1, "tail");
        
        head.next = tail;
        tail.prev = head;
        
        this.size = 0;
    }
    
     // 添加新的資料到快取
     public void addLast(Node node) {
         node.prev = tail.prev;
         node.next = tail;
         tail.prev.next = node;
         tail.prev = node;
         
         this.size += 1;
     }
    
    // 洗掉快取中的某項資料
    public void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        
        this.size -= 1;
    }
    
    // 快取空間已滿，洗掉最早未被使用的資料
    public Node removeFirst() {
        if (head.next == tail) {
            return null;
        }
        
        Node first = head.next;
        remove(first);
        
        return first;
    } 
    
    public int size() {
        return this.size;
    }
}

LRU Cache

目前使用的雙向鏈表支持從尾部插入，即尾部為最新的資料，頭部則是最久未被使用的資料，

public class LRUCache {
    private Map<Integer, Node> map;
    private MyLinkedList cache;
    private int capacity;
    
    public LRUCache(int capacity) {
        this.map = new HashMap<>();
        this.cache = new MyLinkedList();
        this.capacity = capacity;
    }
    
    public String get(int key) {
        if (!map.containsKey(key)) {
            return null;
        }
        
        makeRecently(key);
        return map.get(key).data;
    }
    
    /**
     * 1. 判斷 key 是否已存在于快取，若已存在則更新對應的data，并設定為最新使用即添加到隊尾
     * 2. 判斷快取空間是否已滿，若已滿則洗掉最久未使用的資料
     */
    public void put(int key, String data) {
        if (map.containsKey(key)) {
            deleteKey(key);
            addRecently(key, data);
            return;
        }
        
        // 快取空間已滿
        if (this.capacity == cache.size()) {
            removeLeastRecently();
        }
        
        addRecently(key, data);
    }
    
    private void addRecently(int key, String data) {
        Node node = new Node(key, data);
        cache.addLast(node);
        map.put(key, node);
    }
    
    private void makeRecently(int key) {
        Node node = map.get(key);
        cache.remove(node);
        cache.addLast(node);
    }
    
    private void deleteKey(int key) {
        Node node = map.get(key);
        cache.remove(node);
        map.remove(key);
    }
    
    /**
     * 洗掉最久未被使用的資料
     */
    private void removeLeastRecently() {
        Node node = cache.removeFirst();
        map.remove(node.key);
    }
}

標籤：其他

上一篇：JDBC p1 JDBC概述

下一篇：返回列表