开篇
LinkedHashMap是HashMap的变种，有一些额外的特性其中最重要的就是维护数据插入的有序性，这篇文章就是为了讲清楚LinkedHashMap的实现细节。
LinkedHashMap类图
LinkedHashMap类图
LinkedHashMap和HashMap的差别
- LinkedHashMap可以认为是HashMap+LinkedList，即它既使用HashMap操作数据结构，又使用LinkedList维护插入元素的先后顺序。
- LinkedHashMap除了维持Map的有序性质外，其他和HashMap是一模一样的，
LinkedHashMap实现细节
从LinkedHashMap的类依赖图可以看出来，LinkedHashMap其实是继承自HashMap类，所以LinkedHashMap的所有接口基本上都是继承自己HashMap类，当然也存在一个非常核心的差别。
- LinkedHashMap用于存储key/value的结果是继承自己HashMap的，但是LinkedHashMap本身维护着一个有序列表。
- head是LinkedHashMap的列表头，tail是LinkedHashMap的列表尾，通过这两个变量保证了维护LinkedHashMap的插入顺序。
- LinkedHashMap的Entry相比HashMap.Node对象增加了before和after两个变量，由于指向前后节点。
- LinkedHashMap通过重写HashMap的newNode方法，创建Entry对象并在内部初始化了HashMap当中的Node节点。
- 在创建Entry的newNode过程中通过linkNodeLast()方法按照put顺序维持LinkHashMap的有序性。
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
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);
}
}
// 保存HashMap有序列表的头
transient LinkedHashMap.Entry<K,V> head;
// 保存HashMap有序列表的尾
transient LinkedHashMap.Entry<K,V> tail;
final boolean accessOrder;
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;
}
}
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;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
LinkedHashMap实际存储结构图
image.png
说明：
上述按照Entry1->Entry6的顺序进行存储的，不过这个图有些问题，正常的情况是head就是Entry1的对象，tail是Entry6的对象。
