LRU(最近最少使用)緩存機制簡介

LRU緩存機制（Least Recently Used）是一種常用的緩存淘汰政策，用于提高記憶體通路效率。它的基本邏輯：最近被通路的資料很可能在近期内會再次被通路，而較長時間未被通路的資料則可能變得不那麼重要，LRU緩存機制的基本原理是保留最近被使用過的資料，将最久未被使用的資料淘汰出緩存。

LRU緩存機制通常由一個緩存資料結構和相關的操作組成。常見的資料結構是使用哈希表和雙向連結清單實作的LRU緩存。

在實際應用中，LRU緩存機制被廣泛用于資料庫管理系統、作業系統的頁面置換、Web伺服器的緩存等場景，以提高資料通路速度和系統性能。

那麼，如何判斷哪些資料是最接近未被使用的呢？這就需要借助一些算法和技術來實作。一般來說，有兩種常見的方法可以用于判斷資料的“新鮮度”：時間戳和通路次數。

1. 基于時間戳的方法：在這種方法中，每個資料項都會記錄一個時間戳，表示其被通路或添加到緩存中的時刻。當新的資料需要被通路時，系統會比較目前時間與所有資料項的時間戳，找到最晚被通路的那個資料項，并将其放入緩存中。這樣可以確定緩存中的資料都是最近被使用的。
2. 基于通路次數的方法：在這種方法中，每個資料項都會記錄一個通路次數計數器。當新的資料需要被通路時，系統會比較目前通路次數與所有資料項的通路次數計數器，找到通路次數最少的那個資料項，并将其放入緩存中。這樣可以確定緩存中的資料都是最不常被使用的。

Java實作示例

下面是一個使用Java實作LRU緩存機制的示例代碼：

import java.util.HashMap;
import java.util.Map;

class LRUCache {
    class Node {
        int key;
        int value;
        Node prev;
        Node next;
        
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private int capacity;
    private Map<Integer, Node> cache;
    private Node head;
    private Node tail;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            moveToHead(node);
            return node.value;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            if (cache.size() > capacity) {
                Node tailNode = removeTail();
                cache.remove(tailNode.key);
            }
        }
    }
    
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
    
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private Node removeTail() {
        Node tailNode = tail.prev;
        removeNode(tailNode);
        return tailNode;
    }
}
           

上述示例代碼中的LRUCache類實作了一個固定容量的LRU緩存。它使用了哈希表 cache 存儲緩存資料，并使用雙向連結清單來維護緩存資料的通路順序。

• get(key) 方法用于擷取指定鍵的緩存值。如果鍵存在于緩存中，則傳回對應的值，并将該鍵對應的節點移動到連結清單頭部，表示最近被通路過。如果鍵不存在于緩存中，則傳回 -1。
• put(key, value) 方法用于将指定的鍵值對添加到緩存中。如果鍵已存在于緩存中，則更新對應的值，并将該鍵對應的節點移動到連結清單頭部。如果鍵不存在于緩存中，則建立一個新的節點，并将其添加到連結清單頭部。若緩存已滿，則淘汰連結清單尾部的節點，并從哈希表中删除對應的鍵。

通過以上的示例代碼，基本可以了解LRU緩存機制的基本原理。