說到集合類，之前介紹的ArrayList類，HashMap可能是大家日常用的最多的類，但是對于另一個集合類 LinkedHashMap,可能大家用的不多，但是這種鏈?zhǔn)焦＜希行┣闆r確實特別好用。

1、LinkedHashMap 定義

LinkedHashMap 是基于 HashMap 實現(xiàn)的一種集合，具有 HashMap 集合上面所說的所有特點，除了 HashMap 無序的特點，LinkedHashMap 是有序的，因為 LinkedHashMap 在 HashMap 的基礎(chǔ)上單獨維護了一個具有所有數(shù)據(jù)的雙向鏈表，該鏈表保證了元素迭代的順序。

所以我們可以直接這樣說：LinkedHashMap = HashMap + LinkedList。LinkedHashMap 就是在 HashMap 的基礎(chǔ)上多維護了一個雙向鏈表，用來保證元素迭代順序。

更形象化的圖形展示可以直接移到文章末尾。

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

2、字段屬性

①、Entry

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

LinkedHashMap 的每個元素都是一個 Entry，我們看到對于 Entry 繼承自 HashMap 的 Node 結(jié)構(gòu)，相對于 Node 結(jié)構(gòu)，LinkedHashMap 多了 before 和 after 結(jié)構(gòu)。

下面是Map類集合基本元素的實現(xiàn)演變。

LinkedHashMap 中 Entry 相對于 HashMap 多出的 before 和 after 便是用來維護 LinkedHashMap 插入 Entry 的先后順序的。

②、其它屬性

//用來指向雙向鏈表的頭節(jié)點
transient LinkedHashMap.Entry< K,V > head;
//用來指向雙向鏈表的尾節(jié)點
transient LinkedHashMap.Entry< K,V > tail;
//用來指定LinkedHashMap的迭代順序
//true 表示按照訪問順序，會把訪問過的元素放在鏈表后面，放置順序是訪問的順序
//false 表示按照插入順序遍歷
final boolean accessOrder;

注意：這里有五個屬性別搞混淆的，對于 Node next 屬性，是用來維護整個集合中 Entry 的順序。對于 Entry before，Entry after ，以及 Entry head，Entry tail，這四個屬性都是用來維護保證集合順序的鏈表，其中前兩個before和after表示某個節(jié)點的上一個節(jié)點和下一個節(jié)點，這是一個雙向鏈表。后兩個屬性 head 和 tail 分別表示這個鏈表的頭節(jié)點和尾節(jié)點。

3、構(gòu)造函數(shù)

①、無參構(gòu)造

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

調(diào)用無參的 HashMap 構(gòu)造函數(shù)，具有默認初始容量（16）和加載因子（0.75）。并且設(shè)定了 accessOrder = false，表示默認按照插入順序進行遍歷。

②、指定初始容量

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

③、指定初始容量和加載因子

public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

4、添加元素

LinkedHashMap 中是沒有 put 方法的，直接調(diào)用父類 HashMap 的 put 方法。關(guān)于 HashMap 的put 方法，可以參看我之前對于 HashMap 的介紹。

我將方法介紹復(fù)制到下面：

//hash(key)就是上面講的hash方法，對其進行了第一步和第二步處理
   public V put(K key, V value) {
       return putVal(hash(key), key, value, false, true);
   }
   /**
    *
    * @param hash 索引的位置
    * @param key  鍵
    * @param value  值
    * @param onlyIfAbsent true 表示不要更改現(xiàn)有值
    * @param evict false表示table處于創(chuàng)建模式
    * @return
    */
   final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
           boolean evict) {
        Node< K,V >[] tab; Node< K,V > p; int n, i;
        //如果table為null或者長度為0，則進行初始化
        //resize()方法本來是用于擴容，由于初始化沒有實際分配空間，這里用該方法進行空間分配，后面會詳細講解該方法
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //注意：這里用到了前面講解獲得key的hash碼的第三步，取模運算，下面的if-else分別是 tab[i] 為null和不為null
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);//tab[i] 為null，直接將新的key-value插入到計算的索引i位置
        else {//tab[i] 不為null，表示該位置已經(jīng)有值了
            Node< K,V > e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;//節(jié)點key已經(jīng)有值了，直接用新值覆蓋
            //該鏈?zhǔn)羌t黑樹
            else if (p instanceof TreeNode)
                e = ((TreeNode< K,V >)p).putTreeVal(this, tab, hash, key, value);
            //該鏈?zhǔn)擎湵?/span>
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //鏈表長度大于8，轉(zhuǎn)換成紅黑樹
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //key已經(jīng)存在直接覆蓋value
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;//用作修改和新增快速失敗
        if (++size > threshold)//超過最大容量，進行擴容
            resize();
        afterNodeInsertion(evict);
        return null;
   }

5、刪除元素

同理也是調(diào)用 HashMap 的remove 方法，這里我不作過多的講解，著重看LinkedHashMap 重寫的第 46 行方法。

public V remove(Object key) {
        Node< K,V > e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

    final Node< K,V > removeNode(int hash, Object key, Object value,
            boolean matchValue, boolean movable) {
        Node< K,V >[] tab; Node< K,V > p; int n, index;
        //(n - 1) & hash找到桶的位置
        if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node< K,V > node = null, e; K k; V v;
        //如果鍵的值與鏈表第一個節(jié)點相等，則將 node 指向該節(jié)點
        if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        node = p;
        //如果桶節(jié)點存在下一個節(jié)點
        else if ((e = p.next) != null) {
            //節(jié)點為紅黑樹
        if (p instanceof TreeNode)
         node = ((TreeNode< K,V >)p).getTreeNode(hash, key);//找到需要刪除的紅黑樹節(jié)點
        else {
         do {//遍歷鏈表，找到待刪除的節(jié)點
             if (e.hash == hash &&
                 ((k = e.key) == key ||
                  (key != null && key.equals(k)))) {
                 node = e;
                 break;
             }
             p = e;
         } while ((e = e.next) != null);
        }
        }
        //刪除節(jié)點，并進行調(diào)節(jié)紅黑樹平衡
        if (node != null && (!matchValue || (v = node.value) == value ||
                      (value != null && value.equals(v)))) {
        if (node instanceof TreeNode)
         ((TreeNode< K,V >)node).removeTreeNode(this, tab, movable);
        else if (node == p)
         tab[index] = node.next;
        else
         p.next = node.next;
        ++modCount;
        --size;
        afterNodeRemoval(node);
        return node;
        }
        }
        return null;
    }

6、查找元素

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

相比于 HashMap 的 get 方法，這里多出了第 5,6行代碼，當(dāng) accessOrder = true 時，即表示按照最近訪問的迭代順序，會將訪問過的元素放在鏈表后面。

對于 afterNodeAccess(e) 方法，在前面第 4 小節(jié) 添加元素已經(jīng)介紹過了，這就不在介紹。

7、遍歷元素

在介紹 HashMap 時，我們介紹了 4 中遍歷方式，同理，對于 LinkedHashMap 也有 4 種，這里我們介紹效率較高的兩種遍歷方式：

①、得到 Entry 集合，然后遍歷 Entry

LinkedHashMap< String,String > map = new LinkedHashMap<  >();
        map.put("A","1");
        map.put("B","2");
        map.put("C","3");
        map.get("B");
        Set< Map.Entry< String,String >> entrySet = map.entrySet();
        for(Map.Entry< String,String > entry : entrySet ){
            System.out.println(entry.getKey()+"---"+entry.getValue());
        }

②、迭代

Iterator< Map.Entry< String,String >> iterator = map.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry< String,String > entry = iterator.next();
            System.out.println(entry.getKey()+"----"+entry.getValue());
        }

8、小結(jié)

好了，這就是JDK中java.util.LinkedHashMap 類的介紹。