如何手写一个LRU算法
背景
在Redis的内存占用过多的时候，此时会进行内存淘汰，比较常用的就是基于LRU算法进行淘汰。那么什么是LRU算法呢？
LRU算法概念
LRU 是Least Recently Used的缩写，简称最近最少使用。
也就是说在Redis中内存满了，会优先淘汰那些最近最不常访问的数据。那在Java中用什么数据结构去实现呢？一种的话是基于LinkedHashMap，一种是自己设计数据结构，使用链表+HashMap。
既然有现成的，那我们就直接拿过来用吧。有人会问，为什么用LinkedHashMap呢？我们下面看一下LinkedHashMap的数据结构是怎么样的？
LinkedHashMap数据结构
LinkedHashMap继承了HashMap，拥有HashMap的所有特性，同时LinkedHashMap在增加了head和tail指针，用于实现双向链表
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
LinkedHashMap默认按照插入顺序保存数据，新的数据插入双向链表尾部
public static void main(String[] args) {
LinkedHashMap<String,String> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("3","3");
linkedHashMap.put("4","4");
linkedHashMap.put("1","1");
linkedHashMap.put("7","7");
linkedHashMap.put("5","5");
linkedHashMap.put("9","9");
linkedHashMap.put("0","0");
linkedHashMap.put("2","2");
linkedHashMap.put("6","6");
linkedHashMap.put("8","8");
for (Map.Entry<String,String> entry : linkedHashMap.entrySet()){
System.out.println(entry.getKey());
}
}
=================运行结果=================
3
4
1
7
5
9
0
2
6
8
LinkedHashMap中有构造方法支持按顺序访问，最新访问的数据放到链表尾部
public static void main(String[] args) {
LinkedHashMap<String,String> linkedHashMap = new LinkedHashMap<>(10,0.75f,true);
linkedHashMap.put("3","3");
linkedHashMap.put("4","4");
linkedHashMap.put("1","1");
linkedHashMap.put("7","7");
linkedHashMap.put("5","5");
linkedHashMap.put("9","9");
linkedHashMap.put("0","0");
linkedHashMap.put("2","2");
linkedHashMap.put("6","6");
linkedHashMap.put("8","8");
linkedHashMap.get("4");
linkedHashMap.get("7");
for (Map.Entry<String,String> entry : linkedHashMap.entrySet()){
System.out.println(entry.getKey());
}
}
============运行结果===========
3
1
5
9
0
2
6
8
4
7
从下面源码中，我们可以看到，通过accessOrder如果为true，则按照访问顺序进行排序，将访问到的数据放置链表尾部，如果为false，则按插入顺序进行排序
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial
*/
final boolean accessOrder;
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
// 获取元素
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
// 开启按顺序访问，则移动访问节点至链表尾部
afterNodeAccess(e);
return e.value;
}
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 开启按顺序访问且当前节点不是尾结点
if (accessOrder && (last = tail) != e) {
// 设置b为e的前置节点，a为e的后置节点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 将当前节点的后置节点设为null
p.after = null;
// 如果e的前置节点为空,则将e的后置节点设置为头结点，否则将e的前置节点的后置节点设置为a
if (b == null)
head = a;
else
b.after = a;
// 如果e的后置节点不为空，将e的后置节点的前置节点设置为b，否则，将e的前置节点设置为尾结点
if (a != null)
a.before = b;
else
last = b;
// 如果尾节点为空，则将当前节点p设置为头结点，否则将当前节点的前置节点设置为尾结点，尾结点的后置节点为当前节点
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
// 设置当前节点为尾结点
tail = p;
++modCount;
}
}
LRU缓存实现
通过LinkedHashMap的特性，如何实现LRU算法呢，自动删除掉链表表头的过期数据
- 定义一个类继承LinkedHashMap
public class LRULinkedMap<K,V> extends LinkedHashMap<K,V> {
private int size;
public LRULinkedMap(int initialCapacity,float loadFactor,boolean accessOrder){
super(initialCapacity,loadFactor,accessOrder);
this.size = initialCapacity;
}
/**
* 重写LinkedHashMap的removeEldestEntry方法
* 当LRU元素超过容量上限size后，删除最不经常使用的
* @param eldest
* @return
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > size;
}
}
- 测试类
public static void main(String[] args) {
LRULinkedMap<String,String> linkedHashMap = new LRULinkedMap<>(5,0.75f,true);
linkedHashMap.put("3","3");
linkedHashMap.put("4","4");
linkedHashMap.put("1","1");
linkedHashMap.put("5","5");
linkedHashMap.put("6","6");
for (Map.Entry<String,String> entry : linkedHashMap.entrySet()){
System.out.println(entry.getKey());
}
System.out.println("=========get(1)后将1移动到尾部=========");
linkedHashMap.get("1");
for (Map.Entry<String,String> entry : linkedHashMap.entrySet()){
System.out.println(entry.getKey());
}
System.out.println("=========插入新数据后，移除头部最老的3和4=========");
linkedHashMap.put("2","2");
linkedHashMap.put("9","9");
for (Map.Entry<String,String> entry : linkedHashMap.entrySet()){
System.out.println(entry.getKey());
}
}
=========运行结果========
3
4
1
5
6
=========get(1)后将1移动到尾部=========
3
4
5
6
1
=========插入新数据后，移除头部最老的3和4=========
5
6
1
2
9
removeEldestEntry
目前看的确是达到了效果，但是也许有人会有疑问，为什么重写了removeEldestEntry就可以了，那我们去看看removeEldestEntry方法的源码是怎么样的。
在LinkedHashMap中，removeEldestEntry默认返回的是false
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
我们看看removeEldestEntry在哪里被用到了，false起到了什么作用
我们看到在LinkedHashMap中有这么一个方法afterNodeInsertion，在这个方法里需要同时满足以下3个条件才能将LinkedHashMap中的元素删除
- 入参evict为true
- LinkedHashMap中元素头节点不为null
- removeEldestEntry方法返回为true
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
afterNodeInsertion方法是在HashMap中添加元素后所执行的方法，详情本篇文章就不做介绍了，可以自己去看看HashMap中内部的实现逻辑。
总结
本篇文章基于Redis的缓存淘汰策略介绍了LRU算法的背景，基本概念。基于LinkedHashMap的特性实现了简易版的LRU算法，并介绍LinkedHashMap内部的基本原理来帮助大家更好的理解LRU算法的实现。
赞 (0)