什么是LRU缓存?
LRU（Least Recently Used）是最近最少使用算法，是操作系统中用于分页置换的算法，如果要向内存中添加分页，并且内存分页已满的情况下，就选出最近一段时间最不常用的分页进行置换（例如将最不常用的分页暂时放到磁盘，这时内存就有一个空闲分页，将新增分页放过来即可）。
题目
链接：leetcode.146. LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现
LRUCache类：
以 正整数 作为容量
LRUCache(int capacity)capacity初始化 LRU 缓存如果关键字
int get(int key)key存在于缓存中，则返回关键字的值，否则返回-1。如果关键字
void put(int key, int value)key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。函数
get和put必须以O(1)的平均时间复杂度运行。
分析
一、 容器内容的设计
我们可以用一个容器对数据进行缓存，第一个元素表示最近最不经常使用，最后一个元素表示最近最经常使用，从前往后依次过渡
二、 数据结构的选型
① 使用数组
假设将内容全部用数组进行缓存
现在使用元素2，那么应该将2移到尾部，3、4、5全部向前移动。这样查询的时间复杂度为O(1)，移动的时间复杂度为O(n)。
那么题目要求的get时间复杂度就为O(n)，put时间复杂度为O(n)。显然不能使用数组。
② 使用链表
如果使用元素2，那么需要找到元素2，然后将元素2放到尾部即可。这样查询的时间复杂度为O(n)，移动的时间复杂度为O(1)，
显然对于查询操作我们可以使用哈希去优化，使得查询的时间复杂度为O(1)
③ 哈希+ 链表
这样查询2只需要通过key映射，查询效率为O(1)，将2移动到链表尾部，1指向3即可，移动效率为O(1)，完美!
但是这里有个问题，我们通过key定位到元素2时，如何获取2前面的元素？
聪明的小伙伴已经想出来了，答案就是将单链表变为双向链表
④ 哈希 + 双向链表
这样不管是查询还是移动，复杂度都是O(1)
解答
① 设计双向链表节点结构
class ListNode {// 节点前驱ListNode pre;// 节点后继ListNode next;// 哈希中的keyint key;// 数据域，记录缓存内容int val;// 构造函数public ListNode() {}public ListNode(int key, int val) {this.key = key;this.val = val;}
}这里节点中为什么要设计key呢？因为如果添加元素时缓存区已满，就需要删除链表中第一个元素（最近最不常使用的元素），同时还要在哈希中移除，所以需要记录这个数据的key
② 使用带假节点的双向链表
为什么使用假节点？原因很简单，操作方便。对于一个单链表，添加元素时要判断头指针是否为空，删除元素时需要判断是不是头部元素，如果是头部元素，就需要将头指针向后移，但是使用假节点之后便不再需要进行这些操作。结构如下：
可以看出，对于带有假节点的链表，head后邻节点是有效的第一个节点（在不是rear的情况下），rear前邻节点是最后一个有效节点（在不是head的情况下）
③ 初始化LRU容器
// 头部指针
private ListNode head;
// 尾部指针
private ListNode rear;
// 哈希表
private HashMap<Integer, ListNode> hash = new HashMap<>();
// 缓存容量
private final int capacity;public LRUCache(int capacity) {// 缓存容量this.capacity = capacity;// 初始化双向链表// 头部假节点this.head = new ListNode();// 尾部假节点this.rear = new ListNode();// 首尾相连head.next = rear;rear.pre = head;
}目前为止，双向链表还是一个空链表
④ 获取缓存元素
思路如下：
-
元素不存在，直接返回-1
-
元素存在
-
将元素移到链表尾部
-
返回元素
-
代码实现：
public int get(int key) {// 从哈希表中查找节点ListNode node = hash.get(key);// 节点不存在，返回-1if (node == null) {return -1;}// 节点存在，将节点移动到链表尾部moveToLast(node);// 返回缓存数据return node.val;
}⑤ 放置缓存元素
思路如下：
-
元素不存在
-
如果缓存已满，删除链表第一个元素
-
添加新节点到链表尾部
-
-
元素存在
-
将元素移动到链表尾部
-
更节点数据
-
代码实现：
public void put(int key, int value) {// 判断key是否存在ListNode valueNode = hash.get(key);// 元素不存在if (valueNode == null) {// 判断缓存是否到达上限if (hash.size() == capacity) {// 删除最不经常使用的节点ListNode firstNode = head.next;removeNode(firstNode);}// 添加新节点到链表尾部addNodeToBack(new ListNode(key, value));} else {// 节点存在，将节点移到尾部，并修改节点值moveToLast(valueNode);valueNode.val = value;}
}⑥ 操作节点函数的封装
将节点放置到尾部
private void moveToLast(ListNode node) {// 如果节点在链表中，那么更新他的前驱与后继的指针指向if (node.pre != null && node.next != null) {ListNode pre = node.pre;ListNode next = node.next;pre.next = next;next.pre = pre;}// 将节点插入到尾部ListNode rearPre = rear.pre;rearPre.next = node;node.pre = rearPre;node.next = rear;rear.pre = node;
}添加节点到尾部并放入哈希表
private void addNodeToBack(ListNode newNode) {// 将节点移动到尾部moveToLast(newNode);// 将节点映射信息放入哈希表hash.put(newNode.key, newNode);
}删除节点
private void removeNode(ListNode node) {// 移除哈希表中存储的信息hash.remove(node.key);// 移除链表中的节点ListNode pre = node.pre;ListNode next = node.next;pre.next = next;next.pre = pre;
}代码实现
class LRUCache {private static class ListNode {public ListNode pre;public ListNode next;public int key;public int val;public ListNode() {}public ListNode(int key, int val) {this.key = key;this.val = val;}}private ListNode head;private ListNode rear;private HashMap<Integer, ListNode> hash = new HashMap<>();private final int capacity;public LRUCache(int capacity) {this.capacity = capacity;// 初始化双向链表this.head = new ListNode();this.rear = new ListNode();head.next = rear;rear.pre = head;}public int get(int key) {// 从哈希表中查找节点ListNode node = hash.get(key);// 节点不存在，返回-1if (node == null) {return -1;}// 节点存在，将节点移动到链表尾部moveToLast(node);// 返回缓存数据return node.val;}public void put(int key, int value) {// 判断key是否存在ListNode valueNode = hash.get(key);// 元素不存在if (valueNode == null) {// 判断缓存是否到达上限if (hash.size() == capacity) {// 删除最不经常使用的节点ListNode firstNode = head.next;removeNode(firstNode);}// 添加新节点到链表尾部addNodeToBack(new ListNode(key, value));} else {// 节点存在，将节点移到尾部，并修改节点值moveToLast(valueNode);valueNode.val = value;}}private void addNodeToBack(ListNode newNode) {moveToLast(newNode);hash.put(newNode.key, newNode);}private void moveToLast(ListNode node) {// 如果节点在链表中，那么更新他的前驱与后继的指针指向if (node.pre != null && node.next != null) {ListNode pre = node.pre;ListNode next = node.next;pre.next = next;next.pre = pre;}// 将节点插入到尾部ListNode rearPre = rear.pre;rearPre.next = node;node.pre = rearPre;node.next = rear;rear.pre = node;}private void removeNode(ListNode node) {hash.remove(node.key);ListNode pre = node.pre;ListNode next = node.next;pre.next = next;next.pre = pre;}
}