Redis LRU淘汰策略
柒柒Java 人气:0今天我们这篇文章的目的是要 搞懂LRU淘汰策略
以及 实现一个LRU算法
。
文章会结合图解循序渐进的讲解,跟着我的思路慢慢来就能看懂,我们开始吧。
文章导读
Redis的淘汰策略
为什么要有淘汰策略呢?
因为存储内存的空间是有限的,所以需要有淘汰的策略。
Redis的清理内存淘汰策略有哪些呢?
LRU算法简介
LRU是 Least Recently Used
的缩写,即 最近最少使用
,是一种常见的页面置换算法。
我们手机的后台窗口(苹果手机双击Home的效果),他总是会把最近常用的窗口放在最前边,而最不常用的应用窗口,就排列在后边了,如果再加上只能放置N个应用窗口的限制,淘汰最不常用的最近最少用的应用窗口,那就是一个活生生的 LRU
。
实现思想推导
手机应用案例
从上边的示意图,我们可以分析出这么几个点:
- 有序;
- 如果应用开满3个了,要淘汰最不常用的应用,每次新访问应用,需要把数据插入队头(按照业务可以设定左右哪一边是队头);
- O(1)复杂度是我们查找数据的追求,我们什么结构能够实现快速的O(1)查找呢?
推导图
通过上边的推导,我们就能得出, LRU
算法核心是 HashMap + DoubleLinkedList
。
思想搞明白了,我们接下来编码实现。
巧用LinkedHashMap
我们查看Java的 LinkedHashMap
使用说明。
LinkedHashMap使用说明
翻译:这种Map结构很适合构建LRU缓存。
继承 LinkedHashMap
实现 LRU
算法:
public class LRUDemo<K, V> extends LinkedHashMap<K, V> { private int capacity; public LRUDemo(int capacity) { super(capacity, 0.75F, true); this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> 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的 LinkedHashMap
,通过我们自己的理解,动手实现一个 LRU
算法,让我们的 LRU
算法刻入我们的大脑。
手写LRU
上边的推导图中可以看出,我们用 HashMap
来做具体的数据储存,但是我们还需要构造一个 DoubleLinkedList
对象(结构体)来储存 HashMap
的具体 key
顺序关系。
第一步:构建DoubleLinkedList对象
所以我们现在 第一步 ,就是构建一个 DoubleLinkedList
对象:
DoubleLinkedList示意图
我们可以从 HashMap
源码中找一些灵感,他们都是使用一个 Node
静态内部类来储存节点的值。
第二步:构建节点
通过上边的示意图,我们可以得知 节点 应该要储存的内容:
- key
- value
- prev节点
- next节点
翻译成代码:
class Node<K, V> { K key; V value; Node<K, V> prev; Node<K, V> 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<K, V> { Node<K, V> head; Node<K, V> tail; // 构造方法 public DoubleLinkedList(){ head = new Node<>(); tail = new Node<>(); head.next = tail; tail.prev = head; } }
从头添加节点
从头添加节点
翻译成代码:
public void addHead(Node<K, V> node) { node.next = head.next; node.prev = head; head.next.prev = node; head.next = node; }
删除节点
删除节点
翻译成代码:
public void removeNode(Node<K, V> 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<Integer, String>> map;
doubleLinkedList
DoubleLinkedList<Integer, String> 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<Integer, String> node = map.get(key); refreshNode(node); return node.value; }
put节点
public void put(int key, String value) { if (map.containsKey(key)) { Node<Integer, String> 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<Integer, String> 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)); }
总结
LRU
算法到这里就写完啦,完整的代码可以从阅读原文的链接地址获取。
加载全部内容