146、LRU缓存机制
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶:
- 你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
1 <= capacity <= 30000 <= key <= 10000- $0 <= value <= 10^5$
- 最多调用
2 * 105次 get 和 put
题解
LinkedHashMap
class LRUCache extends LinkedHashMap<Integer, Integer>{
// 容量控制
private int capacity;
public LRUCache(int capacity) {
// 调用父类构造函数，0.75F表示
/*
initialCapacity 初始容量 - the initial capacity
loadFactor 负载引子 - the load factor
accessOrder 获取顺序 - the ordering mode -
true for access-order（按照访问频率排序）, false for insertion-order（插入顺序）
*/
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);
}
/**
覆盖此方法，可以保持容量不变，移除最久为未访问的元素
*/
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/
自定义双向链表 + HashMap
链表节点：存储key, value, prev前驱指针，next后继指针。
哈希表：将key和链表节点建立映射。
public class LRUCache {
// 双向链表节点
class DequeLinkedNode {
int key;
int value;
DequeLinkedNode prev;
DequeLinkedNode next;
public DequeLinkedNode() {}
public DequeLinkedNode(int key,int value) {
this.key = key;
this.value = value;
}
// 双向链表节点可以自己将自己从链表中删除
public void removeSelf() {
prev.next = next;
next.prev = prev;
}
}
private int capacity; // 总容量
private int size; // 当前节点数量
private DequeLinkedNode head,tail;// 头尾节点
private Map<Integer,DequeLinkedNode> cache = new HashMap<>();// 哈希表缓存
public LRUCache(int capacity) {
// 初始化
size = 0;
this.capacity = capacity;
head = new DequeLinkedNode();
tail = new DequeLinkedNode();
// 头尾相连
head.next = tail;
tail.prev = head;
}
// 获取key对应的value
public int get(int key) {
DequeLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 最新访问记录，将该节点移动到链表头部
moveToHead(node);
return node.value;
}
// 将key,value 存储起来
public void put(int key,int value) {
// 现判断是否存在
DequeLinkedNode node = cache.get(key);
if(node == null) {
DequeLinkedNode newNode = new DequeLinkedNode(key,value);
cache.put(key, newNode);
addToHead(newNode);
++size;
// 超过容量了
if (size > capacity) {
// 双向链表移除尾结点
DequeLinkedNode tail = removeTail();
// 缓存移除对应的key value
cache.remove(tail.key);
--size;
}
} else {
node.value = value;
moveToHead(node);
}
}
// 将一个节点移动到头部
private void addToHead(DequeLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void moveToHead(DequeLinkedNode node) {
node.removeSelf();
addToHead(node);
}
// 移除尾结点并返回
private DequeLinkedNode removeTail() {
DequeLinkedNode node = tail.prev;
node.removeSelf();
return node;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
