📝 简介

• LRU Cache 指最近最少使用缓存，它是一种常见的缓存管理技术，用于加速数据访问。

• LRU Cache 基于最近使用的记录在缓存中保留一个固定大小的记录集，并剔除最近最少使用的记录。

• 当缓存中的记录数量达到上限时，最早之前被使用的记录会被替换掉。

实现思路

• 维护一个哈希表以及一个双向链表。

• 哈希表用于记录每个记录的位置和值，而双向链表用于记录记录的顺序。

• 当一个新记录被访问时，在哈希表中查找该记录，如果记录存在则将其移动到链表的头部；

• 如果记录不存在，就将其添加到哈希表和链表的头部。

• 如果缓存已满，则将链表的末尾元素从哈希表和链表中移除。

代码实现

基于LinkedHashMap

• LinkedHashMap提供了按访问顺序（access-order）排序的功能

基于HashMap

🤗 时间复杂度

• 哈希表操作 (HashMap):
• 查找（get, containsKey）：平均时间复杂度为 O(1)。
• 插入和删除（put, remove）：平均时间复杂度 O(1)。

• 双向链表操作:
• 移动到头部（moveToHead）、添加到头部（addToHead）：这些操作直接操作链表的头部，时间复杂度为 O(1)。
• 删除节点（removeNode）：时间复杂度也是 O(1) 的，因为每个节点都存储了指向前一个和后一个节点的直接引用。

• 综上，LRU的各种操作，最优的时间复杂度都为 O(1)。

📎 参考文章

JVM 常见面试题 - 掘金

一.JVM 1.JVM 内存模型 JVM 的内存模型指的是 Java 程序在 JVM 中运行时，JVM 给程序分配的内存结构。JVM 的内存模型主要分为以下几个区域： 方法区（Method Area）

https://juejin.cn/post/7233720284707242043