LRU 缓存的实现

概念

LRU（Least recently used，最近最少使用）算法是一种缓存淘汰算法。根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的机率也更高”。

1. 新数据插入到链表头部；
2. 每当缓存命中（即缓存数据被访问），则 将数据移到链表头部；
3. 当链表满的时候，将链表尾部的数据丢弃。

算法过程

假设只有 3 个内存空间：

1. 最开始时，内存空间时空的，因此依次进入 A、B、C 是没有问题的；
2. 当 D 加入时，内存空间不够，因此根据 LRU 算法，内存空间中 A 待的时间最为久远，选择 A，将其淘汰；
3. 当再次引用 B 时，内存空间中的 B 又处于活跃状态处于最顶部，则 C 变成最近最久未使用的了，所以在最底部。
4. 当再次加入新元素 E 时，内存空间又不足，则将最近最少使用的 C 淘汰出去，这是内存空间存放的对象就是 E->B->D.

实现细节

• 使用双向链表存储元素，并用 map 来存储键值映射。Hash Table + Double LinkedList
• 当 put 的元素在链表中时，把该元素防砸哎链表头，并更新 value
• 当 put 的元素不在链表中：
  • 如果链表容量达到上限，则先删除链表尾部节点和相应映射，之后将新元素存入链表开头，并建立键值映射
  • 如果链表容量未达到上限，则直接将新元素存入链表开头，并建立键值映射
• 当 get 的元素在链表时，把该元素调到链表头，并输出 value
• 当 get 的元素不在链表时，返回 -1

复杂度分析

• O(1) 查询
• O(1) 修改、更新

替换策略

• LFU - least frequently used 最少使用
• LRU - least recently used 最近最少使用
• FIFO - 先进先出
• OPT - 最佳置换