面试高频考题——手撸一个 LRU 算法！

Doocs开源社区

共 3238字，需浏览 7分钟

· 2021-05-16

今天给大家讲一道面试中经常容易遇到的一道题：“手写一个 LRU 算法”。

LRU 就是 Least Recently Used 的缩写，翻译过来就是“最近最少使用”。 也就是说 LRU 算法会将最近最少用的缓存移除，让给最新使用的缓存。这是非常常见的一个缓存淘汰策略。

利用好 LRU 算法，我们能够提高对热点数据的缓存效率，进而提升缓存服务的内存使用率。

那么如何实现呢？

其实，通过缓存的 key 获取其对应的缓存，我们应该能想到用哈希表来实现，毕竟这是一个键值对结构，可以在 O(1) 时间内获取 key 对应的缓存值。

但是，哈希表本身是无序的，因此，我们还需要一个类似于队列的数据结构来记录访问的先后顺序，将最近访问的数据放在头部（如下图），移除最后一项数据（最旧），我们可以用双向链表来实现数据的增删以及顺序的调整。

因此，我们结合“哈希表 + 双向链表”来实现 LRU 算法。其中：

•双向链表按照被使用的顺序存储 kv 键值对，靠近头部的 kv 键值对是最近使用的，而靠近尾部的键值对是最久未使用的。•哈希表通过缓存的 key 映射到双向链表中的位置。我们可以在 O(1) 时间内定位到缓存的 key 所对应的 value 在链表中的位置。

对于 get 操作，判断 key 是否存在哈希表中：

•若不存在，返回 -1。•若存在，则 key 对应的节点 node 是最近使用的节点。将该节点移动到双向链表的头部，最后返回该节点的值即可。

对于 put 操作，同样先判断 key 是否存在哈希表中：

•若不存在，则创建一个新的 node 节点，放入哈希表中。然后在双向链表的头部添加该节点。接着判断双向链表节点数是否超过 capacity。若超过，则删除双向链表的尾部节点，并且删除哈希表中对应的项。•若存在，则更新 node 节点的值，然后该节点移动到双向链表的头部。

双向链表节点（哈希表的 value）的结构如下：

class Node {    int key;    int value;    Node prev;    Node next;    Node() {    }    Node(int key, int value) {        this.key = key;        this.value = value;    }}

你可能会问，哈希表的 value 为何还要存放 key？

这是因为，双向链表有一个删除尾节点的操作。我们定位到双向链表的尾节点，在链表中删除之后，还要找到该尾节点在哈希表中的位置，因此需要根据 value 中存放的 key，定位到哈希表的数据项，然后将其删除。

以下是 Java 版本代码的完整实现。

class LRUCache {    class Node {        int key;        int value;        Node prev;        Node next;        Node() {        }        Node(int key, int value) {            this.key = key;            this.value = value;        }    }    private int size;    private int capacity;    private Map<Integer, Node> cache;    /* 虚拟头节点 */    private Node head;    /* 虚拟尾节点 */    private Node tail;    public LRUCache(int capacity) {        this.size = 0;        this.capacity = capacity;        cache = new HashMap<>();        head = new Node();        tail = new Node();        head.next = tail;        tail.prev = head;    }    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);            // 将最近新增的数据放到头部            addToHead(newNode);            ++size;            // 若数据量超过设定的最大容量，移除尾部（最不常访问）的节点数据            if (size > capacity) {                Node tail = removeTail();                // 缓存淘汰，移除尾部节点数据                cache.remove(tail.key);                --size;            }        } else {            node.value = value;            moveToHead(node);        }    }    private void moveToHead(Node node) {        removeNode(node);        addToHead(node);    }    private void removeNode(Node node) {        node.prev.next = node.next;        node.next.prev = node.prev;    }    private void addToHead(Node node) {        node.next = head.next;        head.next = node;        node.next.prev = node;        node.prev = head;    }    private Node removeTail() {        Node node = tail.prev;        removeNode(node);        return node;    }}