2023-04-04 10:42:09
浏览数 (1)
设计LRU 缓存结构
代码语言：javascript
复制import java.util.*;
/**
* LRU 最近最少使用，内存淘汰算法
*/
public class LRUCache {
// 双向链表， 访问节点，说明使用一次，那么这个节点就移动到头部作为热门数据，其余数据位置不变，尾部就是最近最少使用的节点
// 怎么插入呢？ 如果缓存为空，那么头插法插入。如果缓存满了，先将尾节点删除，然后插入到头节点后面
// 双向链表删除尾节点、插入头节点的效率都是O（1）
// 但是如果我们去访问节点的话，双向链表还是遍历O（N）的复杂度，
// 所以就可以通过HashMap 记录key（访问值），value(链表的节点)，达到O（1）的效率
Entry head,tail;// 代表双向链表的头节点和尾节点
int capacity;// 缓存的大小
int size;// 实际存储的大小
Map<Integer,Entry> cache; // 查缓存的哈希表
public LRUCache(int capacity) {
// 实际上双向链表中是真正的LRU缓存数据
initLinkedList();
this.capacity =capacity;
this.size=0;
this.cache = new HashMap<>(capacity);
}
// 向缓存中放一个值
/**
*
* @param key , 就是我们要放入的元素 1、2、3、4、5、6
* @param value ， 就是这个元素 对应的在双向链表中的 一个节点
*/
public void put(int key,int value){
// 先查这个key在双向链表中是否存在
Entry node =cache.get(key);
if(node!=null){// 说明这个key已经在 linkedList中存在，那么首先更新value
node.value = value;
// 删掉这个节点的连接关系，然后移动到头节点
moveToHead(node);
return;
}
// 删 、 添 都需要 操作（链表 缓存Map）
if(size==capacity){// 此时内存已经满了,需要将尾节点的元素删除，然后构建新节点插入到头节点后面
Entry lastNode = tail.pre;
// 删除链表中的一个元素
deleteNode(lastNode);
// 删除缓存中的一个节点
cache.remove(lastNode.key);
size--;
}
// 此时是内存不满，而且key在链表中不存在的情况,头插法查到头节点后面即可
Entry newHead = new Entry(key,value);
addToHead(newHead);
// 也要添加到缓存中
cache.put(key, newHead);
size ;
}
public int get(int key){
Entry node = cache.get(key);
if(node==null){
return -1;
}
// 因为查询了一次，所以这个node又变成了热点数据，需要先删节点关系，然后移动到头节点后面
int result = node.value;
moveToHead(node);
return result;
}
/**
* 删除最后的尾节点前面的节点即可
* @param node
*/
private void deleteNode(Entry node) {
node.pre.next = tail;
tail.pre = node.pre;
}
private void addToHead(Entry node) {
node.next = head.next;
head.next.pre = node;
head.next = node;
node.pre = head;
}
public void moveToHead(Entry node){
deleteNode(node);
addToHead(node);
}
// 初始化链表的方法
private void initLinkedList() {
this.head = new Entry(0,0);
this.tail = new Entry(0,0);
head.next = tail;
tail.pre = head;
}
// 代表双向链表的一个节点
public static class Entry{
public Entry pre;
public Entry next;
public int key;
public int value;
public Entry(int key, int value) {
this.key = key;
this.value = value;
}
}
}
