一、摘要

在集合系列的第一章，咱们了解到，Map的实现类有HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties等等。

本文主要从数据结构和算法层面，探讨LinkedHashMap的实现。

二、简介

LinkedHashMap可以认为是HashMap+LinkedList，它既使用HashMap操作数据结构，又使用LinkedList维护插入元素的先后顺序，内部采用双向链表（doubly-linked list）的形式将所有元素（ entry ）连接起来。

LinkedHashMap继承了HashMap，允许放入key为null的元素，也允许插入value为null的元素。从名字上可以看出该容器是LinkedList和HashMap的混合体，也就是说它同时满足HashMap和LinkedList的某些特性，可将LinkedHashMap看作采用Linked list增强的HashMap。

打开 LinkedHashMap 源码，可以看到主要三个核心属性：

public class LinkedHashMap<K,V>     extends HashMap<K,V>     implements Map<K,V>{      /**双向链表的头节点*/     transient LinkedHashMap.Entry<K,V> head;      /**双向链表的尾节点*/     transient LinkedHashMap.Entry<K,V> tail;      /**       * 1、如果accessOrder为true的话，则会把访问过的元素放在链表后面，放置顺序是访问的顺序       * 2、如果accessOrder为false的话，则按插入顺序来遍历       */       final boolean accessOrder; }

LinkedHashMap 在初始化阶段，默认按插入顺序来遍历

public LinkedHashMap() {         super();         accessOrder = false; }

LinkedHashMap 采用的 Hash 算法和 HashMap 相同，不同的是，它重新定义了数组中保存的元素Entry，该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表。

源码如下：

static class Entry<K,V> extends HashMap.Node<K,V> {         //before指的是链表前驱节点，after指的是链表后驱节点         Entry<K,V> before, after;         Entry(int hash, K key, V value, Node<K,V> next) {             super(hash, key, value, next);         } }

可以直观的看出，双向链表头部插入的数据为链表的入口，迭代器遍历方向是从链表的头部开始到链表尾部结束。

除了可以保迭代历顺序，这种结构还有一个好处：迭代LinkedHashMap时不需要像HashMap那样遍历整个table，而只需要直接遍历header指向的双向链表即可，也就是说LinkedHashMap的迭代时间就只跟entry的个数相关，而跟table的大小无关。

三、常用方法介绍

3.1、get方法

get方法根据指定的key值返回对应的value。该方法跟HashMap.get()方法的流程几乎完全一样，默认按照插入顺序遍历。

public V get(Object key) {         Node<K,V> e;         if ((e = getNode(hash(key), key)) == null)             return null;         if (accessOrder)             afterNodeAccess(e);         return e.value; }

如果