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; listpairint,int ls; unordered_mapint,listpairint,int:: iterator mp; public: LRUCache(int capacity) { capcapacity; } int get(int key) { auto itmp.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 itmp.find(key); if(it!mp.end()) { it-second-secondvalue; ls.splice(ls.begin(),ls,it-second); return; } if(ls.size()cap) { auto itls.back().first; mp.erase(it); ls.pop_back(); } ls.emplace_front(key,value); mp[key]ls.begin(); } };cap用于指定LRU缓存的最大容量capcapacity并在构造时初始化为最大容量capacity。listpairintint lsls用于存储pair键值对(key,value)unordered_mapintlistpairintint::iterator mpmp将key映射到对应的链表节点迭代器。auto itmp.find(key)get方法首先在哈希表mp中查找keyif(it!mp.end())如果存在ls.splice(ls.begin()lsit-second)则调用list的splice方法将该节点移动到链表头部表示最近访问it-second则为该节点对应的迭代器return it-second-second最后返回该节点存储的值value如果不存在则return -1。auto itmp.find(key)put方法同样先查找keyif(it!mp.end())如果存在it-second-secondvalue则更新节点的值为valuels.splice(ls.begin()lsit-second)调用splice将节点移到头部最后return即可。如果key不存在需先判断缓存是否已满if(ls.size()cap)如果缓存已满auto itls.back().first则取出链表尾部节点的key即最久未使用的元素itmp.erase(it)从哈希表mp中删除该元素itls.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的设计思想已渗透到计算机体系的各个层级。