一、概念
LRU是Least Recently Used的缩写，即最近最少使用页面置换算法，是一种内存管理算法，该算法最早应用于Linux操作系统，是为虚拟页式存储管理服务的，是根据页面调入内存后的使用情况进行决策了。
通俗来讲，就是将最近最少使用的 key 从缓存中淘汰掉。
- 时间上，新的留下，老的淘汰
- 如果访问了某个 key，则它就变成最新的
实现策略：
链表法，最近访问的 key 移动到链表头，不常访问的自然靠近链表尾，如果超过容量、个数限制，移除尾部的
随机取样法，链表法占用内存较多，redis 使用的是随机取样法，每次只抽 5 个 key，每个 key 记录了它们的最近访问时间，在这 5 个里挑出最老的移除
二、实现LRU
2.1 使用双向链表实现LRU
整体的设计思路是，可以使用 HashMap 存储 key，这样可以做到 save 和 get key的时间都是 O(1)，而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点，如图所示：
可以把LRU算法代码的构建类比为后端分层模型:持久层（Dao层）、业务层（Service层）、Servlet层
- 最底层就是链表
- 中间层就是用哈希map包装了链表操作(用哈希map的value存链表node)
- 最上层就是加上了LRU算法逻辑
数据结构：哈希表+双向链表，哈希表用来存储节点信息，双向链表用来存储位置信息。链表中每个节点的结构为Node类型，包含所需的键-值信息、该节点的前驱节点、该节点的后继节点。
哈希表是由若干个Key-Value组成的。在“逻辑”上，这些Key-Value是无所谓排列顺序的，
谁先谁后都一样。
在哈希链表中，这些Key-Value不再是彼此无关的存在，而是被一个链条串了
起来。每一个Key-Value都具有它的前驱Key-Value、后继Key-Value，就像双向
链表中的节点一样。
原本无序的哈希表就拥有了固定的排列顺序
依靠哈希链表的有序性，我们可以把Key-Value按照最后的使用时间进行排序。
将新插入的或者刚被访问的数据插入到链表的最左端，右端就是最近最少被访问的数据
约定：双向链表的头部是最近访问的节点。这个并不是固定不变的，而是人为约定的。
注意：（1）给双向链表添加头尾的虚拟节点，虚拟节点不包含信息，只起到连接的作用，这样的好处是不用再特殊考虑链表中有数据的第一个节点和最后一个节点，可以把这两个节点也当成普通节点一样对待了。（2）LRU有容量限制，所以在put一个全新的键值时，可以首先考虑剩余容量大小，如果容量已满，先要删除最不常使用的节点（和上面的约定规则相关联）。
例如：LRU缓存机制（LeetCode146）
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) ：如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
写入数据 put(key, value) ：如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
定义链表节点信息
//链表节点
class Node{
public Node pre;
public Node next;
public String key;
public String value;
public Node(String key, String value) {
this.key = key;
this.value = value;
}
}
最底层实现
/**
* 删除链表中任意位置的节点
* @param node 要删除的节点
* @return
*/
private String removeNode(Node node){
if(node==head&&node==end){
//链表只有一个元素，移除唯一的节点
//头指针和尾指针都置空
head=null;
end=null;
}else if(node==end){
//移除尾节点
end = end.pre;//尾指针前移一位
end.next=null;
}else if(node==head){
//移除头节点
head = head.next;//头指针后移一位
head.pre = null;
}else {
//移除中间节点
node.pre.next = node.next;
node.next.pre = node.pre;
}
//将删除节点的key返回
return node.key;
}
/**
* 尾部插入节点
* LRU算法每次都只能在尾部插入节点
* 链表头部表示：最近最少使用的节点
* @param node 要插入的节点
*/
private void addNode(Node node){
if(end!=null){
//链表有元素，则插入到end指针指向的元素后面
end.next = node;
node.pre = end;
node.next = null;
}
//尾指针后移
//不管之前链表有没有元素，node插入都将是链表最后一个元素
end=node;
if(head==null){
//说明在没插入node之前是空链表
//插入后只有node一个元素
//node既是头也是尾
head=node;
}
}
/**
* 刷新被访问的节点位置(就是再次访问链表中已经存在的元素,将他们放到链表尾)
* @param node 被访问的节点
* 这里Node node都是引用（node就是指针，指向node的指针）
* node和end,pre都是引用（指针)
*/
private void refreshNode(Node node){
if(node==end){
//访问的是尾节点，无需移动节点
return;
}
//走到这一步都得把node指向的节点移动到链表尾
//先删除这个节点
removeNode(node);
//在插入到尾部(尾插)
addNode(node);
}
中间层实现：
//中间层***********
/**
* 从哈希map链表中删除key对应的value
* 注意看传入参数
* 其实本质就是链表指定位置的删除
* 在外面套了一层哈希map的皮
* @param key
*/
public void remove(String key){
Node node =hashMap.get(key);
removeNode(node);//链表中删除
hashMap.remove(key);//哈希map中删除
}
/**
* 从哈希map链表中添加key对应的value
* 注意看传入参数
* 其实本质就是链表尾插
* 在外面套了一层哈希map的皮
* @param key
* @param value
*/
public void add(String key,String value){
//新建链表节点
Node node =new Node(key,value);//value本质保存到node中了
addNode(node);//链表尾插
hashMap.put(key,node);//哈希map中添加
}
最上层实现：
/**
* 将key和value存入哈希map链表中..
* 注意这里key和value都是String类型
* 我们定义的：private HashMap<String,Node> hashMap;
* @param key
* @param value
*/
public void put(String key,String value){
//获取HashMap中对应key值的valus
//在LRU算法中，如果key对应的value不存在，则在链表末尾插入
//如果key对应的value存在，则将该元素取出放到链表的末尾
Node node = hashMap.get(key);
//如果Key 不存在，则在末尾插入Key-Value
if(node==null){
//哈希mao链表超过长度，移除头节点
if(hashMap.size()>=limit){
//头节点是最近最少使用的，移除
String oldKey = removeNode(head);
hashMap.remove(oldKey);
}
add(key,value);
}else {
//如果Key 存在，则刷新Key-Value(将其放入链表末尾)
node.value = value;//更新值
refreshNode(node);
}
}
public String get(String key){
Node node = hashMap.get(key);
//没有存对应的key和value
if(node==null){
String a="哈希链表没有 "+key+" 和与之对应的value";
return a;
}
refreshNode(node);//将刚访问的节点放到链表末尾
return node.value;
}
测试代码：
public static void main(String[] args) {
myLinkHashMap myLinkHashMap = new myLinkHashMap(4);
myLinkHashMap.put("1","张三");
myLinkHashMap.put("2","李四");
myLinkHashMap.put("3","王五");
System.out.println(myLinkHashMap.get("2"));
System.out.println(myLinkHashMap.get("4"));
myLinkHashMap.put("4","赵六");
System.out.println(myLinkHashMap.get("4"));
myLinkHashMap.put("5","孙七");
System.out.println(myLinkHashMap.get("1"));
}
在例子中，需要注意的是：
- 使用的数据结构：哈希表+双向链表，哈希表用来存储节点（数据），双向链表用来存储位置信息。
- 哈希表的键值对中，键是给出的key，值是节点信息，节点Node是内部类，注意这里必须要存储节点，从而保证从链表中删除一个节点的时间复杂度为O(1)。
- 这里约定：最近访问过的（get、put）节点放在双向链表的头部，所以尾部的节点就是最不经常使用的节点。
- 具体实现的过程中，head和tail是虚拟节点，不指向真正的节点，便于链表的穿针引线。
2.2 使用LinkedHashMap
LinkedHashMap = HashMap + 双向链表
Java中的LinkedHashmap对哈希链表已经有了很好实现了，需要注意的是，这段不是线程安全的，要想做到线程安全，需要加上synchronized修饰符。
LinkedHashMap可以实现LRU算法的缓存基于两点：
1、LinkedList首先它是一个Map，Map是基于K-V的，和缓存一致
2、LinkedList提供了一个boolean值可以让用户指定是否实现LRU
例子：使用LinkedHashMap实现一个符合LRU算法的数据结构，该结构最多可以缓存6个元素，当元素多余六个时，会自动删除最近最久没有被使用的元素。
import java.util.LinkedHashMap;
import java.util.Map;
public class LRU<K, V> extends LinkedHashMap<K, V> {
// initialCapacity 初始容量
// loadFactor 加载因子
// accessOrder 顺序模式，true对应访问顺序，false对应插入顺序
public LRU(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor, accessOrder);
}
// 重写LinkedHashMap中的removeEldestEntry方法，
// 当LRU中元素多余6个时，删除最不经常使用的元素
@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
if (size() > 6) {
return true;
}
return false;
}
public static void main(String[] args) {
LRU<Character, Integer> lru = new LRU<>(16, 0.75f, true);
String s = "abcdefghijkl";
for (int i = 0; i < s.length(); i++) {
lru.put(s.charAt(i), i);
}
System.out.println("LRU中key为h的Entry的值为：" + lru.get('h'));
System.out.println("LRU的大小：" + lru.size());
System.out.println("LRU：" + lru);
}
}
三、Redis的LRU实现
按照HashMap和双向链表实现，需要额外的存储存放 next 和 prev 指针，牺牲比较大的存储空间，显然是不划算的。所以Redis采用了一个近似的做法，就是随机取出若干个key，然后按照访问时间排序后，淘汰掉最不经常使用的，如下：
为了支持LRU，Redis 2.8.19中使用了一个全局的LRU时钟，server.lruclock，定义如下:
#define REDIS_LRU_BITS 24
unsigned lruclock:REDIS_LRU_BITS; /* Clock for LRU eviction */
默认的LRU时钟的分辨率是1秒，可以通过改变REDIS_LRU_CLOCK_RESOLUTION宏的值来改变，Redis会在serverCron()中调用updateLRUClock定期的更新LRU时钟，更新的频率和hz参数有关，默认为100ms一次，如下:
#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1 /* LRU clock resolution in seconds */
void updateLRUClock(void) {
server.lruclock = (server.unixtime / REDIS_LRU_CLOCK_RESOLUTION) &
REDIS_LRU_CLOCK_MAX;
}
server.unixtime是系统当前的unix时间戳，当 lruclock 的值超出REDIS_LRU_CLOCK_MAX时，会从头开始计算，所以在计算一个key的最长没有访问时间时，可能key本身保存的lru访问时间会比当前的lrulock还要大，这个时候需要计算额外时间，如下:
/* Given an object returns the min number of seconds the object was never
* requested, using an approximated LRU algorithm. */
unsigned long estimateObjectIdleTime(robj *o) {
if (server.lruclock >= o->lru) {
return (server.lruclock - o->lru) * REDIS_LRU_CLOCK_RESOLUTION;
} else {
return ((REDIS_LRU_CLOCK_MAX - o->lru) + server.lruclock) *
REDIS_LRU_CLOCK_RESOLUTION;
}
}
Redis支持和LRU相关淘汰策略包括:
- volatile-lru 设置了过期时间的key参与近似的lru淘汰策略
- allkeys-lru 所有的key均参与近似的lru淘汰策略
当进行LRU淘汰时，Redis按如下方式进行的:
......
/* volatile-lru and allkeys-lru policy */
else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
{
for (k = 0; k < server.maxmemory_samples; k++) {
sds thiskey;
long thisval;
robj *o;
de = dictGetRandomKey(dict);
thiskey = dictGetKey(de);
/* When policy is volatile-lru we need an additional lookup
* to locate the real key, as dict is set to db->expires. */
if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
de = dictFind(db->dict, thiskey);
o = dictGetVal(de);
thisval = estimateObjectIdleTime(o);
/* Higher idle time is better candidate for deletion */
if (bestkey == NULL || thisval > bestval) {
bestkey = thiskey;
bestval = thisval;
}
}
}
......
Redis会基于server.maxmemory_samples配置选取固定数目的key，然后比较它们的lru访问时间，然后淘汰最近最久没有访问的key，maxmemory_samples的值越大，Redis的近似LRU算法就越接近于严格LRU算法，但是相应消耗也变高，对性能有一定影响，样本值默认为5。
四、实际使用场景
LRU算法也可以用于一些实际的应用中，如你要做一个浏览器，或类似于淘宝客户端的应用的就要用到这个原理。大家都知道浏览器在浏览网页的时候会把下载的图片临时保存在本机的一个文件夹里，下次再访问时就会，直接从本机临时文件夹里读取。但保存图片的临时文件夹是有一定容量限制的，如果你浏览的网页太多，就会一些你最不常使用的图像删除掉，只保留最近最久使用的一些图片。这时就可以用到LRU算法 了，这时上面算法里的这个特殊的栈就不是保存页面的序号了，而是每个图片的序号或大小；所以上面这个栈的元素都用Object类来表示，这样的话这个栈就可以保存的对像了。