一 成员变量解析
/**
* 双向链表头节点
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* 双向链表尾节点
*/
transient LinkedHashMap.Entry<K,V> tail;
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
/**
* true按访问排序 false按插入排序
*/
final boolean accessOrder;
二 关键方法解析
1 添加元素
//该方法继承于HashMap，LinkedHashMap只重写了newNode()和afterNodeAccess()
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// LinkedHashMap重写newNode()方法
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// LinkedHashMap重写该方法
// 如果key对应的entry存在，按访问更新链表顺序
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
// 将节点插入链表尾部，保证插入的顺序不变
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
// 如果尾部为null 则将p设为头部
if (last == null)
head = p;
else {
// 如果last不为null 则将p放到last后面，至此p为尾部节点
p.before = last;
last.after = p;
}
}
// LinkedHashMap将此函数重写，用于当访问某一节点后，将该节点放到尾部
// 所以最近最少访问的节点在头部，最频繁访问的节点在尾部
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 若accessOrder为true且节点e不是尾节点，则设置e为tail节点
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)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
2 获取元素
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
// 若accessOrder为true，则将访问的节点放入链表尾部
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
LinkedHashMap 继承了 HashMap，是 HashMap 的子类，所以其他方法和 HashMap 基本相同，在此不必赘述
三 LinkedHashMap可以实现LRU缓存调度算法
前面讲了LinkedHashMap添加元素，删除、修改元素就不说了，比较简单，和HashMap+LinkedList的删除、修改元素大同小异，下面讲一个新的内容。
LinkedHashMap可以用来作缓存，比方说LRUCache，看一下这个类的代码，很简单，就十几行而已：
public class LRUCache extends LinkedHashMap {
public LRUCache(int maxSize)
{
super(maxSize, 0.75F, true);
maxElements = maxSize;
}
protected boolean removeEldestEntry(java.util.Map.Entry eldest)
{
return size() > maxElements;
}
private static final long serialVersionUID = 1L;
protected int maxElements;
}
LinkedHashMap 可以实现LRU算法的缓存基于两点：
- LinkedList 首先它是一个 Map，Map是基于K-V的，和缓存一致
- LinkedList 提供了一个 boolean 值可以让用户指定是否实现LRU
那么，首先我们了解一下什么是LRU：LRU即Least Recently Used，最近最少使用，也就是说，当缓存满了，会优先淘汰那些最近最不常访问的数据。比方说数据a，1天前访问了；数据b，2天前访问了，缓存满了，优先会淘汰数据b。
我们看一下LinkedList带boolean型参数的构造方法：
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
就是这个accessOrder，它表示：
（1）false，所有的Entry按照插入的顺序排列
（2）true，所有的Entry按照访问的顺序排列
第二点的意思就是，如果有1，2，3这3个Entry，那么访问了1，就把1移到尾部去，即2，3，1。每次访问都把访问的那个数据移到双向队列的尾部去，那么每次要淘汰数据的时候，双向队列最头的那个数据不就是最不常访问的那个数据了吗？换句话说，双向链表最头的那个数据就是要淘汰的数据。
“访问”，这个词有两层意思：
（1）根据Key拿到Value，也就是get方法
（2）修改Key对应的Value，也就是put方法
