LRU 算法全称是最近最少使用算法（Least Recently Use），是一种简单的缓存策略。顾名思义，LRU 算法会选出最近最少使用的数据进行淘汰。
那么什么是缓存呢？缓存专业点可以叫一种提高数据读取性能的技术，可以有效解决存储器性能和容量的矛盾，是一种空间换时间的设计思想，比如我们常见的内存是硬盘的缓存，Cache 是内存的缓存，浏览器本地存储是网络访问的缓存......
LRU 有许多应用场景，例如：
146. LRU 缓存 [1]，请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
函数 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
如上图所示，就是哈希表 + 链表实现的 LRU 缓存数据结构，有以下几个问题解释一下：
package main
import "fmt"
// LRU 数据结构
type LRUCache struct {
capacity int // 容量
size int // 已使用空间
head, tail *DLinkedNode // 头节点，尾节点
cache map[int]*DLinkedNode // 哈希表
}
// 双向链表数据结构
type DLinkedNode struct {
key, value int
prev, next *DLinkedNode // 前指针，后指针
}
// 创建一个新的节点
func initDLinkedNode(key, value int) *DLinkedNode {
return &DLinkedNode{
key: key,
value: value,
}
}
// 初始化 LRU 结构
func Constructor(capacity int) LRUCache {
l := LRUCache{
cache: map[int]*DLinkedNode{}, // 哈希表
head: initDLinkedNode(0, 0), // 虚拟头节点
tail: initDLinkedNode(0, 0), // 虚拟尾节点
capacity: capacity, // 容量
}
// 虚拟头节点和虚拟尾节点互连
l.head.next = l.tail
l.tail.prev = l.head
return l
}
// 获取元素
func (this *LRUCache) Get(key int) int {
// 如果没有在哈希表中找到 key
if _, ok := this.cache[key]; !ok {
return -1
}
// 如果 key 存在，先通过哈希表定位，再移到头部
node := this.cache[key]
this.moveToHead(node)
return node.value
}
// 插入元素
func (this *LRUCache) Put(key int, value int) {
// 先去哈希表中查询
// 如果 key 不存在，创建一个新的节点
if node, ok := this.cache[key]; !ok {
newNode := initDLinkedNode(key, value)
// 如果达到容量限制，链表删除尾部节点，哈希表删除元素
this.size++
if this.size > this.capacity {
// 得到删除的节点
removed := this.removeTail()
// 根据得到的 key 删除哈希表中的元素
delete(this.cache, removed.key)
// 减少已使用容量
this.size--
}
// 插入哈希表
this.cache[key] = newNode
// 插入链表
this.addToHead(newNode)
} else { // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
node.value = value
this.moveToHead(node)
}
}
// 将节点添加到头部
func (this *LRUCache) addToHead(node *DLinkedNode) {
// 新节点指向前后节点
node.prev = this.head
node.next = this.head.next
// 前后节点指向新节点
this.head.next.prev = node
this.head.next = node
}
// 删除该节点
func (this *LRUCache) removeNode(node *DLinkedNode) {
// 修改该节点前后节点的指针，不再指向该节点
node.next.prev = node.prev
node.prev.next = node.next
}
// 移动到头部，也就是当前位置删除，再添加到头部
func (this *LRUCache) moveToHead(node *DLinkedNode) {
this.removeNode(node)
this.addToHead(node)
}
// 移除尾部节点，淘汰最久未使用的
func (this *LRUCache) removeTail() *DLinkedNode {
node := this.tail.prev // 虚拟尾节点的上一个才是真正的尾节点
this.removeNode(node)
return node
}
// 打印链表（解题不需要此方法，只是为了显示效果）
func (this *LRUCache) printDLinkedNode() {
p := this.head
for p != nil {
fmt.Printf("key: %d, value: %d\n", p.key, p.value)
p = p.next
}
}
func main() {
lru := Constructor(3)
fmt.Println("=========================== 插入 3 个节点 ===========================")
lru.Put(1, 100)
lru.Put(2, 200)
lru.Put(3, 300)
fmt.Println("=========================== 打印当前链表 ===========================")
lru.printDLinkedNode()
fmt.Println("=========================== 插入第 4 个节点，LRU 缓存淘汰尾部节点 ===========================")
lru.Put(4, 400)
lru.printDLinkedNode()
fmt.Println("=========================== 获取 key2 节点，更新 LRU 缓存，将会移动至链表头部 ===========================")
lru.Get(2)
lru.printDLinkedNode()
}
import java.util.HashMap;
import java.util.Map;
public class LRUCache {
// 双向链表
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {
}
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
// 哈希表
private Map<Integer, DLinkedNode> cache = new HashMap<>();
// 已使用空间
private int size;
// 容量
private int capacity;
// 头节点，尾节点
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 使用虚拟头部和虚拟尾部节点
head = new DLinkedNode();
tail = new DLinkedNode();
// 虚拟头节点和虚拟尾节点互连
head.next = tail;
tail.prev = head;
}
// 获取元素
public int get(int key) {
DLinkedNode node = cache.get(key);
// 如果没有在哈希表中找到 key
if (node == null) {
return -1;
}
// 如果 key 存在，先通过哈希表定位，再移到头部
moveToHead(node);
return node.value;
}
// 插入元素
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
// 如果 key 不存在，创建一个新的节点
DLinkedNode newNode = new DLinkedNode(key, value);
// 如果达到容量限制，链表删除尾部节点，哈希表删除元素
size++;
if (size > capacity) {
// 得到删除的节点
DLinkedNode removed = removeTail();
// 根据得到的 key 删除哈希表中的元素
cache.remove(removed.key);
// 减少已使用容量
size--;
}
// 插入哈希表
cache.put(key, newNode);
// 添加至双链表的头部
addToHead(newNode);
} else {
// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
node.value = value;
moveToHead(node);
}
}
// 将节点添加到链表头部
private void addToHead(DLinkedNode node) {
// 新节点指向前后节点
node.prev = head;
node.next = head.next;
// 前后节点指向新节点
head.next.prev = node;
head.next = node;
}
// 删除节点
private void removeNode(DLinkedNode node) {
// 修改该节点前后节点的指针，不再指向该节点
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 移动到头部，也就是当前位置删除，再添加到头部
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
// 移除尾部节点，淘汰最久未使用的
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev; // 虚拟尾节点，prev 才是此时真正的尾节点
removeNode(res);
return res;
}
// 打印链表（解题不需要此方法，只是为了显示效果）
private void printDLinkedNode() {
DLinkedNode p = this.head;
while (p != null) {
System.out.printf("key: %d, value: %d\n", p.key, p.value);
p = p.next;
}
}
public static void main(String[] args) {
LRUCache lru = new LRUCache(3);
System.out.println("=========================== 插入 3 个节点 ===========================");
lru.put(1, 100);
lru.put(2, 200);
lru.put(3, 300);
System.out.println("=========================== 打印当前链表 ===========================");
lru.printDLinkedNode();
System.out.println("=========================== 插入第 4 个节点，LRU 缓存淘汰尾部节点 key1 ===========================");
lru.put(4, 400);
lru.printDLinkedNode();
System.out.println("=========================== 获取 key2 的节点，更新 LRU 缓存，将会移动至链表头部 ===========================");
lru.get(2);
lru.printDLinkedNode();
}
}
代码运行的返回结果如下，其中头尾两个 key=0, value=0 的节点是虚拟节点，请忽略。
=========================== 插入 3 个节点 ===========================
=========================== 打印当前链表 ===========================
key: 0, value: 0
key: 3, value: 300
key: 2, value: 200
key: 1, value: 100
key: 0, value: 0
=========================== 插入第 4 个节点，LRU 缓存淘汰尾部节点 ===========================
key: 0, value: 0
key: 4, value: 400
key: 3, value: 300
key: 2, value: 200
key: 0, value: 0
=========================== 获取 key2 节点，更新 LRU 缓存，将会移动至链表头部 ===========================
key: 0, value: 0
key: 2, value: 200
key: 4, value: 400
key: 3, value: 300
key: 0, value: 0
第 1 步：初始化数据结构。
第 2 步：插入节点 key1。
第 3 步：插入节点 key2。 此时 key2 插入到链表头部。
第 4 步：插入节点 key3。 此时 key3 插入到链表头部。
第 5 步：插入节点 key4。当前 capacity 容量达到上限（3），分为 2 步：
使用 removeTail() 方法删除链表尾部的节点 key1，从 removeTail() 方法的返回值得到 node，再根据 node.key 得到 key1，然后去哈希表删除节点 key1。
然后插入节点 key4，此时 key4 在链表头部。
第 6 步：读取 key2 的值，将 key2 移动到链表头部。 
微信关注我们
转载内容版权归作者及来源网站所有！
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。
Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。
Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。
WebStorm 是jetbrains公司旗下一款JavaScript 开发工具。目前已经被广大中国JS开发者誉为“Web前端开发神器”、“最强大的HTML5编辑器”、“最智能的JavaScript IDE”等。与IntelliJ IDEA同源，继承了IntelliJ IDEA强大的JS部分的功能。
扫码在手机上查看文章
扫描二维码，手机阅读更方便
有任何问题或合作意向欢迎联系我们
Email: 99873273@qq.com
QQ: 99873273