如何实现LRU缓存淘汰算法

实现LRU缓存淘汰算法的一种常用方法是使用哈希表和双向链表结合实现。具体实现步骤如下：

1. 使用一个哈希表来存储缓存中的键值对，其中键为缓存的键，值为该键对应的节点在双向链表中的指针。

2. 使用一个双向链表来存储缓存中的键值对，每个节点包含该节点对应的键、值以及前驱和后继指针。

3. 当有新的键值对被访问时，首先在哈希表中查找该键是否存在，如果存在，则将该键所对应的节点移到链表头部，表示最近被访问过；如果不存在，则在哈希表和链表中分别添加该键值对以及节点，并将该节点插入到链表头部。

4. 当缓存空间不足时，淘汰链表尾部的节点，并在哈希表中删除对应的键值对。

下面是一个Python实现的LRU缓存淘汰算法的代码示例：

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add(node)
            return node.val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self.cache[key] = node
        self._add(node)
        if len(self.cache) > self.capacity:
            node = self.head.next
            self._remove(node)
            del self.cache[node.key]

    def _add(self, node):
        p = self.tail.prev
        p.next = node
        node.prev = p
        node.next = self.tail
        self.tail.prev = node

    def _remove(self, node):
        p = node.prev
        n = node.next
        p.next = n
        n.prev = p

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

在这个实现中，我们使用了一个双向链表来维护缓存中节点的顺序，其中head和tail分别是链表的头节点和尾节点。同时，我们使用了一个哈希表来查询节点是否存在以及快速删除节点。当有新的节点被访问时，我们将其移到链表头部，并且当缓存空间不足时，我们淘汰链表尾部的节点。