力扣题目：146. LRU 缓存
LRU 是什么？
最近最少使用算法。一个队列，将最近使用的元素放到队列的头部，当队列长度不够时，移除队列的最后一个元素，也就是最近最少使用的元素。
解法 1：继承 LinkedHashMap
投机取巧解法（最好还是自己实现），利用 Java 的 LinkedHashMap 已经实现好的方法，所以直接继承 LinkedHashMap 为父类即可。
有兴趣可以自己阅读 LinkedHashMap 源码。重点关注这三个方法：
-
afterNodeAccess()：访问元素之后，将元素放到双向链表的尾部 -
afterNodeRemoval()：删除元素之后，同时将元素也从双向链表中删除 -
afterNodeInsertion()：插入元素之后，是否需要移除最近最少使用的元素
/**
* 继承 LinkedHashMap
*/
class LRUCache extends LinkedHashMap {
/**
* 容量
*/
private int capacity;
/**
* 调用父类的构造方法
* capacity：容量
* 0.75F：负载因子
* true：开启 LRU 缓存算法
*/
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
/**
* 获取元素，调用父类的构造方法
* 原理：
* （1）首先将这个元素从队列中移除
* （2）然后再将这个元素添加到队列的头部
*/
public int get(int key) {
return (int) super.getOrDefault(key, -1);
}
/**
* 得到元素，调用父类的构造方法
* 原理：
* （1）首先判断 key 所代表的元素是否已经在队列中
* （2）如果在队列中，则直接覆盖元素的值即可
* （3）覆盖之后则从队列中移除，然后再添加到队列头部
* （4）此时操作完成
* （5）如果不在队列中，则判断容量是否足够
* （6）如果容量足够，则直接添加到队列头部，此时操作完成
* （7）如果容量不足够，则移除队列最后一个元素
* （8）并且将要添加的元素添加到队列的头部，此时操作完成
*/
public void put(int key, int value) {
super.put(key, value);
}
/**
* 移除元素条件方法，因为在 LinkedHashMap 中是空方法
* 所以我们需要重写方法，定义自己的逻辑
* 这里就是当容量不够时进行移除元素
*/
@Override
public boolean removeEldestEntry(Map.Entry eldest) {
return super.size() > capacity;
}
}
解法 2：哈希表 + 双向链表
很重要，面试官需要你写出来的是这个，要能够手写！
class LRUCache {
/**
* 双向链表长度
*/
private int size;
/**
* 最大容量
*/
private int capacity;
/**
* 哈希表，存储数据
*/
private Map<Integer, DoubleLinkedNode> cache;
/**
* 双向链表头节点，不存储任何值，标识作用
*/
private DoubleLinkedNode head;
/**
* 双向链表尾节点，不存储任何值，标识作用
*/
private DoubleLinkedNode tail;
/**
* 构造方法
*/
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
this.cache = new HashMap<>();
this.head = new DoubleLinkedNode();
this.tail = new DoubleLinkedNode();
head.next = tail;
tail.prev = head;
}
/**
* 获取元素
*/
public int get(int key) {
DoubleLinkedNode node = this.cache.get(key);
// 如果要获取的节点不存在
if (node == null) {
return -1;
}
// 移动到双向链表头部
moveToHead(node);
// 返回值
return node.value;
}
/**
* 添加元素
*/
public void put(int key, int value) {
DoubleLinkedNode node = cache.get(key);
// 如果元素不存在
if (node == null) {
node = new DoubleLinkedNode(key, value);
// 添加到哈希表中
cache.put(key, node);
// 双向链表长度加 1
size++;
// 添加到双向链表头部
addToHead(node);
// 如果长度大于容量，说明要删除元素了
if (size > capacity) {
// 从双向链表中删除最后一个元素
DoubleLinkedNode tail = removeTail();
// 同时从哈希表中删除对应的元素
cache.remove(tail.key);
// 长度减 1
size--;
}
// 如果元素存在
} else {
// 修改值
node.value = value;
// 移动到双向链表头部
moveToHead(node);
}
}
/**
* 自己构造一个双向链表节点
*/
class DoubleLinkedNode {
/**
* 键
*/
int key;
/**
* 值
*/
int value;
/**
* 前驱节点
*/
DoubleLinkedNode prev;
/**
* 后继节点
*/
DoubleLinkedNode next;
/**
* 构造方法
*/
public DoubleLinkedNode() {}
public DoubleLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
/**
* 添加一个节点到双向链表头部
*/
private void addToHead(DoubleLinkedNode node) {
node.next = head.next;
node.prev = head;
node.next.prev = node;
head.next = node;
}
/**
* 从双向链表中删除一个节点
*/
private void removeNode(DoubleLinkedNode node) {
node.next.prev = node.prev;
node.prev.next = node.next;
node.prev = null;
node.next = null;
}
/**
* 将双向链表中一个节点移动双向链表到头部
*/
private void moveToHead(DoubleLinkedNode node) {
removeNode(node);
addToHead(node);
}
/**
* 移除双向链表中最后一个节点
*/
private DoubleLinkedNode removeTail() {
DoubleLinkedNode node = this.tail.prev;
removeNode(node);
return node;
}
}