数据结构与算法 | 第二篇深入学习LRU算法（原理 图解 核心思想）

文章结构概览

• 1.LRU算法
  • • 1.1相关概念
    • 1.2图解举例
    • 1.3基于HashMap和双向链表实现
    • • 1.3.1核心思想
      • 1.3.2代码解读
      • 1.3.3全部代码

1.LRU算法原理与应用

1.1相关概念

• LRU（Least Recently Used，最近最久未使用算法）：

  • 定义：该算法依据页面在内存中被调用后的使用频率进行判断。LRU页面替换机制会优先移除那些在最近一段时间内未被访问的页面；

  • 支持：此方法为每个页面分配一个访问字段，用于记录自上一次访问以来所经历的时间t；当需要淘汰页面时，系统将选择当前所有页面中t值最大的那个页面，即为最近最久未使用的页面予以替换。

  • 两种硬件支持（可任选其一）：

    1. 寄存器：
       • 功能：寄存器中包含标记位与时间戳信息。标记位能够快速判断缓存块（或页面）是否处于有效状态，从而避免对整个栈进行遍历查找。时间戳则可用于记