找往期文章包括但不限于本期文章中不懂的知识点：
个人主页： 我要学编程(ಥ_ಥ)-CSDN博客
所属专栏：数据结构（Java版）
目录
LRU Cache的概念
LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法 。什么是Cache？狭义的Cache指的是位于CPU和主存间的快速RAM（random-access memory的缩写，即我们日常生活中所说的运行内存），通常它不像系统主存那样使用DRAM技术，而使用昂贵但较
快速的SRAM技术。广义上的Cache指的是位于速度相差较大的两种硬件之间，用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache，内存与硬盘之间也有Cache，乃至在硬盘与网络之间也有某种意义上的Cache一称为lnternetl临时文件夹或网络内容缓存等。
Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时，就需要挑选并舍弃原有的部分内容，从而腾出空间来放新内容。LRUCache的替换原则就是将最近最少使用的内容替换掉。其实，LRU译成最久未使用会更形象，因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。
LRU Cache的实现
实现LRU Cache的方法和思路很多，但是要保持高效实现O(1)的put和get，那么使用双向链表和哈希表的搭配是最高效和经典的。使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除，使用哈希表是因为哈希表的增删查改也是O(1)。
在Java的集合类中有一个类和LRU Cache的实现类似——LinkedHashMap，其底层也是哈希表+双向链表。
每次使用get方法，访问数据后，会把数据放到当前双向链表的最后。
当accessOrder为true时，get方法和put方法都会调用recordAccess方法使得最近使用的Entry移到双向链表的末尾；当accessOrder为默认值false时，从源码中可以看出recordAccess方法什么也不会做。
模拟实现LRU Cache
模式实现LRU Cache主要就是实现两个方法：put 和 get。
前期准备：
哈希表+双向链表：
// 节点
static class ListNode{
public int key;
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int key, int val) {
this.key = key;
this.val = val;
}
}
// 这个哈希表中存放的是一个一个的节点，快速查找
public HashMap<Integer, ListNode> hashMap;
// 带头节点和尾节点便于修改，速度非常快
public ListNode head;
public ListNode tail;
public int capacity; // LRU Cache容量
public int usedSize; // 记录使用个数
public LRUCache(int capacity) {
this.hashMap = new HashMap<>();
this.head = new ListNode(-1, -1);
this.tail = new ListNode(-1, -1);
this.head.next = this.tail;
this.tail.prev = this.head;
this.capacity = capacity;
}
实现 put 方法：
思路： 首先，得在哈希表中查找是否存在该key。如果存在，只需要更新其 val值即可，然后再把这个节点移动到链表的尾部（先删除，在尾插）；如果不存在，就新实例化一个节点，然后再尾插到链表尾部，接着usedSize++，检查容量是否满了。满了就得删除头结点（最近最久未被使用）
代码实现：
public void put(int key, int val) {
// 首先得查找hashmap中是否有这个元素
ListNode node = hashMap.get(key);
if (node == null) {
ListNode newNode = new ListNode(key, val);
hashMap.put(key, newNode); // 哈希表存一份
usedSize++; // 个数++
addToTail(newNode); // 把该节点移到链表末尾
if (usedSize > capacity) {
// 移除链表的头节点
ListNode head = moveHead();
// 将哈希表中的元素移除
hashMap.remove(head.key);
usedSize--;
}
} else {
// 存在这个元素，更新val即可
node.val = val; // 这里就已经把哈希表中的val更新了
moveTail(node);
}
}
private ListNode moveHead() {
ListNode del = head.next;
head.next = del.next;
del.next.prev = head;
return del;
}
private void moveTail(ListNode node) {
// 先删除node节点，在尾插到末尾
removeNode(node);
addToTail(node);
}
private void addToTail(ListNode node) {
node.next = tail;
node.prev = tail.prev;
tail.prev.next = node;
tail.prev = node;
}
private void removeNode(ListNode newNode) {
newNode.prev.next = newNode.next;
newNode.next.prev = newNode.prev;
}
实现 get 方法：
思路： 直接在哈希表中查找。如果不存在，返回-1；如果存在，就返回其对应的val，并在此之前把这个节点移动到链表的尾部。
代码实现：
public Integer get(int key) {
if (hashMap.get(key) == null) {
return -1;
} else {
// 把这个移到链表尾部
moveTail(hashMap.get(key));
return hashMap.get(key).val;
}
}
相关练习
题目：
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现
LRUCache类：
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。函数
get和put必须以O(1)的平均时间复杂度运行。
示例：
输入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4] 解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4提示：
1 <= capacity <= 30000 <= key <= 100000 <= value <= 105- 最多调用
2 * 105次get和put
思路一：就是直接手动实现一个LRU Cache，也就是我们模拟实现LRU Cache的代码。
思路二：在Java中LInkedHashMap是类似于LRU Cache的，因此我们直接用这个来写也是可以的。
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
public LRUCache(int capacity) {
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);
}
// 注意：这个是用来判断是否需要移除元素的，因此一定要重写（默认是false）
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
好啦！本期 数据结构之LRUCache 的学习之旅就到此结束啦！我们下一期再一起学习吧！
原文链接: https://blog.csdn.net/2301_80854132/article/details/141409321