146. LRU缓存机制
程序员文章站
2022-03-24 14:13:40
...
题目：
题解：
1. 题解一：使用LinkedHashMap实现
2. 题解二：使用双向链表结构+HashMap实现
0. 解题思路：
1. 解释一：
2. 解释二：（主要思路）
/* 缓存容量为 2 */
LRUCache cache = new LRUCache(2);
// 你可以把 cache 理解成一个队列
// 假设左边是队头，右边是队尾
// 最近使用的排在队头，久未使用的排在队尾
// 圆括号表示键值对 (key, val)
cache.put(1, 1);
// cache = [(1, 1)]
cache.put(2, 2);
// cache = [(2, 2), (1, 1)]
cache.get(1); // 返回 1
// cache = [(1, 1), (2, 2)]
// 解释：因为最近访问了键 1，所以提前至队头
// 返回键 1 对应的值 1
cache.put(3, 3);
// cache = [(3, 3), (1, 1)]
// 解释：缓存容量已满，需要删除内容空出位置
// 优先删除久未使用的数据，也就是队尾的数据
// 然后把新的数据插入队头
cache.get(2); // 返回 -1 (未找到)
// cache = [(3, 3), (1, 1)]
// 解释：cache 中不存在键为 2 的数据
cache.put(1, 4);
// cache = [(1, 4), (3, 3)]
// 解释：键 1 已存在，把原始值 1 覆盖为 4
// 不要忘了也要将键值对提前到队头
1. 双链表的节点类：
class Node {
public int key, val;
public Node next, prev;
public Node(int k, int v) {
this.key = k;
this.val = v;
}
}
2. 包含常用 API 的双链表类：
class DoubleList {
private Node head, tail; // 头尾虚节点
private int size; // 链表元素数
public DoubleList() {
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
size = 0;
}
// 在链表头部添加节点 x
public void addFirst(Node x) {
x.next = head.next;
x.prev = head;
head.next.prev = x;
head.next = x;
size++;
}
// 删除链表中的 x 节点（x 一定存在）
public void remove(Node x) {
x.prev.next = x.next;
x.next.prev = x.prev;
size--;
}
// 删除链表中最后一个节点，并返回该节点
public Node removeLast() {
if (tail.prev == head)
return null;
Node last = tail.prev;
remove(last);
return last;
}
// 返回链表长度
public int size() { return size; }
}
3. 实现逻辑：
// key 映射到 Node(key, val)
HashMap<Integer, Node> map;
// Node(k1, v1) <-> Node(k2, v2)...
DoubleList cache;
int get(int key) {
if (key 不存在) {
return -1;
} else {
将数据 (key, val) 提到开头；
return val;
}
}
void put(int key, int val) {
Node x = new Node(key, val);
if (key 已存在) {
把旧的数据删除；
将新节点 x 插入到开头；
更新 map 中对应的数据；
} else {
if (cache 已满) {
删除链表的最后一个数据腾位置；
删除 map 中映射到该数据的键；
}
将新节点 x 插入到开头；
map 中新建 key 对新节点 x 的映射；
}
}
if (cap == cache.size()) {
// 删除链表最后一个数据
Node last = cache.removeLast();
map.remove(last.key);
}
代码：
1. 代码一：使用LinkedHashMap实现
// 方法1：使用LinkedHashMap实现
public static class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
public LRUCache(int capacity) {
// 初始大小，0.75是装载因子，true是表示按照访问时间排序
super(capacity, 0.75F, true);
// 传入指定的缓存最大容量
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
/**
* 实现LRU的关键方法，如果map里面的元素个数大于了缓存最大容量，则删除链表的顶端元素
*/
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest)
{
return size() > capacity;
}
}
2. 代码二：使用双向链表结构+HashMap实现
import java.util.*;
/**
* code146
*/
public class code146 {
// 方法2：使用双向链表结构+HashMap实现
// 双链表的节点类
public static class Node {
public int key, val;
public Node next, prev;
public Node(int k, int v)
{
this.key = k;
this.val = v;
}
}
// 包含常用 API 的双链表类
public static class DoubleList {
private Node head, tail; // 头尾虚节点
private int size; // 链表元素数
public DoubleList()
{
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
size = 0;
}
// 在链表头部添加节点 x
public void addFirst(Node x)
{
x.next = head.next;
x.prev = head;
head.next.prev = x;
head.next = x;
size++;
}
// 删除链表中的 x 节点（x 一定存在）
public void remove(Node x)
{
x.prev.next = x.next;
x.next.prev = x.prev;
size--;
}
// 删除链表中最后一个节点，并返回该节点
public Node removeLast()
{
if(tail.prev == head)
{
return null;
}
Node last = tail.prev;
remove(last);
return last;
}
// 返回链表长度
public int size()
{
return size;
}
}
// 实现逻辑：
public static class LRUCache {
// key -> Node(key, val)
private HashMap<Integer, Node> map;
// Node(k1, v1) <-> Node(k2, v2)...
private DoubleList cache;
// 最大容量
private int cap;
public LRUCache(int capacity) {
this.cap = capacity;
map = new HashMap<>();
cache = new DoubleList();
}
public int get(int key) {
if(!map.containsKey(key))
{
return -1;
}
int val = map.get(key).val;
// 利用 put 方法把该数据 (key, val) 提到开头；
put(key, val);
return val;
}
public void put(int key, int value) {
// 先把新节点 x 做出来
Node x = new Node(key, value);
if(map.containsKey(key))
{
// 把旧的数据删除；
cache.remove(map.get(key));
// 将新节点 x 插入到开头；
cache.addFirst(x);
// 更新 map 中对应的数据；
map.put(key, x);
}
else
{
if(cap == cache.size)
{
// 删除链表的最后一个数据腾位置；
Node last = cache.removeLast();
// 删除 map 中映射到该数据的键；
map.remove(last.key);
}
// 将新节点 x 插入到开头；
cache.addFirst(x);
// map 中新建 key 对新节点 x 的映射；
map.put(key, x);
}
}
}
public static void main(String[] args) {
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
int res1 = cache.get(1);
System.out.println(res1);
cache.put(3, 3);
int res2 = cache.get(2);
System.out.println(res2);
cache.put(4, 4);
int res4 = cache.get(1);
System.out.println(res4);
int res5 = cache.get(3);
System.out.println(res5);
int res6 = cache.get(4);
System.out.println(res6);
}
}