缓存结构设计(力扣)
1. LRU缓存机制
1.自己构建
力扣 146.LRU缓存机制, 题解参考资料 Dong哥 和 狗哥, 并转载了他们的图片
计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。但问题是，删除哪些内容呢？我们肯定希望删掉哪些没什么用的缓存，而把有用的数据继续留在缓存里，方便之后继续使用。那么，什么样的数据，我们判定为「有用的」的数据呢？
LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。
题目要求:
设计一种缓存结构，该结构在构造时确定大小，假设大小为K，并有两个功能：set(key,value)：将记录(key,value)插入该结构。get(key)：返回key对应的value值。
【要求】
set和get方法的时间复杂度为O(1)。
某个key的set或get操作一旦发生，认为这个key的记录成了最经常使用的。
当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。
【举例】
假设缓存结构的实例是cache，大小为3，并依次发生如下行为：
cache.set(“A”,1)。最经常使用的记录为(“A”,1)。
cache.set(“B”,2)。最经常使用的记录为(“B”,2)，(“A”,1)变为最不经常的。
cache.set(“C”,3)。最经常使用的记录为(“C”,2)，(“A”,1)还是最不经常的。
cache.get(“A”)。最经常使用的记录为(“A”,1)，(“B”,2)变为最不经常的。
cache.set(“D”,4)。大小超过了3，所以移除此时最不经常使用的记录(“B”,2)，加入记录 (“D”,4)，并且为最经常使用的记录，然后(“C”,2)变为最不经常使用的记录
题解:
那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表 LinkedHashMap。
LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样：
在哈希表中value存放的是节点的引用，通过key可以直接查询到某个节点，也可以直接在链表中定位！
1.设计好的Cache的上层结构
public static class MyCache<K>{
// cache缓存包括，哈希表，双端链表 和 容量
private HashMap<K, Node<K>> keyNodeMap;
private NodeDoubleLinkedList<K> nodeList;
private final int capacity;
// 初始化结构体
public MyCache(int capacity) {
this.capacity = capacity;
this.keyNodeMap = new HashMap<K, Node<K>>();
this.nodeList = new NodeDoubleLinkedList<K>();
}
// get(key)：返回key对应的value值。
public int get(K key){
// 如果这个key还在缓存中
if (keyNodeMap.containsKey(key)){
int val = keyNodeMap.get(key).value;
// 这个操作，会更新被操作的节点的顺序
nodeList.moveNodeToTail(keyNodeMap.get(key));
return val;
}else{
// 没有找到，它被移除了
return -1;
}
}
//set(key,value)：将记录(key,value)插入该结构。
public void put(K key, int value){
// 可能会是更新，也可能是插入新的点
// 更新操作不会移除点
if (keyNodeMap.containsKey(key)){
Node<K> node = keyNodeMap.get(key);
node.value = value;
// 这个操作，会更新被操作的节点的顺序
nodeList.moveNodeToTail(node);
}else {// 插入新节点了，要先判断容量够么
if (capacity == keyNodeMap.size()){
// 也可以定义一个函数: removeMostUnusedCache()
// 从链表中去除
Node<K> node = nodeList.removeHead();
// 在HashMap表中也清除它
keyNodeMap.remove(node.key);
}
// 插入新的点
Node<K> newNode = new Node<K>(key, value);
keyNodeMap.put(key, newNode);
nodeList.addNode(newNode);
}
}
} 2.实现其中的双端链表 和 基本的node类
// 定义包含 <key,value> 的Node节点
public static class Node<K>{
public K key;
public int value;
public Node<K> pre;
public Node<K> next;
public Node(K key, int value){
this.key = key;
this.value = value;
pre = null;
next = null;
}
}
// 在双端链表中要实现，三个功能
// void addNode(Node<K> node) : 添加新的节点，并放到链表尾部
// void moveNodeToTail(Node<K> node) : 把node放到链表尾部
// Node<K> removeHead() : 把头部节点从链表上移除，并返回它
public static class NodeDoubleLinkedList<K>{
// 设置头尾指针
public Node<K> head;
public Node<K> tail;
// 结构体初始化
public NodeDoubleLinkedList(){
head = null;
tail = null;
}
// 添加新的节点，并放到链表尾部
// 要分情况: 是空链表么
public void addNode(Node<K> node){
// 空链表
if (head == null){
head = node;
tail = node;
}else { // 非空链表
this.tail.next = node;
node.pre = this.tail;
this.tail = node;
}
}
// node 首先一定会存在
public void moveNodeToTail(Node<K> node){
// 本来就是尾巴
if (node == tail){
return;
}
// 本来是头部，就会给链表换头了
if (node == head){
node.next.pre = null;
// 更换头节点
head = node.next;
node.next = null;
// 拼接到尾节点上, 代码重复
}else { // 中间节点
// 连接好左右两边
node.pre.next = node.next;
node.next.pre = node.pre;
node.next = null;
node.pre = null;
// 拼接到尾节点上, 代码重复
}
// 把node放在tail上
tail.next = node;
node.pre = tail;
tail = node;
}
// 移除头节点，并把它返回
public Node<K> removeHead(){
// 压根没有头
if (head == null){
return null;
}
// 记录原来的头节点
Node<K> res = head;
// 只有一个节点
if (head == tail){
head = null;
tail = null;
}else{
// 把head标志位，向后移动一位
head = res.next;
// 根据新的头节点，把以前的头节点左右设置为空
res.next = null;
// 彻底断开原来的头节点, 新头部pre置空
head.pre = null;
}
return res;
}
} 2.LinkedHashMap build-in
参考资料
LinkedHashMap保持HashMap的数据结构，但是自己也维护一个双向循环链表。
LinkedHashMap内部有accessOrder标记，为false时，双向链表按插入的顺序排列。因为新插入的元素都是尾插法，此时我们需要自己实现makeItAsRecentlyUsed()方法，其实就是删除它在插入。
accessOrder=true时，每次对元素进行增删改查，都会将该元素放到链表尾部。使这个链表将最新操作的元素放入链表尾，长时间未使用的放入头部。这种即是LRU算法。
1.accessOrder=false
public static class MyCache{
int capacity;
LinkedHashMap<Integer, Integer> linkedHashMap;
// 结构体初始化
public MyCache(int capacity){
this.capacity = capacity;
this.linkedHashMap = new LinkedHashMap<>();
}
public int get(int key){
if (linkedHashMap.containsKey(key)){
int val = linkedHashMap.get(key);
// 因为get操作，把这个它更新了
makeItAsRecentlyUsed(key);
// 查询到了结果
return val;
}
// 没有这个点
return -1;
}
public void put(int key, int value){
// 更新操作
if (linkedHashMap.containsKey(key)){
// map上的更新
linkedHashMap.put(key, value);
makeItAsRecentlyUsed(key);
}else {
if (linkedHashMap.size() >= capacity){
// 移除链表的头部
int oldestKey = linkedHashMap.keySet().iterator().next();
linkedHashMap.remove(oldestKey);
}
// 腾出空间，添加新的节点
linkedHashMap.put(key, value);
}
}
private void makeItAsRecentlyUsed(int key){
int value = linkedHashMap.get(key);
linkedHashMap.remove(key);
// 重新加入，就自动放到tail上了
linkedHashMap.put(key, value);
}
} 2.accessOrder=true
public static class MyCache{
int capacity;
LinkedHashMap<Integer, Integer> linkedHashMap;
// 结构体初始化
public MyCache(int capacity){
this.capacity = capacity;
// 0.65f是扩容因子，true是启用accessOrder
this.linkedHashMap = new LinkedHashMap<>(capacity, 0.65f, true);
}
public int get(int key){
if (linkedHashMap.containsKey(key)){
int val = linkedHashMap.get(key);
// 因为get操作，把这个它更新了
// makeItAsRecentlyUsed(key);
// 查询到了结果
return val;
}
// 没有这个点
return -1;
}
public void put(int key, int value){
// 更新操作
if (linkedHashMap.containsKey(key)){
// map上的更新
linkedHashMap.put(key, value);
// makeItAsRecentlyUsed(key);
}else {
if (linkedHashMap.size() >= capacity){
// 移除链表的头部
int oldestKey = linkedHashMap.keySet().iterator().next();
linkedHashMap.remove(oldestKey);
}
// 腾出空间，添加新的节点
linkedHashMap.put(key, value);
}
}
}
