Redies 淘汰策略的 LRU 算法你知道吗？
阅读文本大概需要 6 分钟。
Redis作为高效的缓存工具，在面试的时候常常会被问到。
最近有个小伙伴跟我诉苦，说他面试的时候被问到Redis的淘汰策略，这个问题他是有准备的
Redis 中有下面八种内存淘汰策略：
noeviction：默认策略，当内存达到设置的最大值时，所有申请内存的操作都会报错(如set,lpush等)，只读操作如get命令可以正常执行； allkeys-lru：所有key使用LRU算法淘汰； allkeys-lfu：所有key使用LFU算法淘汰；allkeys-random：所有key使用随机淘汰； volatile-lru：设置了过期时间的key使用LRU算法淘汰； volatile-lfu：设置了过期时间的key使用LFU算法淘汰； volatile-random：设置了过期时间的key使用随机淘汰； volatile-ttl：设置了过期时间的key根据过期时间淘汰，越早过期越早淘汰；
可紧接着面试官问到LRU的实现，他之前知道有被问过LRU的，但是觉得比较复杂，心想自己应该不会遇到，所以暂时就没准备。
奈何不巧，这还就真的考到了！ 结果自然GG...
今天我们就来看看这个LRU算法的实现吧：
LRU算法
LRU（Least Recently Used）表示最近最少使用，该算法根据数据的历史访问记录来进行淘汰数据，其核心思想是如果数据最近被访问过，那么将来被访问的几率也更高。
LRU算法的常见实现方式为链表：
新数据放在链表头部 ，链表中的数据被访问就移动到链头，链表满的时候从链表尾部移出数据。
实现 LRUCache 类：
LRUCache(int capacity)
以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key)
如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value)
如果关键字已经存在，则变更其数据值；
如果关键字不存在，则插入该组「关键字-值」。
当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
LRU的核心就是借助哈希+双链表。
哈希用于查询，双链表实现删除，只知道当前节点也能删除，不过双链表需要考虑的头尾指针特殊情况。
对于这个情况，你需要能够手写双链表：
class LRUCache {
//存储数据的链表节点
class Node {
int key;
int value;
Node pre;
Node next;
public Node() {
}
public Node( int key,int value) {
this.key = key;
this.value=value;
}
}
// 双向链表
class DoubleList{
private Node head;// 头节点
private Node tail;// 尾节点
private int length;
public DoubleList() {
head = new Node(-1,-1);
tail = head;
length = 0;
}
void add(Node teamNode)// 默认尾节点插入
{
tail.next = teamNode;
teamNode.pre=tail;
tail = teamNode;
length++;
}
void deleteFirst(){
if(head.next==null)
return;
if(head.next==tail)//如果删除的那个刚好是tail，tail指针前面移动
tail=head;
head.next=head.next.next;
if(head.next!=null)
head.next.pre=head;
length--;
}
void deleteNode(Node team){
team.pre.next=team.next;
if(team.next!=null)
team.next.pre=team.pre;
if(team==tail)
tail=tail.pre;
team.pre=null;
team.next=null;
length--;
}
}
Map<Integer,Node> map=new HashMap<>();
DoubleList doubleList;//存储顺序
int maxSize;
LinkedList<Integer>list2=new LinkedList<>();
public LRUCache(int capacity) {
doubleList=new DoubleList();
maxSize=capacity;
}
public int get(int key) {
int val;
if(!map.containsKey(key))
return -1;
val=map.get(key).value;
Node team=map.get(key);
doubleList.deleteNode(team);
doubleList.add(team);
return val;
}
public void put(int key, int value) {
if(map.containsKey(key)){// 已经有这个key 不考虑长短直接删除然后更新
Node deleteNode=map.get(key);
doubleList.deleteNode(deleteNode);
}
else if(doubleList.length==maxSize){//不包含并且长度小于
Node first=doubleList.head.next;
map.remove(first.key);
doubleList.deleteFirst();
}
Node node=new Node(key,value);
doubleList.add(node);
map.put(key,node);
}
}
当然Redis是基于C的，这里我们只是基于熟悉的Java进行实现，思路是相同的。
我们还可以发现 LinkedHashMap其实也是这种哈希+双链表的数据结构！
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}但是一般面试官，既然这样问了，肯定是希望咱们能自己实现写一个双链表的。
希望本文对你有帮助 ！
腾讯云开发者
