LRU緩存算法怎么用

這篇文章主要介紹了LRU緩存算法怎么用，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

LRU（Least Recently Used），即最近最少使用，是一種內存管理算法，該算法基于一個假設：長期不被使用的數據，未來會被使用的概率也很低。當緩存占用達到某個值的時候，應該移除最近最少被使用的數據。

1、LRU 的存儲結構

LRU 存儲結構是哈希鏈表，哈希表的數據存儲是無序的，但查找效率比較高，而雙鏈表通過前驅和后繼指針使其在邏輯上有序。

• [ ] TODO ：LinkedHashMap 的源碼。

• 通過 Hash 表快速找到所需要節點

• 通過雙鏈表的特性，可以快速增加和刪除節點

• 通過雙鏈表，使其在邏輯上有序

對于緩存中沒有的數據，會將其加入到鏈表的尾部：

對于緩存中已經有的數據，會更新數據值，并把節點移動到鏈表的尾部

當緩存容量不夠時候，會將頭節點移除

2、代碼實現簡單的 LRUCache

雙鏈表的數據結構：

public class Node {
    public String Key;
    public String value;
    public Node pre;
    public Node next;

    public Node(String key, String value) {
        Key = key;
        this.value = value;
    }
}

LRUCache 的簡單實現

ublic class LRUCache {
    // 頭結點和尾部結點
    private Node head;
    private Node end;
    // LRU Cache 容量
    private int limit;
    // HashMap 用來存儲
    public Map<String, Node> hashMap;

    public LRUCache(int limit) {
        this.limit = limit;
        hashMap = new HashMap<>();
    }

    // 根據 key 獲取 value
    public String get(String key) {
        Node node = hashMap.get(key);
        if (node != null) {
            // 更新
            refreshNode(node);
            return node.value;
        }
        return null;
    }

    // 添加
    public void put(String key, String value) {
        // 檢查是否存在 key
        Node node = hashMap.get(key);
        if (node != null) {
            // 如果 key 已經存在，則直接更新 value，并刷新鏈表
            node.value = value;
            refreshNode(node);
        } else {
            // 判斷是否大于 LRU 長度
            if (hashMap.size() >= limit) {
                // 移除頭部節點
                String oldKey = removeNode(head);
                // 從 hashMap 中移除
                hashMap.remove(oldKey);
            }
            // key 不存在 ，直接插入
            node = new Node(key, value);
            // 添加到鏈表尾部
            addNode(node);
            // 添加到 hashMap
            hashMap.put(key, node);
        }
    }

    public String remove(String key) {
        Node node = hashMap.get(key);
        if (node != null) {
            // 移除這個節點
            removeNode(node);
            hashMap.remove(key);
            return node.value;
        }
        return null;
    }


    private void refreshNode(Node node) {
        // 如果是尾部節點，無需移動
        // 如果不是尾部節點，先移除，再添加到尾部節點
        if (node != end) {
            // 移除
            removeNode(node);
            // 添加到尾部
            addNode(node);
        }
    }

    // 尾部添加結點
    private void addNode(Node node) {
        // 尾部插入
        if (end != null) {
            end.next = node;
            node.pre = end;
            node.next = null;
        }
        // 新的節點變為尾部
        end = node;
        // 如果頭部為空，既是尾部也是頭部
        if (head == null) {
            head = node;
        }
    }

    // 移除節點
    private String removeNode(Node node) {
        // 如果只有一個節點
        if (node == head && node == end) {
            // 移除唯一節點
            head = null;
            end = null;
        } else if (node == end) {
            // 移除尾部節點
            end = end.pre;
            end.next = null;
        } else if (node == head) {
            // 移除頭部節點
            head = head.next;
            head.pre = null;
        } else {
            // 移除中間的節點
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        return node.Key;
    }

    // 測試
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(5);
        cache.put("key1", "value1");
        cache.put("key2", "value2");
        cache.put("key3", "value3");
        cache.put("key4", "value4");
        cache.put("key5", "value5");
        cache.put("001", "001 的 value");
      	// 會輸出 null，因為已經從緩存中移除
        System.out.println(cache.get("key1"));

        Map<String,String> map = new LinkedHashMap<>();
        map.put("ddd","ddd");
    }
}

感謝你能夠認真閱讀完這篇文章，希望小編分享的“LRU緩存算法怎么用”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!