最常见面试算法之 LRU 缓存机制
一、题目描述
运用你所掌握的数据结构，设计和实现一个 LRU（最近最少使用）缓存机制。它应该支持以下操作：
- 获取数据 get(key)：如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
- 写入数据 put(key, value) ：如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶：
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例：
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4二、题解
LRU 是 Least Recently Used 的缩写，这种算法认为最近使用的数据是热门数据，下一次很大概率将会再次被使用。而最近很少被使用的数据，很大概率下一次不再用到。当缓存容量满的时候，优先淘汰最近很少使用的数据。
实现 LRU 缓存的常用方法是使用有界队列。实现 LRU 的关键是将所有最近使用的数据放在队列的开头。在每次插入之前，我们检查队列是否已满。如果队列已满，我们将删除其最后一个元素，并将新节点插入队列的开头。如果队列未满，我们只需将数据添加到队列的开头。
为了方便理解，我们借助前面的示例来演示一下上述的处理流程：
当我们想要删除节点或更新节点时，我们需要快速找到该节点在队列中的位置。因此，可以使用 HashMap 支持快速查找操作。在这种情况下，get 操作的时间复杂度为 O(1)。
由于我们还需要有效地删除队列中间的节点，因此需要一个双向链表。在两种情况下，我们需要删除队列中间的节点：
- 客户端指定需要删除一个节点。
- 节点已更新，需要将其删除并插入队列的开头。
通过使用双向链表，一旦我们通过 HashMap 定位了要删除的节点的位置，就可以在 O(1) 时间从队列中删除该节点。
当我们需要更新键的缓存时，我们首先使用 HashMap 定位相应的节点，更新值，然后从队列中删除该节点，并将该节点放置在 Doubly Linked List 的开头。
LRU 算法 Java 实现
下面我们先用 Java 来实现 LRU 缓存算法。
首先定义个双向链表的节点：
class Node {
int key;
int value;
Node pre;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}每次执行操作时，我们都使用 HashMap 定位节点在队列中的位置，然后删除该节点并将其插入链表头。因此最好定义两个方法：
- remove(node)：从双向链表中删除指定 node 节点；
- setHead(node)：把指定 node 节点插入到双向链表表头。
定义 LRUCache 类
public class LRUCache {
int capacity;
Map<Integer, Node> map = new HashMap<>();
Node head = null;
Node tail = null;
public LRUCache(int capacity) {
this.capacity = capacity;
}
/**
* 根据指定key查找其对应的值
*
* @param key
* @return
*/
public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
remove(node);
setHead(node);
return node.value;
}
return -1;
}
/**
* 移除指定n节点
*
* @param n
*/
public void remove(Node n) {
if (n.pre != null) { // 非头节点
n.pre.next = n.next;
} else { // 头节点
head = n.next;
}
if (n.next != null) { // 非尾节点
n.next.pre = n.pre;
} else { // 尾节点
tail = n.pre;
}
}
/**
* 设置双向链表的头节点
*
* @param n
*/
public void setHead(Node n) {
n.next = head;
n.pre = null;
if (head != null)
head.pre = n;
head = n;
if (tail == null)
tail = head;
}
/**
* 把指定key和value添加到缓存中
*
* @param key
* @param value
*/
public void put(int key, int value) {
// key对应的节点已存在，先更新节点值，然后将其删除并插入到链表头
if (map.containsKey(key)) {
Node old = map.get(key);
old.value = value;
remove(old);
setHead(old);
} else {
// 基于key和value创建新的节点
Node created = new Node(key, value);
// 若链表已满，则先移除链表尾元素，然后再把新元素添加到链表头
if (map.size() >= capacity) {
map.remove(tail.key);
remove(tail);
setHead(created);
} else {
setHead(created);
}
map.put(key, created);
}
}
}定义 LRUCacheDemo 测试类
public class LRUCacheDemo {
public static void main(String[] args) {
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println("cache.get(1): " + cache.get(1));
cache.put(3, 3);
System.out.println("cache.get(2): " + cache.get(2));
System.out.println("cache.get(3): " + cache.get(3));
}
}以上代码成功运行后，输出以下结果：
cache.get(1): 1
cache.get(2): -1
cache.get(3): 3三、参考资源
欢迎小伙伴们订阅前端全栈修仙之路，及时阅读 Angular、TypeScript、Node.js/Java和Spring技术栈最新文章。