一、背景
- 含义: Least Recently Used, 最近最少使用。
- 作用: 缓存空间不足时，决定哪些数据被移除。
- 场景
- 内存管理，页面置换算法
- 一种缓存淘汰策略
二、原理
局部性原理
- 时间局部性：被引用过一次的存储器位置在未来会被多次引用（通常在循环中）。
- 空间局部性：如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。
三、实现
三个操作
- 查找 get 当某个元素被访问到，会把它移动到链表的表头
- 插入 put 存在结点，更新 不存在，插入到表头。如果空间不足，还需要淘汰掉末尾的结点
单链表实现
双链表实现
双向链表+哈希表
双向链表：最近使用的放在链表的前端，反之则是在链表的后端。