今天给大家讲一道面试中经常容易遇到的一道题：“手写一个 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; }}
