1.LRU是什么?
LRU,Least Recently Used,最近最少使用,也就是优先淘汰最近最少使用的元素。
2.如何使用LinkedHashMap实现LRU?
简而言之,就是将LinedHashMap的accessOrder设为true即可。
demo实现如下:
package com.hikvision.dai.didi;
import java.util.LinkedHashMap;
import java.util.Map;
/**
* @Classname LRU
* @Description LRU
* @Date 2023/4/22 21:16
* @Created by Chamption-Dai
*/
public class LRU<K, V> extends LinkedHashMap<K, V> {
/**
* 保存缓存的容量
*/
private Integer cache;
/**
* 构造函数
*
* @param cache 缓存容量
* @param loadFactor 负载因子
*/
public LRU(int cache, float loadFactor) {
//linkedHashMap中的accessOrder设为true
super(cache, loadFactor, true);
this.cache = cache;
}
/**
* 重写removeEldestEntry()方法设置何时移除旧元素
*
* @param eldest 最好使用的元素
* @return boolean
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
//当元素容量大鱼设置的缓存容量,就开始移除最少使用的元素
return size() > this.cache;
}
public Integer getInitialCap() {
return cache;
}
public void setInitialCap(Integer cache) {
this.cache = cache;
}
}
测试一下:
package com.hikvision.dai.didi;
/**
* @Classname LRUTest
* @Description LRUTest
* @Date 2023/4/22 21:00
* @Created by Chamption-dai
*/
public class LRUTest {
public static void main(String[] args) {
//设置缓存大小为5,负载因子为0.75f
LRU<String, Integer> lru = new LRU<>(5, 0.75f);
//添加元素:
lru.put("1", 1);
lru.put("2", 2);
lru.put("3", 3);
lru.put("4", 4);
lru.put("5", 5);
System.out.println(lru); //输出:{1=1, 2=2, 3=3, 4=4, 5=5}
lru.put("100", 100);
System.out.println(lru); //输出:{2=2, 3=3, 4=4, 5=5, 100=100} ,现象:最开始添加的“最老“的”1=1被移除了
//使用entry:("3",3)
lru.get("3");
//调用get()或者put(),LinkedHashMap中的双向链表会把对应的元素放在链表的末尾,3=3目前是最年轻的
System.out.println(lru); //输出:{2=2, 4=4, 5=5, 100=100, 3=3}。
lru.put("200", 200);
System.out.println(lru); //{4=4, 5=5, 100=100, 3=3, 200=200},现象,最老的“2=2”被移除了
}
}
3.LinkedHashMap源码分析
3.1 LinkedHashMap简介
LinkedHashMap内部维护了一个双向链表,能保证元素按插入的顺序访问,也能以访问顺序访问,可以用来实现LRU缓存策略。
LinkedHashMap可以看成是 LinkedList + HashMap。
3.2 继承体系
3.3 内部数据存储结构
HashMap是(数组 + 单链表 + 红黑树)的存储结构,那LinkedHashMap是怎么存储的呢?
通过上面的继承体系,我们知道它继承了HashMap,所以它的内部也有这三种结构,但是它还额外添加了一种“双向链表”的结构存储所有元素的顺序。
添加删除元素的时候需要同时维护在HashMap中的存储,也要维护在LinkedList中的存储,所以性能上来说会比HashMap稍慢。
3.4源码解析
属性:
/**
* 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;
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
* 是否按访问顺序排序
*/
final boolean accessOrder;
构造方法:
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
前四个构造方法accessOrder都等于false,说明双向链表是按插入顺序存储元素。
最后一个构造方法accessOrder从构造方法参数传入,如果传入true,则就实现了按访问顺序存储元素,这也是实现LRU缓存策略的关键。
afterNodeInsertion(boolean evict)方法
在节点插入之后做些什么,在HashMap中的putVal()方法中被调用,可以看到HashMap中这个方法的实现为空。
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);
}
}
//上述实现LRU重写了该方法,重写removeEldestEntry()可以实现不同的缓存机制
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
evict,英:/ɪˈvɪkt/ 美:/ɪˈvɪkt/ 驱逐、逐出的意思。
(1)如果evict为true,且头节点不为空,且确定移除最老的元素,那么就调用HashMap.removeNode()把头节点移除(这里的头节点是双向链表的头节点,而不是某个桶中的第一个元素);
(2)HashMap.removeNode()从HashMap中把这个节点移除之后,会调用afterNodeRemoval()方法;
(3)默认removeEldestEntry()方法返回false,也就是不删除元素。
afterNodeAccess(Node e)方法
在节点访问之后被调用,主要在put()已经存在的元素或get()时被调用,如果accessOrder为true,调用这个方法把访问到的节点移动到双向链表的末尾。
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 如果accessOrder为true,并且访问的节点不是尾节点
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 把p节点从双向链表中移除
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
// 把p节点放到双向链表的末尾
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
// 尾节点等于p
tail = p;
++modCount;
}
}
(1)如果accessOrder为true,并且访问的节点不是尾节点;
(2)从双向链表中移除访问的节点;
(3)把访问的节点加到双向链表的末尾;(末尾为最新访问的元素)
afterNodeRemoval(Node e)方法
在节点被删除之后调用的方法。
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
直接将节点从双向链表中移除。
get(Object key)方法
获取元素
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;
}
如果查找到了元素,且accessOrder为true,则调用afterNodeAccess()方法把访问的节点移到双向链表的末尾。
源码总结
(1)LinkedHashMap继承自HashMap,具有HashMap的所有特性;
(2)LinkedHashMap内部维护了一个双向链表存储所有的元素;
(3)如果accessOrder为false,则可以按插入元素的顺序遍历元素;
(4)如果accessOrder为true,则可以按访问元素的顺序遍历元素;
(5)LinkedHashMap的实现非常精妙,很多方法都是在HashMap中留的钩子(Hook),直接实现这些Hook就可以实现对应的功能了,并不需要再重写put()等方法;
(6)默认的LinkedHashMap并不会移除旧元素,如果需要移除旧元素,则需要重写removeEldestEntry()方法设定移除策略;文章来源:https://www.toymoban.com/news/detail-423502.html
(7)LinkedHashMap可以用来实现LRU缓存淘汰策略;文章来源地址https://www.toymoban.com/news/detail-423502.html
到了这里,关于LinkedHashMap如何实现LRU缓存淘汰策略?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!