1. 简介
Map是一种关联容器，其中键是唯一的，每个键都有与之对应的值，我们可以通过键获取到唯一的值。JDK中，HashMap是其中的一种实现，只不过HashMap是无序的，不能记录插入顺序与访问顺序，而LinkedHashMap恰好能记录插入顺序或访问顺序，至于为什么能够实现，是因为它在内部维护了一个链表专门来记录插入顺序或访问顺序，接着我们来剖析其内部实现。
2. 实现
类继承关系
从下面的类继承关系可以看出LinkedHashMap是继承了HashMap的，内部复用了HashMap的代码。
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>{}
结点结构
这里的Entry类继承了HashMap.Node类，并增加了两个引用字段before, after，可以看出该链表是一个双向链表,这个类其实是为链表准备的，两个引用分别指向当前链表结点前后结点。
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);
}
}
因为从JDK8开始，HashMap开始采用红黑树，当每个桶中的链表长度大于8时会转为红黑树存储。所以为了保证TreeNode能够插入到LinkedHashMap维护的链表，TreeNode需要继承LinkedHashMap.Entry。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
属性
// 链表的头结点
transient LinkedHashMap.Entry<K,V> head;
// 链表的尾结点
transient LinkedHashMap.Entry<K,V> tail;
// 为false表示链表中结点按照键值对的插入顺序排序，为true表示按照访问顺序，即最近插入与访问的结点都在链表尾部
final boolean accessOrder;
构造函数
以下构造函数都是先调用父类的构造函数创建一个HashMap，接着将accessOrder设置为false表示按照链表按照键值对插入顺序排序
public LinkedHashMap(int initialCapacity, float loadFactor) {
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);
}
// 这里讲accessOrder设置为给定值
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
创建结点
每次我们创建HashMap使用的结点都使用以下两个方法创建，内部实现会维护双向链表
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;
}
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
// 创建一个红黑树结点
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
// 将该结点添加到双向链表尾部
linkNodeLast(p);
return p;
}
// 将该结点添加到双向链表尾部
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;
}
}
get方法
public V get(Object key) {
Node<K,V> e;
// 找到key对应的Node结点，为null则不存在，返回null
if ((e = getNode(hash(key), key)) == null)
return null;
// 如果accessOrder为true则调用afterNodeAccess方法将最近访问的结点从链表中移动到链表尾部
if (accessOrder)
afterNodeAccess(e);
//返回找到的值
return e.value;
}
// 将结点e移动到链表尾部
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.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;
}
}
其他方法
// 执行remove方法从哈希表中删除键值对后调用，将该结点从链表中移除
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;
}
// 执行put方法成功插入后调用，目的是移除最旧的结点，即头结点
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);
}
}
