前言
今天时间紧张，借一道经典面试题简单聊两句吧。
LeetCode 146 - LRU Cache
最近最少使用缓存（LRU Cache）是一种简单而高效的缓存机制，其思想基于局部性原理，在CPU缓存管理、操作系统内存管理以及Redis、Memcached等内存数据库中有非常重要的地位。下面来按照题目要求实现一个最简单的LRU Cache。
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity)Initialize the LRU cache with positive size capacity.int get(int key)Return the value of the key if the key exists, otherwise return -1.void put(int key, int value)Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.Follow up:
Could you do get and put in O(1) time complexity?
分析：
- 什么数据结构能够满足在O(1)时间内存取数据？——哈希表。
- 什么数据结构能够记录元素进入缓存的顺序？——数组或链表。但是为了与上一个条件配合，只有双端链表能满足。
结构如下图所示。
Java代码如下。注意这里采用了头插法，亦即链表头部的元素最新，链表尾部的元素最旧。在执行get/put操作时，如果key对应的元素已经存在，就需要将这个最近使用的元素从链表中移除，再插回头部。如果超过了缓存容量，就从链表尾部淘汰元素。
class LRUCache {
private class ListNode {
private int key;
private int value;
private ListNode prev, next;
public ListNode() {}
public ListNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private Map<Integer, ListNode> container;
private ListNode head, tail;
private int capacity, size;
public LRUCache(int capacity) {
this.container = new HashMap<>();
this.head = this.tail = new ListNode();
head.next = tail;
tail.prev = head;
this.capacity = capacity;
this.size = 0;
}
private void insertNode(ListNode node) {
ListNode head1 = head.next;
head.next = node;
node.prev = head;
node.next = head1;
head1.prev = node;
}
private void deleteNode(ListNode node) {
ListNode nPrev = node.prev, nNext = node.next;
nPrev.next = nNext;
nNext.prev = nPrev;
node.prev = node.next = null;
}
public int get(int key) {
ListNode data = container.get(key);
if (data == null) {
return -1;
}
deleteNode(data);
insertNode(data);
return data.value;
}
public void put(int key, int value) {
ListNode data = container.get(key);
if (data == null) {
if (size < capacity) {
size++;
} else {
ListNode leastRecent = tail.prev;
container.remove(leastRecent.key);
deleteNode(leastRecent);
}
ListNode newNode = new ListNode(key, value);
insertNode(newNode);
container.put(key, newNode);
} else {
data.value = value;
deleteNode(data);
insertNode(data);
}
}
}
解法二：LinkedHashMap
如果不想手写双端链表怎么办？我们当然可以换用LinkedList，不过更加简单的方式是直接借助Java集合框架中的LinkedHashMap。LinkedHashMap就是在普通HashMap Entry的基础上加了前向指针和后向指针，所以能够按顺序组织键值对。其结构图如下所示。
注意其构造方法中的accessOrder参数。如果accessOrder为false，则保持元素的插入顺序。如果accessOrder为true，则按照访问顺序重新整理元素，最近被访问到的元素会放在双端链表的尾部。更方便的是，通过覆写其removeEldestEntry()方法，就可以在满足特定的条件时自动删除最久未被使用的元素，其他事情交给LinkedHashMap本身去做。
代码如下，同样能AC。
import java.util.LinkedHashMap;
class LRUCache extends LinkedHashMap<Integer, Integer> {
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
}
LinkedHashMap的源码不难，看官可自行参考。
如何保证线程安全？
对于解法二，换用线程安全的ConcurrentLinkedHashMap即可。如果仍然要求我们自己来实现，有两种思路：
- 将普通的HashMap换成ConcurrentHashMap，双端链表换成ConcurrentLinkedQueue（此时链表内部维护的是key的访问顺序）；
- 用可重入读写锁ReentrantReadWriteLock来保证put/get操作的线程安全性。
Redis中的LRU
Redis的最大用途之一就是作为缓存，所以它提供了相当完备的LRU算法实现。需要注意的是，由于Redis内部可能会维护海量的key，用类似LinkedHashMap的方法将所有键值都串在一起显然是不现实的。所以Redis采用了一种定期近似抽样的方法，根据LRU时钟分辨率REDIS_LRU_CLOCK_RESOLUTION确定抽样周期，每次抽取maxmemory-samples（默认值为5）个key，并淘汰掉这些key中最久未被访问的那一个。显然，增大此参数的值会增大LRU的精准度，但同时也会增大内存占用。
Redis文档中Using Redis as an LRU Cache一节对此机制有非常详细的讲解，看官可自行参考，不再废话了。
The End
最近昼夜温差大，大家注意身体。
晚安咯。
网友评论