LRU缓存实现以及哨兵节点

LRU缓存

LRU算法，即最近最久未使用算法，广泛应用于内存管理之中，在MySQL，Redis，操作系统的内存淘汰策略中均有它的影子。

该算法通过双向链表+哈希表实现。当我们访问某个节点的时候，先看链表中是否存在该节点，如果存在，将该节点移动到链表首部，并更新该节点的值。当我们插入节点的时候，插入到链表首部，如果链表容量达到上限，删去尾部节点。

由于双向链表+哈希表，我们的LRU缓存插入删除的时间复杂度都是O(1)。

LRU缓存的实现，包含几部分：

- 双向链表，通过内部类Node表示
- 容量，用capacity表示
- 首尾哨兵节点，dummy表示，
- 哈希表，keyToNode表示

核心实现在于三个方法：

- remove(Node x)方法，移除指定节点
- pushFront(Node x)方法，插入节点至头部
- getNode(int key)方法，查询链表中的节点，如果存在，移动到头部

暴露的两个方法get和put均基于上面三个方法实现

下面是该算法的实现

public class LRUCache {
    private class Node {
        private int key, value;
        private Node prev, next;

        private Node(int k, int v) {
            this.key = k;
            this.value = v;
        }
    }

    private final int capacity;
    private final Node dummy = new Node(0, 0);
    private final Map<Integer, Node> keyToNode = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.next = dummy;
        dummy.prev = dummy;
    }

    public int get(int key) {
        Node node = getNode(key);
        return node == null ? -1 : node.value;
    }

    public void put(int key, int value) {
        Node node = getNode(key);
        if (node != null) {
            node.value = value;
            return;
        }
        node = new Node(key, value);
        pushFront(node);
        keyToNode.put(key, node);
        if (keyToNode.size() > capacity) {
            Node backNode = dummy.prev;
            remove(backNode);
            keyToNode.remove(backNode.key);
        }
    }

    private Node getNode(int key) {
        Node node = keyToNode.get(key);
        if (node == null) {
            return null;
        }
        remove(node);
        pushFront(node);
        return node;
    }

    private void remove(Node x) {
        x.next.prev = x.prev;
        x.prev.next = x.next;
    }

    private void pushFront(Node x) {
        x.prev = dummy;
        x.next = dummy.next;
        x.prev.next = x;
        x.next.prev = x;
    }
}

这里面一大难点就在于理解为什么dummy.prev就是尾节点

Node backNode = dummy.prev;

我们先看初始化方法

public LRUCache(int capacity) {
    this.capacity = capacity;
    dummy.next = dummy;
    dummy.prev = dummy;
}

其实这段代码可以这样理解

dummy <---> dummy

然后看pushFront方法

private void pushFront(Node x) {
    x.prev = dummy;
    x.next = dummy.next;
    x.prev.next = x;
    x.next.prev = x;
}

相当于

dummy <---> x1...xn <---> dummy

我们发现dummy.prev就是尾节点。并且LRU通过首尾哨兵节点省略了边界条件特判。

链表中的哨兵节点

不带哨兵节点的情况下，插入节点

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

class LinkedListNoSentinel {
    ListNode head;

    // 在第 index 个位置插入 val（0-based）
    public void insert(int index, int val) {
        if (index == 0) {
            ListNode newNode = new ListNode(val);
            newNode.next = head;
            head = newNode;
            return;
        }

        ListNode prev = head;
        for (int i = 0; i < index - 1 && prev != null; i++) {
            prev = prev.next;
        }

        if (prev == null) {
            throw new IllegalArgumentException("Index out of bounds");
        }

        ListNode newNode = new ListNode(val);
        newNode.next = prev.next;
        prev.next = newNode;
    }
}

带哨兵节点的情况下，插入节点

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

class LinkedListWithSentinel {
    private ListNode dummy;

    public LinkedListWithSentinel() {
        dummy = new ListNode(-1); // dummy 节点，不存实际数据
    }

    // 在第 index 个位置插入 val（0-based，相对于第一个真实节点）
    public void insert(int index, int val) {
        ListNode prev = dummy;
        for (int i = 0; i < index && prev != null; i++) {
            prev = prev.next;
        }

        if (prev == null) {
            throw new IllegalArgumentException("Index out of bounds");
        }

        ListNode newNode = new ListNode(val);
        newNode.next = prev.next;
        prev.next = newNode;
    }

    public ListNode getHead() {
        return dummy.next; // 返回真实头结点
    }
}

不带哨兵节点的情况下，删除节点

class LinkedListNoSentinel {
    ListNode head;

    // 删除第 index 个节点（0-based）
    public void delete(int index) {
        if (head == null) return;

        if (index == 0) {
            head = head.next;  // 头节点特殊处理
            return;
        }

        ListNode prev = head;
        for (int i = 0; i < index - 1 && prev.next != null; i++) {
            prev = prev.next;
        }

        if (prev.next == null) {
            throw new IllegalArgumentException("Index out of bounds");
        }

        prev.next = prev.next.next;
    }
}

带哨兵节点的情况下，删除节点

class LinkedListWithSentinel {
    private ListNode dummy;

    public LinkedListWithSentinel() {
        dummy = new ListNode(-1);
    }

    // 删除第 index 个节点（0-based）
    public void delete(int index) {
        ListNode prev = dummy;
        for (int i = 0; i < index && prev.next != null; i++) {
            prev = prev.next;
        }

        if (prev.next == null) {
            throw new IllegalArgumentException("Index out of bounds");
        }

        prev.next = prev.next.next;
    }

    public ListNode getHead() {
        return dummy.next;
    }
}

我们从上面的代码例子中不难发现，加入哨兵节点可以不用判断链表为空或者插入/删除的是头节点的情况。省略了烦人的边界条件判断，提高写代码的正确性和简便性。