LinkedHashMap源码解析

HashMap底层是数组 + (链表 / 红黑树)，元素是无序的，LinkedHashMap有序可以按两种顺序排列，一种是按照插入的顺序，一种是按照访问的顺序（初始化 LinkedHashMap 对象时设置 accessOrder 参数为 true），内部是靠建立一个双向链表来维护这个顺序的，在每次插入、删除后，都会调用一个函数来进行双向链表的维护，这也是实现LRU Cache功能的基础。下面是几个比较重要的结论，可从后面的源码解析中得到证据。

1. LinkedHashMap继承了HashMap，所以和HashMap的底层数据结构是一样的，都是数组+链表+红黑树，扩容机制也一样。
2. LinkedHashMap是通过双向链表来维护数据的，与HashMap的拉链式存储不同。
3. LinkedHashMap存储顺序与添加顺序是一样得，同时可以根据accessOrder参数 来决定是否在访问时移动元素，以实现 LRU功能。

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> { /** * 在 HashMap.Node节点 的基础上增加了 “前继节点” 和 “后继节点” 这种双向链表的功能特性 */ static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key,