Leetcode题解（5）：LRU与LinkedHashMap
为了记录访问顺序，我们可以使用一个双向链表，首节点为最近最少访问的数据，尾节点为最近访问的数据。为了快速获取值，我们可以额外使用一个 $Map$ 存储键值映射。
public class LRUCache {
private int capacity;
private int size;
private Map<Integer, Node> map;
private Node head;
private Node tail;
public LRUCache(int capacity) {
this.capacity = capacity;
size = 0;
map = new HashMap<>();
}
public int get(int key) {
Node node = getNode(key);
return node == null ? -1 : node.val;
}
public void put(int key, int value) {
Node node = getNode(key);
if (node != null) {
node.val = value;
return;
}
if (++size > capacity) removeHead();
node = new Node(key, value);
putToTail(node);
map.put(key, node);
}
private Node getNode(int key) {
Node node = map.get(key);
if (node == null) return null;
putToTail(node);
return node;
}
private void removeHead() {
map.remove(head.key);
if (head == tail) head = tail = null;
else {
head = head.next;
head.prev = null;
}
--size;
}
private void putToTail(Node node) {
if (head == null) {
head = tail = node;
return;
} else if (node == tail)
return;
if (head == node) head = head.next;
Node p = node.prev, n = node.next;
if (n != null) n.prev = p;
if (p != null) p.next = n;
tail.next = node;
node.prev = tail;
node.next = null;
tail = node;
}
private class Node {
int key;
int val;
Node prev;
Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
}
讲完了 $LRUCache$ 之后就可以讲讲 $LRUCache$ 与 $LinkedHashMap$ 之间的关系了。默认情况下 $LinkedHashMap$ 是一种保存了值写入顺序的 $HashMap$ ，扩展了 $HashMap$ ，也就是说底层与 $HashMap$ 相同。而写入顺序是通过一个双向链表存储的，在每次写入和删除时更新。
可以发现 $LinkedHashMap$ 里面有一个特殊的构造函数：
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
$accessOrder$ 是一个标志位，当它设置为 $true$ 时，允许我们通过访问顺序改变链表。以 $get$ 方法为例：
public V get(Object key) {
Node<K, V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
可以发现在每次 $get$ 之后，都会判断 $accessOrder$ ，然后调用 $afterNodeAccess$ 方法。后者的实现如下：
void afterNodeAccess(Node<K, V> e) {
LinkedHashMap.Entry<K, V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K, V> p =
(LinkedHashMap.Entry<K, V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
可以看到逻辑很简单，就是将节点 $p$ 置于链表尾部。而这个节点 $p$ 是我们刚刚通过 $get$ 方法尝试访问的节点 $e$ 转化过来的，也就是说这个方法实际上是将最近访问的节点放到链表尾部。除了 $get$ 方法之外，$put$ 方法和 $replace$ 方法也会调用该方法。
除了这个方法外，$put$ 方法在添加键值对时，还会调用另一个方法：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
/*
将值插入表内
*/
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
$LinkedHashMap$ 本身并没有重写 $put$ 方法，也就是说它调用的是 $HashMap$ 中的版本。而在 $HashMap$ 里，$afterNodeInsertion$ 方法是空实现，也就是不执行任何操作。$LinkedHashMap$ 重写了该方法：
void afterNodeInsertion(boolean evict) {
LinkedHashMap.Entry<K, V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
方法实现很简单，只要 $evict = true$ 、链表非空并且 $removeEldestEntry$ 方法为 $true$ ，就移除首节点，也就是最近最少访问的节点。而 $removeEldestEntry$ 方法的实现如下：
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return false;
}
可以发现默认返回 $false$ ，也就是不移除节点。所以如果要使用 $LinkedHashMap$ 实现 $LRUCache$ ，就需要重写该方法。而除了 $afterNodeInsertion$ 和 $afterNodeAccess$ 方法之外，还有一个用于移除时的 $afterNodeRemoval$ 方法，实现逻辑大致相同，在此就不赘述。
使用 $LinkedHashMap$ 实现 $LRUCache$ 的方法如下：
public class LRUCache extends LinkedHashMap<Integer, Integer> {
private int capacity;
public LRUCache(int capacity) {
super(16, 0.75f, true);
this.capacity = capacity;
}
public int get(int key) {
return getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}