LRU算法实现

1，LRU概念

1）LRU：least recent used 最近最少使用，常用语cpu的L1、L2等cache中的淘汰算法。
2）核心步骤
1.save key，找到缓存位置。LRU缓存满，淘汰尾部节点，key放入头部节点。
2.get key，将节点放入头部位置。

2，LRU java实现

放入和移除都是 O(1)
1）基于HashMap和双向列表实现LRU

image.png
2）数据结构
image.png
image.png
image.png

3，redis LRU算法

1）随机取固定数目的key基于server.maxmemory_samples，按照访问时间排序，淘汰的最不经常使用的。
2）LRU淘汰策略
volatile-lru：只淘汰设置了过期时间的key。
allkeys-lru：所有的key都参与近似的lru淘汰策略。
3）redis的serverCron()事件循环中，执行近似的LRU淘汰算法。