HashMap是Java%20Collection%20Framework的重要成员，也是Map族中最为常用的一种。不过遗憾的是，HashMap是无序的，也就是说，迭代HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。HashMap的这一缺点往往会造成诸多不便，因为在有些场景中，的确需要用到一个可以保持插入顺序的Map。庆幸的是，JDK为解决了这个问题，它为HashMap提供了一个子类%20——%20LinkedHashMap。虽然LinkedHashMap增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了迭代顺序==。特别地，==该迭代顺序可以是插入顺序，也可以是访问顺序。因此，根据链表中元素的顺序可以将LinkedHashMap分为：保持插入顺序的LinkedHashMap和保持访问顺序的LinkedHashMap，其中LinkedHashMap的默认实现是按插入顺序排序的。更直观地，下图很好地还原了LinkedHashMap的原貌：HashMap和双向链表的密切配合和分工合作造就了LinkedHashMap。特别需要注意的是，next用于维护HashMap各个桶中的Entry链，before、after用于维护LinkedHashMap的双向链表，虽然它们的作用对象都是Entry，但是各自分离，是两码事儿。特别地，由于LinkedHashMap是HashMap的子类，所以LinkedHashMap自然会拥有HashMap的所有特性。比如，LinkedHashMap也最多只允许一条Entry的键为Null(多条会覆盖)，但允许多条Entry的值为Null。此外，LinkedHashMap 也是 Map 的一个非同步的实现。此外，LinkedHashMap还可以用来实现LRU (Least recently used, 最近最少使用)算法。

2.1、LinkedHashMap定义及构造函数

本质上，HashMap和双向链表合二为一即是LinkedHashMap。JDK1.8中LinkedHashMap的定义源码如下：

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
 /**
  * HashMap.Node subclass for normal LinkedHashMap entries.
  */
 static class Entry<K,V> extends HashMap.Node<K,V> {
  //再加两个引用，分别指向前一个插入的Entry与后一个插入的Entry
     Entry<K,V> before, after;
     Entry(int hash, K key, V value, Node<K,V> next) {
         super(hash, key, value, next);
     }
 }
 /**
  * The head (eldest) of the doubly linked list.
  * 头节点引用
  */
 transient LinkedHashMap.Entry<K,V> head;
 /**
  * The tail (youngest) of the doubly linked list.
  * 尾节点引用
  */
 transient LinkedHashMap.Entry<K,V> tail;
 /**
  * The iteration ordering method for this linked hash map: <tt>true</tt>
  * for access-order, <tt>false</tt> for insertion-order.
  * true表示按照访问顺序迭代，false时表示按照插入顺序 
  * @serial
  */
 final boolean accessOrder;
 ... 
}

LinkedHashMap采用的hash算法和HashMap相同，但是它重新定义了Entry。LinkedHashMap中的Entry继承了HashMap.Node，但增加了两个指针before 和 after，它们分别用于维护双向链接列表。特别需要注意的是，**next**用于维护HashMap各个Node的连接顺序，before、after用于维护Entry插入的先后顺序。LinkedHashMap的5大构造函数都是在HashMap的构造函数的基础上实现的，分别如下：

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);
}
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

2.2、LinkedHashMap的快速存取

在HashMap中最常用的两个操作就是：put(Key,Value) 和 get(Key)。同样地，在 LinkedHashMap 中最常用的也是这两个操作。对于put(Key,Value)方法而言，LinkedHashMap完全继承了HashMap的 put(Key,Value) 方法，只是对putVal(hash,key, value, onlyIfAbsent,evict)方法所调用的afterNodeAccess方法和afterNodeInsertion方法进行了重写；对于get(Key)方法，LinkedHashMap则直接对它进行了重写。下面结合JDK源码看 LinkedHashMap 的存取实现。HashMap的putVal源码，上一节中已经分析过，直接来看LinkedHashMap对afterNodeAccess和afterNodeInsertion方法的实现：

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);
    }
}
/**
 * 如果map应该删除最老的节点，返回true
 * 这个方法在被put和putAll方法被调用，当向map中插入一个新的entry时被执行。这个方法提供了当一个新的entry被添加到linkedHashMap中，删除最老节点的机会。
 * 
 * 这个方法是很有用的，可以通过删除最老节点来减少内存消耗，避免溢出。
 * 
 * 简单的例子：这个方法的重写将map的最大值设为100，到100时，每次增一个entry，就删除一次最老节点。
 * 
 *     private static final int MAX_ENTRIES = 100;
 *
 *     protected boolean removeEldestEntry(Map.Entry eldest) {
 *        return size() > MAX_ENTRIES;
 *     }
 *
 * 这个方法一般不会直接修改map，而是通过返回true或者false来控制是否修改map。
 *
 *
 * @param    eldest 最老的节点（即头节点）
 * @return   如果map应该删除头节点就返回true，否则返回false
 */
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

以上afterNodeInsertion方法由于removeEldestEntry方法默认一直返回的false而无执行意义。也就意味着如果想要让它有意义必须重写removeEldestEntry方法。

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

可见仅有accessOrder为true时，且访问节点不等于尾节点时，该方法才有意义。通过before/after重定向，将新访问节点链接为链表尾节点。LinkedHashMap的get操作：

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    //当accessOrder为true时，才会出现个性化逻辑
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}
//以下是HashMap中的getNode方法
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

在LinkedHashMap的get方法中，通过HashMap中的getNode方法获取Node对象。注意这里的afterNodeAccess方法，如果链表中元素的排序规则是按照插入的先后顺序排序的话，该方法什么也不做；如果链表中元素的排序规则是按照访问的先后顺序排序的话，则将e移到链表的末尾处。

2.3、LinkedHashMap与LRU算法

到此为止，已经分析完了LinkedHashMap的存取实现，这与HashMap大体相同。LinkedHashMap区别于HashMap最大的一个不同点是，前者是有序的，而后者是无序的。为此，LinkedHashMap增加了两个属性用于保证顺序，分别是双向链表头结点header和标志位accessOrder。header是LinkedHashMap所维护的双向链表的头结点，而accessOrder用于决定具体的迭代顺序。当accessOrder标志位为true时，表示双向链表中的元素按照访问的先后顺序排列，可以看到，虽然Entry插入链表的顺序依然是按照其put到LinkedHashMap中的顺序，但put和get方法均有判断accessOrder的值。如果accessOrder为true，put时将新插入的元素放入到双向链表的尾部，get时将当前访问的Entry移到双向链表的尾部。当标志位accessOrder的值为false时，表示双向链表中的元素按照Entry插入LinkedHashMap到中的先后顺序排序，即每次put到LinkedHashMap中的Entry都放在双向链表的尾部，这样遍历双向链表时，Entry的输出顺序便和插入的顺序一致，这也是默认的双向链表的存储顺序。测试代码

@Test
public void testLinkedHashMap() {
    Map<String, String> map = new HashMap<>(128);
    System.out.println("------HashMap------");
    map.put("first", "a");
    map.put("second", "b");
    map.put("third", "c");
    map.put("fourth", "d");
    map.put("fifth", "e");
    map.put("sixth", "f");
    map.forEach((key,value) -> {
        System.out.println("key=" + key + ",value=" + value);
    });
    map.clear();
    System.out.println("------LinkedHashMap------");
    map = new LinkedHashMap<>(128);
    map.put("first", "a");
    map.put("second", "b");
    map.put("third", "c");
    map.put("fourth", "d");
    map.put("fifth", "e");
    map.put("sixth", "f");
    map.forEach((key,value) -> {
        System.out.println("key=" + key + ",value=" + value);
    });
}

运行结果如下，HashMap不保证有序而LinkedHashMap默认按迭代顺序和插入的顺序一致。前面介绍的LinkedHashMap的五种构造方法，前四个构造方法都将accessOrder设为false，说明默认是按照插入顺序排序的；而第五个构造方法可以自定义传入的accessOrder的值。当要用LinkedHashMap实现LRU算法时，就需要调用该构造方法并将accessOrder置为true。使用LinkedHashMap实现LRU的必要前提是将accessOrder标志位设为true以便开启按访问顺序排序的模式。可以看到，无论是put方法还是get方法，都会导致目标Entry成为最近访问的Entry，因此就把该Entry加入到了双向链表的末尾。这样，便把最近使用的Entry放入到了双向链表的后面。多次操作后，双向链表前面的Entry便是最近没有使用的，这样当节点个数满的时候，删除最前面的Entry即可，因为它就是最近最少使用的Entry。

public class SomeTest {
    @Test
    public void testLru() {
        LRU<Character, Integer> lru = new LRU<>(8);
        String s = "abcdefghijkl";
        for (int i = 0; i < s.length(); i++) {
            lru.put(s.charAt(i), i + 1);
        }
        System.out.println("LRU的大小： " + lru.size());
        System.out.println(lru);
        System.out.println("LRU的中key为h的value值： " + lru.get('h'));
        System.out.println(lru);
        lru.put('z', 26);
        System.out.println(lru);
    }
    public static class LRU<K, V> extends LinkedHashMap<K, V> {
        private int cacheSize;
        public LRU(int cacheSize) {
            super(cacheSize, 0.75f, true);
            this.cacheSize = cacheSize;
        }
        /**
         * 重写LinkedHashMap中的removeEldestEntry方法，当LRU中元素多余cacheSize个时，删除最老的节点（即最不经常使用的元素）
         * @param eldest
         * @return
         */
        protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
            return size() > getCacheSize();
        }
        public int getCacheSize() {
            return cacheSize;
        }
    }
}

运行结果：

LRU的大小：8
{e=5, f=6, g=7, h=8, i=9, j=10, k=11, l=12}
LRU的中key为h的value值：8
{e=5, f=6, g=7, i=9, j=10, k=11, l=12, h=8}
{f=6, g=7, i=9, j=10, k=11, l=12, h=8, z=26}