LinkedHashMap 源码解析

特性

LinkedHashMap 继承自 HashMap，像是 put、get、扩容等操作都是沿袭自父类。

只是在此基础上，重写了对相关结点的钩子方法，去构建了结点的双向链表。

这样做的目的，就是为了维护可预测的结点遍历顺序。

• 这种遍历顺序默认是结点的 插入顺序
  （当 key 已存在的情况下，put 的更新时不会改变原有的顺序。），可以设置为 访问顺序
  。
• 可以以 Map 为基准构建，将 Map 中结点的原有顺序作为遍历顺序。
• 基于 访问顺序
  ，可以方便地实现 LRU 缓存。
• 初始容量和负载因子，同 HashMap。
• 对视图的操作不会影响原有数据结构的顺序。
• 可以重写 removeEldestEntry(Map.Entry)
  来自定义插入新结点时，对旧节点的操作。

结点

static class Entry<K,V> extends HashMap.Node<K,V> {
// 注意：HashMap.TreeNode 是继承自该类，所以当 LinkedHashMap 树化时也是支持顺序的。
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
复制代码

构造函数

public LinkedHashMap(int initialCapacity, float loadFactor) {
// 容量和负载因子,完全沿袭 HashMap
super(initialCapacity, loadFactor);
// 默认是插入顺序
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
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;
}
复制代码

钩子方法

在 HashMap 源码解析的文章曾经说到， HashMap 定义了三个钩子方法，由子类实现。子类通过这三个方法，在结点插入、访问、删除的过程中，维护子类添加的结点属性。

而在 LinkedHashMap 中，新增的结点属性，所代表的的就是结点之间的顺序。

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;
}
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// evict:是否删除最旧的结点
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
// 删除结点, HashMap 的方法
removeNode(hash(key), key, null, false, true);
}
}
void afterNodeAccess(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)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
复制代码

结点构造方法

从上面可以看到，afterNodeInsertion 定义的是结点插入之后，是否删除最旧的结点。

没有提及结点插入时，如何维系顺序。

这就需要子类重写 HashMap 的几个结点构造方法：newNode、replacementNode、newTreeNode、replacementTreeNode。

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<>(hash, key, value, e);
// 将新结点放在最后, 默认的插入顺序
linkNodeLast(p);
return p;
}
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
LinkedHashMap.Entry<K,V> t =
new LinkedHashMap.Entry<>(q.hash, q.key, q.value, next);
// 替换结点, 将顺序属性也已迁移掉
transferLinks(q, t);
return t;
}
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
TreeNode<K,V> p = new TreeNode<>(hash, key, value, next);
// 将新结点放在最后, 默认的插入顺序
linkNodeLast(p);
return p;
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
TreeNode<K,V> t = new TreeNode<>(q.hash, q.key, q.value, next);
// 替换结点, 将顺序属性也已迁移掉
transferLinks(q, t);
return t;
}
复制代码

结点顺序维护方法

其实和父类差不多，多的就是两个维护顺序的方法。

private void linkNodeLast(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;
}
}
// apply src's links to dst
private void transferLinks(LinkedHashMap.Entry<K,V> src,
LinkedHashMap.Entry<K,V> dst) {
LinkedHashMap.Entry<K,V> b = dst.before = src.before;
LinkedHashMap.Entry<K,V> a = dst.after = src.after;
if (b == null)
head = dst;
else
b.after = dst;
if (a == null)
tail = dst;
else
a.before = dst;
}
复制代码