腾讯一面-LRU缓存

为了设计一个满足LRU（最近最少使用）缓存约束的数据结构，我们可以使用哈希表（HashMap）来存储键值对，以便在O(1)时间复杂度内访问任意键。同时，我们还需要一个双向链表（Doubly Linked List）来保持键的使用顺序，以便在O(1)时间复杂度内执行插入和删除操作。

我们使用了一个ListNode类来表示双向链表中的节点，每个节点包含键、值、指向前一个节点的指针和指向后一个节点的指针。LRUCache类包含了容量、哈希表、双向链表的头节点和尾节点。

get方法首先检查键是否存在于哈希表中。如果存在，则将对应的节点移到双向链表的头部，并返回节点的值。如果不存在，则返回-1。

put方法首先检查键是否存在于哈希表中。如果不存在，则创建一个新的节点，将其添加到哈希表和双向链表的头部，并检查是否超出了容量。如果超出了容量，则删除双向链表尾部的节点，并从哈希表中移除对应的键值对。如果键已经存在，则更新节点的值，并将其移到双向链表的头部。

addToHead、removeNode、moveToHead和removeTail是辅助方法，用于在双向链表中添加节点、删除节点、将节点移到头部和删除尾部节点。

代码如下：

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

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

    ListNode(int k, int v) {
        key = k;
        value = v;
    }
}

class LRUCache {
    private int capacity;
    private Map<Integer, ListNode> map;
    private ListNode head;
    private ListNode tail;

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

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

    public void put(int key, int value) {
        ListNode node = map.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            ListNode newNode = new ListNode(key, value);
            // 添加进哈希表
            map.put(key, newNode);
            // 添加进双向链表头部
            addToHead(newNode);
            // 如果超出容量，删除双向链表尾部节点
            if (map.size() > capacity) {
                ListNode tail = removeTail();
                map.remove(tail.key);
            }
        } else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(ListNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(ListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(ListNode node) {
        removeNode(node);
        addToHead(node);
    }

    private ListNode removeTail() {
        ListNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

addToHead(ListNode node)

这个方法用于将一个新的节点添加到双向链表的头部。

1. 设置新节点的prev指针：新节点的prev指针指向当前的头节点（head）。

2. 设置新节点的next指针：新节点的next指针指向头节点的下一个节点（head.next）。

3. 更新头节点下一个节点的prev指针：因为新节点被插入到了头节点和头节点的下一个节点之间，所以需要更新头节点的下一个节点的prev指针，使其指向新节点。

4. 更新头节点的next指针：最后，更新头节点的next指针，使其指向新节点，这样新节点就成为了双向链表的新头节点。

removeNode(ListNode node)

这个方法用于从双向链表中移除一个节点。

1. 更新被移除节点前一个节点的next指针：将被移除节点的prev指针所指向的节点的next指针更新为被移除节点的next指针，这样前一个节点就“跳过”了被移除的节点。

2. 更新被移除节点后一个节点的prev指针：将被移除节点的next指针所指向的节点的prev指针更新为被移除节点的prev指针，这样后一个节点也“跳过”了被移除的节点。

moveToHead(ListNode node)

这个方法用于将一个已存在的节点从双向链表的当前位置移动到头部。

1. 调用removeNode方法：首先，使用removeNode方法将被移动的节点从双向链表中移除。

2. 调用addToHead方法：然后，使用addToHead方法将被移除的节点（现在是游离的）添加到双向链表的头部。

removeTail()

这个方法用于移除双向链表的尾部节点，并返回该节点。

1. 获取尾部节点的前一个节点：由于尾节点（tail）的prev指针指向了双向链表的最后一个实际存储数据的节点，所以tail.prev就是我们要移除的尾部节点。

2. 调用removeNode方法：使用removeNode方法移除尾部节点。

3. 返回被移除的节点：返回被移除的尾部节点。

注意：在removeTail方法中，实际上并没有直接更新tail指针，因为按照LRU缓存的逻辑，尾部节点在移除后通常不需要再被引用。然而，如果出于某种原因需要保持tail指针的有效性（比如在某些实现中，你可能想要保持一个有效的尾部引用以便快速添加新节点到尾部），你可能需要在移除尾部节点后更新tail指针，使其指向新的尾部节点（即原尾部节点的前一个节点）。但在你提供的代码中，这个步骤是省略的，因为tail节点始终是一个哑节点（dummy node），不存储实际数据。