大厂面试：2024年虾皮Java开发面试题及参考答案（5万字长文）

LRU（Least Recently Used）算法即最近最少使用算法，是一种常用的页面置换算法，在计算机的内存管理和缓存机制中广泛应用。

LRU 算法的实现方式

通常可以使用双向链表和哈希表来实现 LRU 算法。

1. 双向链表

   • 用于存储数据节点，每个节点包含一个键值对（key-value）和指向前一个节点和后一个节点的指针。
   • 最近使用的节点位于链表头部，最久未使用的节点位于链表尾部。

2. 哈希表

   • 用于快速访问双向链表中的节点，键为数据的键（key），值为双向链表中的节点。

当进行数据访问时：

• 如果数据在哈希表中存在，通过哈希表快速定位到双向链表中的节点，将该节点移动到链表头部，表示最近被使用过。
• 如果数据不在哈希表中，且缓存已满（双向链表长度达到上限），则删除链表尾部的节点，并将新的数据节点插入到链表头部，并在哈希表中添加相应的映射。
• 如果数据不在哈希表中且缓存未满，则直接将新的数据节点插入到链表头部，并在哈希表中添加