🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇
⭐LRU⭐
🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇
前言
这道题其实刷了有段时间了，很久之前就像写这道题的博客了，被期末耽误了。这道题挺特别的，可能是我确实刷题不够亦或者刷题不够深刻，这道题是刷这么久的题（其实没很久）第一次深刻的感受到算法在实际业务中的运用，很奇妙的感觉，就像天天被风吹的脸生疼，但这次我感觉到了风的律动（有点小夸张哈哈哈哈）。
更神奇的是，在期末考完之后，最后一门就是操作系统，很意外，我竟然在这操作系统中再次碰见了 LRU ，页面置换算法中的 LRU，今天刚考完试，就这份缘分也必须把这博客今日毕。
1. LRU 缓存简介
LRU（最近最少使用）是一种缓存淘汰算法，通常用于缓存管理系统中。当缓存的容量达到上限时，LRU算法会优先淘汰那些最久未被访问的数据项。具体而言，LRU缓存会保持一个顺序列表，其中最“旧”的数据项（即最久未被使用的数据项）会被移除，以腾出空间给新的数据项。
2. 问题描述
我们需要设计一个类 LRUCache，它支持以下两种操作：
- get(key): 如果缓存中存在该
key，则返回其对应的值，否则返回-1。- put(key, value): 将给定的
key和value放入缓存中。如果缓存已满，则需要通过 LRU 算法移除最不常用的缓存项。
操作复杂度要求
- get 和 put 操作的时间复杂度要求为 O(1)，即常数时间复杂度。
为了达到这个目标，我们需要选择合适的数据结构来支持快速访问、插入和删除操作。
3. 数据结构选择
重点：
在边读题边思考的时候你就会发现，这道题实际上就是实现加了一个功能的哈希表，方法都是一样的，所以毫无疑问会用到哈希表。那么就是这个容量满了会自动删除最久没有使用的算法。
我那会写的时候，可能那段时间队列用多了，下意识的直接把他们放队列中，但是要怎么实现删除最久没有使用的节点呢，我想了挺久，队列是先进先出的，当我把1 2 3 4放入队列后，put是删尾巴，不好实现，如果我此时get 3，那么就要删除 3，然后再加入3。有一个删除，然后添加操作，此时
3 在中间，要出队列就得把前面的数都出了，那前面的数又放在哪，可以再用一个队列，但是这样的时间算法复杂度就不会是 O（1）了。
那么队列就无法时间，队列的好兄弟同理栈也不行，对于中间删除，木讷的数组更不行，二最后一个，最后只剩链表了。
这里我们定义 链表头是最新，链表尾最久。
先单链表，get里边含有的节点，此时节点在中间，删除中间节点，先要找到节点，可以靠哈希表直接 O（1）找到节点，然后就是删除，需要前一个节点才可以，这时我们可以用双向链表解决这个问题。
删除解决了，现在就是添加，添加直接头插就行，put 的话直接尾删。
那么，为了解决这个问题，我结合了两种数据结构：哈希表（HashMap）和 双向链表（Doubly Linked List）。
3.1 哈希表
哈希表用于通过
key快速定位到缓存中的节点。哈希表的查找、插入、删除操作的时间复杂度是 O(1)。在LRUCache中，哈希表的键（key）对应缓存项的key，而值（value）则是缓存项的双向链表节点（Doubly Linked Node）。
3.2 双向链表
双向链表允许我们在 O(1) 的时间内将节点移动到链表的头部或尾部，也能在 O(1) 时间内删除节点。双向链表的头部表示最新使用的数据，尾部表示最久未使用的数据。每次访问一个缓存项时，我们将其移动到链表头部，表示它是最新使用的；每次淘汰缓存项时，我们会从尾部移除最旧的数据项。
4. LRUCache 类设计
下面是
LRUCache类的实现，结合了哈希表和双向链表。
4.1 数据成员
class LRUCache {class DLinkedNode {int key;int value;DLinkedNode pre;DLinkedNode next;public DLinkedNode(){}public DLinkedNode(int key, int value) {this.key = key;this.value = value;}}// 哈希表用于快速定位节点HashMap<Integer, DLinkedNode> map;// 缓存容量和当前缓存中的元素数量private int capacity;private int size;// 虚拟头尾节点，便于操作链表DLinkedNode head, tail;
}
4.2 构造函数
构造函数初始化缓存容量，并且创建了一个空的虚拟头节点和尾节点，这样我们就可以方便地在链表的两端进行操作。
public LRUCache(int capacity) {map = new HashMap<>();this.capacity = capacity;size = 0;// 创建头尾虚拟节点head = new DLinkedNode();tail = new DLinkedNode();// 连接头尾虚拟节点head.next = tail;tail.pre = head;
}
4.3 get 方法
get 方法用于查询一个 key 是否存在于缓存中。如果存在，返回对应的值，并将该节点移动到链表的头部，表示它是最新访问的。如果不存在，返回 -1。
public int get(int key) {DLinkedNode node = map.get(key);if (node == null) {return -1; // 缓存中没有该节点} else {moveToHead(node); // 将该节点移动到链表头部return node.value;}
}
4.4 put 方法
put 方法将一个 key 和 value 放入缓存。如果缓存已满，会根据 LRU 算法淘汰掉最旧的节点。如果 key 已经存在于缓存中，我们只需要更新其值并将其移动到链表的头部。如果 key 不在缓存中，则需要创建一个新的节点并插入到链表的头部。
public void put(int key, int value) {// 查询缓存中是否已有该节点DLinkedNode node = map.get(key);if (node == null) {// 如果节点不存在，创建新节点并插入到头部node = new DLinkedNode(key, value);addToHead(node);map.put(key, node);size++;// 如果缓存超出容量，移除尾部最旧的节点if (size > capacity) {DLinkedNode tail = removeTail();map.remove(tail.key);}} else {// 如果节点存在，更新其值并移动到头部node.value = value;moveToHead(node);}
}
4.5 辅助函数
removeTail: 删除并返回尾部节点，即最久未使用的节点。addToHead: 将节点插入到链表的头部。moveToHead: 将一个节点从当前的位置移到链表的头部。removeNode: 删除指定的节点。
public DLinkedNode removeTail() {DLinkedNode node = tail.pre;removeNode(node);return node;
}public void addToHead(DLinkedNode node) {head.next.pre = node;node.next = head.next;node.pre = head;head.next = node;
}public void moveToHead(DLinkedNode node) {removeNode(node);addToHead(node);
}public void removeNode(DLinkedNode node) {node.next.pre = node.pre;node.pre.next = node.next;
}
5. 算法原理总结
- 哈希表的使用：通过哈希表，我们可以 O(1) 时间复杂度地查找和更新缓存中的数据项。
- 双向链表的使用：双向链表保证了我们可以在 O(1) 的时间复杂度内将一个节点移动到链表的头部或尾部，支持 LRU 缓存的高效实现。
- 缓存容量管理：当缓存达到容量上限时，我们通过删除尾部节点来确保缓存的容量不超过上限。
6. 总结
通过结合哈希表和双向链表，我们可以实现一个高效的 LRU Cache。哈希表提供了快速的查找和更新，而双向链表则使得我们可以快速地更新缓存项的顺序。整体上，该算法能够在 O(1) 时间复杂度内完成 get 和 put 操作，确保在大规模数据访问时也能保持高效。
感谢阅览！！！