LRU 缓存¶
- 参考
LRU (Least Recently Used) 最近最少使用
LRU 缓存机制是通过 哈希表 + 双向链表 实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。 - 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。 - 哈希表即为普通的哈希映射（C++ 中 unordered_map），通过缓存数据的键映射到其在双向链表中的位置。
1 LRU 变体¶
1.1 LRU-K¶
LRU-K 比 LRU 多了一层队列 A （用来存历史访问数据，仅仅记录的是某个 key 对应的访问次数，并不是 key 对应的 value），当队列 A 中的元素访问达到 K 次后，才将此元素放入缓存队列 B 中。 访问时先向缓存队列 B 中查找，缓存没有命中就从磁盘或其它介质上查找，同时更新访问队列 A。
1.2 LRU-Two queues (2Q)¶
2Q 和 LRU-2 类似，也有 2 个队列，但 2Q 的 2 个队列都是缓存队列。新增的 缓存队列是 FIFO 缓存，只有在 FIFO 缓存队列中存在的数据被再次访问时，才会加入到 LRU 缓存队列中。