面試必備：LRU緩存機(jī)制的Java實(shí)現(xiàn)

請你設(shè)計(jì)并實(shí)現(xiàn)一個(gè)滿足 LRU (最近最少使用) 緩存約束的數(shù)據(jù)結(jié)構(gòu)。

這是一道大廠面試高頻出現(xiàn)的算法題，難度為??????，屬于中等，老鐵們來一起看看這個(gè)題該怎么解？

1. 原題再現(xiàn)

沒有廢話，翠花，上酸菜！

2. 具體實(shí)現(xiàn)

為了實(shí)現(xiàn)一個(gè)滿足 LRU （最近最少使用）緩存約束的數(shù)據(jù)結(jié)構(gòu)，我們需要一個(gè)能夠快速訪問、更新和刪除的數(shù)據(jù)結(jié)構(gòu)，V 哥想到了用哈希表，因?yàn)楣１硖峁┝丝焖俚牟檎夷芰?，但是它不能保持元素的順序；而雙向鏈表可以保持元素的順序，并且可以在 O(1) 時(shí)間復(fù)雜度內(nèi)進(jìn)行插入和刪除操作。因此， V哥采用結(jié)合使用哈希表和雙向鏈表來實(shí)現(xiàn)LRU緩存。

以下是 Java 代碼實(shí)現(xiàn)：

import java.util.HashMap;


class Node {
    int key;
    int value;
    Node prev;
    Node next;


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


public class LRUCache {
    private HashMap<Integer, Node> cache;
    private Node head, tail;
    private int capacity;
    private int count;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.count = 0;
    }


    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }


    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node == null) {
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addNode(newNode);
            count++;
            if (count > capacity) {
                Node toDel = popTail();
                cache.remove(toDel.key);
                count--;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }


    private void addNode(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 void moveToHead(Node node) {
        removeNode(node);
        addNode(node);
    }


    private Node popTail() {
        Node res = tail.prev;
        removeNode(res);
        return res;
    }
}

使用示例：

public class Main {
    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // 緩存是 {1=1}
        lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}
        System.out.println(lRUCache.get(1));    // 返回 1
        lRUCache.put(3, 3); // 該操作會使得關(guān)鍵字 2 作廢，緩存是 {1=1, 3=3}
        System.out.println(lRUCache.get(2));    // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 該操作會使得關(guān)鍵字 1 作廢，緩存是 {4=4, 3=3}
        System.out.println(lRUCache.get(1));    // 返回 -1 (未找到)
        System.out.println(lRUCache.get(3));    // 返回 3
        System.out.println(lRUCache.get(4));    // 返回 4
    }
}

輸出結(jié)果應(yīng)該與題目中的示例輸出一致。這個(gè)實(shí)現(xiàn)使用了哈希表來快速查找節(jié)點(diǎn)，同時(shí)使用雙向鏈表來維護(hù)節(jié)點(diǎn)的順序和實(shí)現(xiàn)快速插入和刪除操作。這樣，我們就可以在 O(1) 的時(shí)間復(fù)雜度內(nèi)完成 get 和 put 操作。

實(shí)現(xiàn)過程和步驟如下：

1. 定義一個(gè) Node 類，用于雙向鏈表的節(jié)點(diǎn)，包含 key、value 以及前驅(qū)和后繼節(jié)點(diǎn)的引用。

1. 在 LRUCache 類中，定義一個(gè) capacity 表示緩存的最大容量，一個(gè) count 表示當(dāng)前緩存中的節(jié)點(diǎn)數(shù)量，一個(gè) cache 哈希表用于存儲鍵和節(jié)點(diǎn)的映射，以及 head 和 tail 虛擬節(jié)點(diǎn)用于簡化雙向鏈表的操作。

1. 實(shí)現(xiàn) get 方法，首先在哈希表中查找鍵對應(yīng)的節(jié)點(diǎn)，如果節(jié)點(diǎn)不存在，返回 -1。如果節(jié)點(diǎn)存在，則將該節(jié)點(diǎn)移動(dòng)到鏈表的頭部，表示最近被使用，然后返回節(jié)點(diǎn)的值。

1. 實(shí)現(xiàn) put 方法，如果鍵在哈希表中不存在，創(chuàng)建一個(gè)新的節(jié)點(diǎn)，并將其添加到鏈表的頭部，同時(shí)添加到哈希表中。如果插入后節(jié)點(diǎn)數(shù)量超過了容量，則需要移除鏈表尾部的節(jié)點(diǎn)，并從哈希表中刪除對應(yīng)的條目。如果鍵已經(jīng)存在，則更新對應(yīng)的節(jié)點(diǎn)值，并將其移動(dòng)到鏈表頭部。

1. addNode 方法用于將節(jié)點(diǎn)添加到鏈表頭部，removeNode 方法用于從鏈表中移除節(jié)點(diǎn)，moveToHead 方法用于將節(jié)點(diǎn)移動(dòng)到鏈表頭部，popTail 方法用于移除鏈表尾部的節(jié)點(diǎn)。

1. 在 Main 類的 main 方法中，我們創(chuàng)建了一個(gè) LRUCache 實(shí)例，并執(zhí)行了一系列的 put 和 get 操作來演示其功能。

V哥認(rèn)為這個(gè)實(shí)現(xiàn)確保了 get 和 put 操作的平均時(shí)間復(fù)雜度為O(1)。get 操作直接通過哈希表查找節(jié)點(diǎn)，而 put 操作中，無論是更新現(xiàn)有節(jié)點(diǎn)還是添加新節(jié)點(diǎn)，都涉及到對雙向鏈表的操作，這些操作的時(shí)間復(fù)雜度都是 O(1)。當(dāng)緩存達(dá)到容量上限時(shí)，put 操作會移除最久未使用的節(jié)點(diǎn)，這也是 O(1) 時(shí)間復(fù)雜度的操作。

3. 小結(jié)一下

V哥的這個(gè)實(shí)現(xiàn)的關(guān)鍵在于維護(hù)一個(gè)雙向鏈表，它可以幫助我們快速地訪問、更新和刪除最近最少使用的節(jié)點(diǎn)，同時(shí)使用哈希表來提供快速的查找能力。這樣，我們就可以在 O(1) 的時(shí)間復(fù)雜度內(nèi)完成所有的緩存操作。哈哈干凈利索，回答完畢。