成为VIP
LRU
Redis的淘汰策略
为什么要有淘汰策略呢？
因为存储内存的空间是有限的，所以需要有淘汰的策略。
Redis的清理内存淘汰策略有哪些呢？
Redis内存淘汰策略
LRU算法简介
LRU是Least Recently Used的缩写，即最近最少使用list初始化，是一种常见的页面置换算法。
我们手机的后台窗口（苹果手机双击Home的效果），他总是会把最近常用的窗口放在最前边，而最不常用的应用窗口，就排列在后边了，如果再加上只能放置N个应用窗口的限制，淘汰最不常用的最近最少用的应用窗口，那就是一个活生生的LRU。
手机后台应用窗口
实现思想推导
手机应用案例
从上边的示意图，我们可以分析出这么几个点：
有序；如果应用开满3个了，要淘汰最不常用的应用，每次新访问应用，需要把数据插入队头（按照业务可以设定左右哪一边是队头）；O(1)复杂度是我们查找数据的追求，我们什么结构能够实现快速的O(1)查找呢？
推导图
通过上边的推导，我们就能得出，LRU算法核心是HashMap + DoubleLinkedList。
思想搞明白了，我们接下来编码实现。
巧用LinkedHashMap
我们查看Java的LinkedHashMap使用说明。
LinkedHashMap使用说明
翻译：这种Map结构很适合构建LRU缓存。
继承LinkedHashMap实现LRU算法：
public class LRUDemo extends LinkedHashMap {
private int capacity;
public LRUDemo(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return super.size() > capacity;
}
public static void main(String[] args) {
LRUDemo lruDemo = new LRUDemo(3);
lruDemo.put(1, "a");
lruDemo.put(2, "b");
lruDemo.put(3, "c");
System.out.println(lruDemo.keySet());
lruDemo.put(4, "d");
lruDemo.put(5, "e");
System.out.println(lruDemo.keySet());
}
}
重点讲解：
构造方法：super(capacity, 0.75F, true)，主要看第三个参数：order参数true -> access-order // false -> insertion-order即按照访问时间排序，还是按照插入的时间来排序// 构造方法改成false
super(capacity, 0.75F, false);
// 使用示例
public static void main(String[] args) {
LRUDemo lruDemo = new LRUDemo(3);
lruDemo.put(1, “a”);
lruDemo.put(2, “b”);
lruDemo.put(3, “c”);
System.out.println(lruDemo.keySet());
lruDemo.put(1, “y”);
// 构造方法order=true，输出：[2,3,1]，
// 构造方法order=false，输出：[1,2,3]，
System.out.println(lruDemo.keySet());
}removeEldestEntry方法：什么时候移除最年长的元素。
通过上面，相信大家对LRU算法有所理解了，接下来我们不依赖JDK的LinkedHashMaplist初始化，通过我们自己的理解，动手实现一个LRU算法，让我们的LRU算法刻入我们的大脑。
手写LRU
上边的推导图中可以看出，我们用HashMap来做具体的数据储存，但是我们还需要构造一个DoubleLinkedList对象（结构体）来储存HashMap的具体key顺序关系。
第一步：构建DoubleLinkedList对象所以我们现在第一步，就是构建一个DoubleLinkedList对象：
DoubleLinkedList示意图
我们可以从HashMap源码中找一些灵感，他们都是使用一个Node静态内部类来储存节点的值。
第二步：构建节点
通过上边的示意图，我们可以得知节点应该要储存的内容：
keyvalueprev节点next节点
翻译成代码：
class Node {
K key;
V value;
Node prev;
Node next;
public Node() {
this.prev = this.next = null;
}
public Node(K key, V value) {
this.key = key;
this.value = value;
this.prev = this.next = null;
}
}
第三步：初始化DoubleLinkedList对象
DoubleLinkedList初始化示意图
还是通过上边的示意图，我们可以得知DoubleLinkedList对象应该要储存的内容：
头节点尾节点
翻译成代码：
class DoubleLinkedList {
Node head;
Node tail;
// 构造方法
public DoubleLinkedList(){
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
}
}
从头添加节点
从头添加节点
翻译成代码：
public void addHead(Node node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
删除节点
删除节点
翻译成代码：
public void removeNode(Node node) {
node.next.prev = node.prev;
node.prev.next = node.next;
node.prev = null;
node.next = null;
}
获取最后一个节点
public Node getLast() {
return tail.prev;
}
第四步：LRU对象属性cacheSize
private int cacheSize;
map
Map<Integer, Node> map;
doubleLinkedList
DoubleLinkedList doubleLinkedList;
第五步：LRU对象的方法构造方法
public LRUDemo(int cacheSize) {
this.cacheSize = cacheSize;
map = new HashMap();
doubleLinkedList = new DoubleLinkedList();
}
refreshNode刷新节点
public void refreshNode(Node node) {
doubleLinkedList.removeNode(node);
doubleLinkedList.addHead(node);
}
get节点
public String get(int key) {
if (!map.containsKey(key)) {
return "";
}
Node node = map.get(key);
refreshNode(node);
return node.value;
}
put节点
public void put(int key, String value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.value = value;
map.put(key, node);
refreshNode(node);
} else {
if (map.size() == cacheSize) {
Node lastNode = doubleLinkedList.getLast();
map.remove(lastNode.key);
doubleLinkedList.removeNode(lastNode);
}
Node newNode = new Node(key, value);
map.put(key, newNode);
doubleLinkedList.addHead(newNode);
}
}
第六步：测试
public static void main(String[] args) {
LRUDemo lruDemo = new LRUDemo(3);
lruDemo.put(1, "美团");
lruDemo.put(2, "微信");
lruDemo.put(3, "抖音");
lruDemo.put(4, "微博");
System.out.println(lruDemo.map.keySet());
System.out.println(lruDemo.get(2));
}
总结
限时特惠：本站每日持续更新海量设计资源，一年会员只需29.9元，全站资源免费下载
站长微信：ziyuanshu688
htebazile
