如果是默认的,则是按照添加顺序,即 accessOrder 默认是 false。
源码实现
如果看 LinkedHashMap 内部源码,会发现,内部确实维护了一个链表:
/**
双向链表的头,最久访问的
*/
transientLinkedHashMap.Entry<K,V>head;
/**
双向链表的尾,最新访问的
*/
transientLinkedHashMap.Entry<K,V>tail;
而这个 LinkedHashMap.Entry 内部也维护了双向链表必须的元素,before,after:
/**
HashMap.Node subclass for normal LinkedHashMap entries.
*/
staticclassEntry<K,V>extendsHashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(inthash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
在添加元素的时候,会追加到尾部。
Node<K,V>newNode(inthash, K key, Vvalue, Node<K,V> e){
LinkedHashMap.Entry<K,V> p =
newLinkedHashMap.Entry<K,V>(hash, key,value, e);
linkNodeLast§;
returnp;
}
// link at the end of list
privatevoidlinkNodeLast(LinkedHashMap.Entry<K,V> p){
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if(last ==null)
head = p;
else{
p.before = last;
last.after = p;
}
}
在 get 的时候,会根据 accessOrder 属性,修改链表顺序:
publicVget(Object key){
Node<K,V> e;
if((e = getNode(hash(key), key)) ==null)
returnnull;
if(accessOrder)
afterNodeAccess(e);
returne.value;
}
voidafterNodeAccess(Node<K,V> e){// move node to last
LinkedHashMap.Entry<K,V> last;
if(accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after =null;
if(b ==null)
head = a;
else
b.after = a;
if(a !=null
【一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义】浏览器打开:.hn/FTf 免费领取
)
a.before = b;
else
last = b;
if(last ==null)
head = p;
else{
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
同时注意:这里修改了 modCount,即使是读操作,并发也是不安全的。
如何实现 LRU 缓存?
LRU 缓存:LRU(Least Recently Used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。
LinkedHashMap 并没有帮助我们实现具体,需要我们自己实现 。具体实现方法是 removeEldestEntry 方法。
一起来看看原理。
首先,HashMap 在 putVal 方法最后,会调用 afterNodeInsertion 方法,其实就是留给 LinkedHashMap 的。而 LinkedHashMap 的具体实现则是根据一些条件,判断是否需要删除 head 节点。
源码如下:
voidafterNodeInsertion(booleanevict){// 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);
}
}
evict 参数表示是否需要删除某个元素,而这个 if 判断需要满足的条件如上:head 不能是 null,调用 removeEldestEntry 方法,返回 true 的话,就删除这个 head。而这个方法默认是返回 false 的,等待着你来重写。
所以,removeEldestEntry 方法的实现通常是这样:
publicbooleanremoveEldestEntry(Map.Entry<K, V> eldest){
returnsize() > capacity;
}
如果长度大于容量了,那么就需要清除不经常访问的缓存了。afterNodeInsertion 会调用 removeNode 方法,删除掉 head 节点 —— 如果 accessOrder 是 true 的话,这个节点就是最不经常访问的节点。