题目链接: https://leetcode.cn/problems/lru-cache/
1.1 LRU 算法描述
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。
也就是说：我没认为最近使用过的数据是 有用的，而那些很久都没有使用过的数据是 无用的，在缓存容量不够的时候，就会删去 无用的数据，这样就可以为新加入的 有用的 数据提供空间。
题目要求：
首先需要接收一个 capacity 参数最为缓存的容量，然后实现put(key, val) 方法存入键值对、实现 get(key) 方法获取 key 对应的 val，如果 key 不存在则返回 -1。
注意：题目要求 get 函数和 put 函数的时间复杂度都是1。我们先来看看按照题目的意思大概的工作流程。
1.2 LRU 算法分析
题目要求 get 函数和 put 函数的时间复杂度都是1，这就指明了需要用的 Map（哈希表）去实现元素的存储和访问。
题目要求淘汰最久没有被使用的元素，说明元素之间是按照一定的顺序存储的。我们可以用双向链表来存储数据。每次访问 缓存 中的某个 key，需要将这个元素变为最近使用的，也就是说 缓存 要支持在任意位置快速插入和删除元素。双向链表也可以很好的满足这个需求（删除一个节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接查找前驱，保证操作的时间复杂度 O(1)）。
所以LRU缓存的结构是由 哈希表 和 双向链表构成的。
1.3 代码实现
完整的代码实现：
class LRUCache {
private final Map cache;
private final DoubleLikedTable doubleLikedTable;
private final int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
cache = new HashMap<>();
doubleLikedTable = new DoubleLikedTable();
}
public int get(int key) {
if (cache.containsKey(key)) {
Node ans = cache.get(key);
doubleLikedTable.delete(ans);
doubleLikedTable.add(ans);
return ans.value;
}
return -1;
}
public void put(int key, int value) {
Node cur = cache.get(key);
if (cur == null) {
cur = new Node(key, value);
if (doubleLikedTable.size >= capacity) {
Node node = doubleLikedTable.deleteHead();
cache.remove(node.key);
}
} else {
cur.value = value;
doubleLikedTable.delete(cur);
}
doubleLikedTable.add(cur);
cache.put(key, cur);
}
// 链表头部的元素是最久没有使用的
class DoubleLikedTable {
Node head, tail;
int size;
public DoubleLikedTable() {
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
size = 0;
}
// 1. 添加元素 (队尾添加元素)
public void add(Node cur) {
if (cur != null) {
cur.next = tail;
cur.prev = tail.prev;
tail.prev.next = cur;
tail.prev = cur;
size++;
}
}
// 2. 删除元素
public void delete(Node cur) {
if (cur != null) {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
size--;
}
}
// 3. 删除队首的元素
public Node deleteHead() {
Node headEle = head.next;
delete(head.next);
return headEle;
}
// 3. 返回长度
public int getSize() {
return size;
}
}
class Node {
public int key, value;
public Node next, prev;
public Node() {
}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
}
力扣运行结果：
实现分析：
首先是双向链表的结点类：这里没有用 private 和 geter/seter 封装代码是为了简化代码。
class Node {
public int key, value;
// next 指向下一个结点，prev指向上一个结点
public Node next, prev;
public Node() {
}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
下面是双向链表的实现类：首先定义2个空结点 head、tail。head的next指向头结点，tail的prev指向尾结点。
// 链表头部的元素是最久没有使用的
class DoubleLikedTable {
Node head, tail;
int size;
public DoubleLikedTable() {
head = new Node();
tail = new Node();
// head的next指向头结点，tail的prev指向尾结点。
head.next = tail;
tail.prev = head;
// 初始化链表的长度为0
size = 0;
}
// 1. 添加元素 (队尾添加元素)
public void add(Node cur) {
cur.next = tail;
cur.prev = tail.prev;
tail.prev.next = cur;
tail.prev = cur;
size++;
}
// 2. 删除元素
public void delete(Node cur) {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
cur.next = null;
cur.prev = null;
size--;
}
// 3. 删除队首的元素，并返回被删除的元素
public Node deleteHead() {
// head.next 指向的就是队首的元素
Node headEle = head.next;
delete(head.next);
return headEle;
}
// 3. 返回长度
public int getSize() {
return size;
}
}
- 添加元素 (队尾添加元素)
// 1. 添加元素 (队尾添加元素)
public void add(Node cur) {
cur.next = tail;
cur.prev = tail.prev;
tail.prev.next = cur;
tail.prev = cur;
size++;
}
- 删除元素
// 2. 删除元素
public void delete(Node cur) {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
cur.next = null;
cur.prev = null;
size--;
}
- 初始化缓存
class LRUCache {
private final Map cache;
private final DoubleLikedTable doubleLikedTable;
private final int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
cache = new HashMap<>();
doubleLikedTable = new DoubleLikedTable();
}
}
- 实现 get 方法
- 如果缓存里面不存在指定的元素，返回 -1。
- 如果缓存里面存在指定的元素，先在链表里面删去该元素，然后再次添加（保证刚刚访问的元素在链表的末尾），然后返回结果即可。
public int get(int key) {
if (cache.containsKey(key)) {
Node ans = cache.get(key);
doubleLikedTable.delete(ans);
doubleLikedTable.add(ans);
return ans.value;
}
return -1;
}
- 实现 put 方法
- 如果缓存里面不存在该元素cur == null)， 则新建一个结点。如果链表长度超过缓存容量，则删去链表的头结点，并从缓存中删除刚刚删去的头结点相关的数据。
- 如果缓存里面存在该元素，则更新缓存的值，并把新加的结点放在链表的尾部（doubleLikedTable.delete(cur); doubleLikedTable.add(cur);）
public void put(int key, int value) {
Node cur = cache.get(key);
if (cur == null) {
cur = new Node(key, value);
if (doubleLikedTable.size >= capacity) {
Node node = doubleLikedTable.deleteHead();
cache.remove(node.key);
}
} else {
cur.value = value;
doubleLikedTable.delete(cur);
}
doubleLikedTable.add(cur);
cache.put(key, cur);
}
