基于Cache替换算法的LRU缓存实现

LRU的全称为Least Recently Used，即最近最少使用，LRU是一种Cache替换算法。狭义的Cache指的是位于CPU和主存间的快速RAM，通常不像系统主存那样使用DRAM技术，而使用昂贵但较快速的SRAM技术。广义上的Cache指的是位于速度相差较大的两种硬件之间，用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache，内存与硬盘之间也有Cache，乃至在硬盘与网络之间也有某种意义上的Cache，称为Internet临时文件夹或网络内存缓存，如下图所示：

Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时，就需要挑选并舍弃原有的部分内容，从而腾出空间来放新内容。LRU Cache的替换原则就是将最近最少使用的内容替换掉。LRU译成最久未使用会更形象，因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。

下面来实现LRU缓存这一数据结构，需要实现的接口如下：

输入输出示例：

LRU缓存数据插入和调整的具体过程如下所示：

实现LRU Cache的方法和思路很多，但是要保持高效的O(1)的put和get，使用双向链表和哈希表是最高效的。双向链表可以实现任意位置O(1)的插入和删除，哈希表增删查改的时间复杂度也为O(1)。

采取双向链表+哈希的实现思路，LRU的结构如下所示：

代码实现：

class LRUCache { int cap; list<pair<int,int>> ls; unordered_map<int,list<pair<int,int>>:: iterator> mp; public: LRUCache(int capacity) { cap=capacity; } int get(int key) { auto it=mp.find(key); if(it!=mp.end()) { ls.splice(ls.begin(),ls,it->second); return it->second->second; } return -1; } void put(int key, int value) { auto it=mp.find(key); if(it!=mp.end()) { it->second->second=value; ls.splice(ls.begin(),ls,it->second); return; } if(ls.size()>=cap) { auto it=ls.back().first; mp.erase(it); ls.pop_back(); } ls.emplace_front(key,value); mp[key]=ls.begin(); } };

cap用于指定LRU缓存的最大容量，cap=capacity，并在构造时初始化为最大容量capacity。list<pair<int，int>> ls，ls用于存储pair键值对(key,value)，unordered_map<int，list<pair<int，int>>::iterator> mp，mp将key映射到对应的链表节点迭代器。auto it=mp.find(key)，get方法首先在哈希表mp中查找key，if(it!=mp.end())，如果存在，ls.splice(ls.begin()，ls，it->second)，则调用list的splice方法将该节点移动到链表头部表示最近访问，it->second则为该节点对应的迭代器，return it->second->second，最后返回该节点存储的值value，如果不存在，则return -1。auto it=mp.find(key)，put方法同样先查找key，if(it!=mp.end())，如果存在，it->second->second=value，则更新节点的值为value，ls.splice(ls.begin()，ls，it->second)，调用splice将节点移到头部，最后return即可。如果key不存在，需先判断缓存是否已满，if(ls.size()>=cap)，如果缓存已满，auto it=ls.back().first，则取出链表尾部节点的key，即最久未使用的元素it，mp.erase(it)，从哈希表mp中删除该元素it，ls.pop_back()，并弹出链表尾结点，ls.emplace_front(key,value)，最后调用emplace_front在链表头部插入新节点，mp[key]=ls.begin()，并在哈希表mp中记录key到链表迭代器的映射，put操作完成。

总结：

LRU缓存实现需同时支持两个操作维度：一是根据键值进行快速随机访问，二是维护键值对之间的时间序关系以便识别最久未使用的元素。哈希与双向链表的结合正是实现LRU这一数据结构的最佳实践，list结点通过存储键值对pair，并通过调用splice实现了O(1)的操作将最近使用过的结点往链表头部移动，使其保持LRU结构，哈希表将key与链表迭代器实现映射，这样当get到一个已有的值之后，就可以直接找到key在list中对应的迭代器，再调用splice将其移动到链表的头部，保持LRU结构。这种实现方式非常高效，每一步操作都在常数时间复杂度内完成，是计算机缓存系统设计中的经典范式，从虚拟内存的页面置换到分布式存储的热数据识别，LRU的设计思想已渗透到计算机体系的各个层级。