說(shuō)到集合類(lèi)，之前介紹的ArrayList類(lèi)，HashMap可能是大家日常用的最多的類(lèi)，但是對(duì)于另一個(gè)集合類(lèi) LinkedHashMap,可能大家用的不多，但是這種鏈?zhǔn)焦＜?，有些情況確實(shí)特別好用。

1、LinkedHashMap 定義

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

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

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

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 的每個(gè)元素都是一個(gè) Entry，我們看到對(duì)于 Entry 繼承自 HashMap 的 Node 結(jié)構(gòu)，相對(duì)于 Node 結(jié)構(gòu)，LinkedHashMap 多了 before 和 after 結(jié)構(gòu)。

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

LinkedHashMap 中 Entry 相對(duì)于 HashMap 多出的 before 和 after 便是用來(lái)維護(hù) LinkedHashMap 插入 Entry 的先后順序的。

②、其它屬性

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

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

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

①、無(wú)參構(gòu)造

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

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

②、指定初始容量

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

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

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

4、添加元素

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

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

//hash(key)就是上面講的hash方法，對(duì)其進(jìn)行了第一步和第二步處理
   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或者長(zhǎng)度為0，則進(jìn)行初始化
        //resize()方法本來(lái)是用于擴(kuò)容，由于初始化沒(méi)有實(shí)際分配空間，這里用該方法進(jìn)行空間分配，后面會(huì)詳細(xì)講解該方法
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //注意：這里用到了前面講解獲得key的hash碼的第三步，取模運(yùn)算，下面的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插入到計(jì)算的索引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é)點(diǎn)key已經(jīng)有值了，直接用新值覆蓋
            //該鏈?zhǔn)羌t黑樹(shù)
            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);
                        //鏈表長(zhǎng)度大于8，轉(zhuǎn)換成紅黑樹(shù)
                        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)//超過(guò)最大容量，進(jìn)行擴(kuò)容
            resize();
        afterNodeInsertion(evict);
        return null;
   }

5、刪除元素

同理也是調(diào)用 HashMap 的remove 方法，這里我不作過(guò)多的講解，著重看LinkedHashMap 重寫(xiě)的第 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;
        //如果鍵的值與鏈表第一個(gè)節(jié)點(diǎn)相等，則將 node 指向該節(jié)點(diǎn)
        if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        node = p;
        //如果桶節(jié)點(diǎn)存在下一個(gè)節(jié)點(diǎn)
        else if ((e = p.next) != null) {
            //節(jié)點(diǎn)為紅黑樹(shù)
        if (p instanceof TreeNode)
         node = ((TreeNode< K,V >)p).getTreeNode(hash, key);//找到需要?jiǎng)h除的紅黑樹(shù)節(jié)點(diǎn)
        else {
         do {//遍歷鏈表，找到待刪除的節(jié)點(diǎn)
             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ǎn)，并進(jìn)行調(diào)節(jié)紅黑樹(shù)平衡
        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 時(shí)，即表示按照最近訪問(wèn)的迭代順序，會(huì)將訪問(wèn)過(guò)的元素放在鏈表后面。

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

7、遍歷元素

在介紹 HashMap 時(shí)，我們介紹了 4 中遍歷方式，同理，對(duì)于 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 類(lèi)的介紹。