LinkedHashMap的数据结构跟HashMap类似，只是在节点上多加了指向前和向后的两个属性，也可以概括为：数组+链表（双向）+红黑树（java8增加了红黑树），如下图所示：

一、类的定义

public class LinkedHashMap<K,V>     extends HashMap<K,V>     implements Map<K,V> {}

二、存储单元

        LinkedHashMap的基本存储单元也是继承HashMap的存储单元，新增了两个节点属性，一个指向前，一个向后。

// 定义在LinkedHashMap类中 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类中 static class Node<K,V> implements Map.Entry<K,V> {         final int hash;         final K key;         V value;         Node<K,V> next;          Node(int hash, K key, V value, Node<K,V> next) {             this.hash = hash;             this.key = key;             this.value = value;             this.next = next;         } }

三、构造函数

        构造函数主要是初始化父类的属性值，LinkedHashMap新增的就只有一个：

boolean accessOrder = false;// 链表是否按照节点访问顺序排序，true：是，false：否。它起到什么作用，我在文章后面会解析。

public LinkedHashMap() {         // 调用父类构造器         super();         accessOrder = false; }

// 指定初始容量 public LinkedHashMap(int initialCapacity) {         super(initialCapacity);         accessOrder = false; }

// 指定初始容量和负载因子（负载因子一般使用默认的） public LinkedHashMap(int initialCapacity, float loadFactor) {         super(initialCapacity, loadFactor);         accessOrder = false; }

// 指定初始容量，负载因子，是否按访问顺序排序 public LinkedHashMap(int initialCapacity,                          float loadFactor,                          boolean accessOrder) {         super(initialCapacity, loadFactor);         this.accessOrder = accessOrder; }

// 可以把其他map的元素加载进来 public LinkedHashMap(Map<? extends K, ? extends V> m) {}

四、双向链表的构造

        LinkedHashMap构建双向链表是通过重写父类HashMap的方法newNode(int hash, K key, V value, Node<K,V> e)实现的。当往LinkedHashMap中插入新节点的时候，其直接调用父类HashMap的put方法，put方法生产新节点的时候会调用newNode方法。

        来看看重写之后的newNode方法做了什么：

 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;         // 如果尾节点为空，说明p是头节点         if (last == null)             head = p;         else {             // 前后节点的链接             p.before = last;             last.after = p;         } }

五、遍历实现

        LinkedHashMap的遍历是通过LinkedHashIterator抽象类实现的，它从双向链表的头节点开始遍历，直到链表的尾部。

abstract class LinkedHashIterator {         LinkedHashMap.Entry<K,V> next;         LinkedHashMap.Entry<K,V> current;         int expectedModCount;          // 构造器初始化的时候把头节点传入         LinkedHashIterator() {             next = head;             // fast-fail机制，遍历时避免节点被改变             expectedModCount = modCount;             current = null;         }         // 迭代器的hasNext()方法会调用该方法         public final boolean hasNext() {             return next != null;         }         // 迭代器的next()方法会调用该方法         final LinkedHashMap.Entry<K,V> nextNode() {             LinkedHashMap.Entry<K,V> e = next;             if (modCount != expectedModCount)                 throw new ConcurrentModificationException();             if (e == null)                 throw new NoSuchElementException();             current = e;             // 对下一个节点赋值             next = e.after;             return e;         } }

        对比LinkedHashMap与HashMap的遍历：

public static void main(String[] args) {         Map<String,String> linkedHashMap = new LinkedHashMap<String, String>();         linkedHashMap.put("NO1","小明");         linkedHashMap.put("NO2","小赵");         linkedHashMap.put("NO3","小周");          System.out.println("----遍历LinkedHashMap----");         for(Map.Entry entry:linkedHashMap.entrySet()){             System.out.println(entry.getKey() + ":" + entry.getValue());         }          Map<String,String> hashMap = new HashMap<String, String>();         hashMap.put("NO1","小明");         hashMap.put("NO2","小赵");         hashMap.put("NO3","小周");          System.out.println("-----遍历HashMap-------");         for(Map.Entry entry:hashMap.entrySet()){             System.out.println(entry.getKey() + ":" + entry.getValue());         } }

        测试结果：

        从上面的测试结果可以看出，LinkedHashMap确实可以对节点进行先进先出的排序。而HashMap的排序顺序是不确定的。

六、访问顺序排序

        文章开头讨论过属性accessOrder，它决定链表是否按节点访问的顺序排序，如果为true就是访问顺序排序，这时当某个存在的节点被操作过（比如被get（）方法调用过，或者值被替换过），那么先进先出的排序就会打乱，被访问的节点会被排到最后。看一个例子：

public static void main(String[] args) {         // 指定accessOrder为true         Map<String,String> linkedHashMap = new LinkedHashMap<String, String>(10,0.75f,true);         linkedHashMap.put("NO1","小明");         linkedHashMap.put("NO2","小赵");         linkedHashMap.put("NO3","小周");         // 对NO1进行get操作         linkedHashMap.get("NO1");          System.out.println("----按访问顺序遍历LinkedHashMap----");         for(Map.Entry entry:linkedHashMap.entrySet()){             System.out.println(entry.getKey() + ":" + entry.getValue());         } }

        测试结果：

        访问排序的实现是在每个操作函数里面调用了方法afterNodeAccess，来看看它的实现：

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;         } }

七、总结

        LinkedHashMap在HashMap的基础上多维护了一条双向链表，其最重要特征就是可以对map进行先进先出的遍历操作，如有需要也可以对其按访问顺序遍历。

        以上就是我对LinkedHashMap的原理的理解，如有错误之处，请批评和指正。