LRU 缓存淘汰算法的两种实现

It's always the attention to detail and the little grace notes that really make something sing. 专注细节愈出彩，别致心思定成败。

本文主要分享了LRU 缓存淘汰算法两种实现。 重要的不是实现，而且思想！

所有源码均已上传至github： github.com/chaoaiqi/st…

定义

LRU（Least Recently Used）最近最少使用策略就像它的名字一样，是根据数据的历史访问记录来进行淘汰数据的，其思想是“如果数据最近被访问过，那么将来被访问的几率也更高；长期不被使用的数据在将来用到的几率也不大；当数据所占内存达到一定的阈值时，将移除最近最少被使用的数据”。

举例

比如一个书柜（容量为10),我会把我自己的书籍放进去，其中有两本书籍是我最喜欢的，经常翻阅，但是随着我的购买，书柜会逐渐放满（内存溢出），这时候就需要用到LRU的思想了，把我不经常看的，从书柜里拿出，放进箱子里，然后再把新买的书籍放进书柜。

再 比如Redis，它是基于内存的，但是内存也不是无穷大的，当内存占用达到一个阈值的时候，它就可以使用LRU等一系列缓存算法，或者是将数据存到硬盘里。

具体的实现代码如下：

基于链表

链表初始化，申请capacity大小的内存空间

模拟LRU的访问（如果没有该数据，则插入头部）

注意：该if-else语句不能交换顺序，否则会出现链表已满，并且该数据已存在的情况无法处理。

删除指定数据方法，常规删除

删除链表尾部数据

在头部插入数据

测试结果如下

1. 首先将capacity大小的链表插满
2. 当插入capacity+1个数据时，需要删除尾部数据
3. 当插入的数据存在的时候，将它从其位置删除，并且插入头部

基于数组

数据比较链表实现起来更为简单，在此不做阐述，直接上代码。

测试结果如下

注意：因为有大量频繁的访问导致数据迁移频繁，因此数组并不适合做这种事情，可以考虑加一个HaspMap做缓存，避免数据的频繁迁移。

end

您的点赞和关注是对我最大的支持，谢谢！