LinkedHashMap源碼詳解

序言

本來是不打算先講map的，但是隨著對set集合的認識，發現如果不先搞懂各種map，是無法理解set的。因為set集合很多的底層就是用map來存儲的。比如HashSet就是用HashMap，LinkedHashSet就是用LinkedHashMap。所以打算把map講完把。

一、LinkedHashMap

先來說說它的特點，然後在一一通過分析源碼來驗證其實現原理

1、能夠保證插入元素的順序。深入一點講，有兩種迭代元素的方式，一種是按照插入元素時的順序迭代，比如，插入A,B,C，那麼迭代也是A,B,C，另一種是按照訪問順序，比如，在迭代前，訪問了B，那麼迭代的順序就是A,C,B，比如在迭代前，訪問了B，接著又訪問了A，那麼迭代順序為C,B,A，比如，在迭代前訪問了B，接著又訪問了B，然後在訪問了A，迭代順序還是C,B,A。要說明的意思就是不是近期訪問的次數最多，就放最後面迭代，而是看迭代前被訪問的時間長短決定。

3、內部存儲的元素的模型。entry是下面這樣的，相比HashMap，多了兩個屬性，一個before，一個after。next和after有時候會指向同一個entry，有時候next指向null，而after指向entry。這個具體後面分析。

　　　　　　　　　　　　　　　　　　　　

4、linkedHashMap和HashMap在存儲操作上是一樣的，但是LinkedHashMap多的東西是會記住在此之前插入的元素，這些元素不一定是在一個桶中，畫個圖。

　　　　　　　　　　　　　　　　　　　　　　

也就是說，對於linkedHashMap的基本操作還是和HashMap一樣，在其上面加了兩個屬性，也就是為了記錄前一個插入的元素和記錄後一個插入的元素。也就是只要和hashmap一樣進行操作之後把這兩個屬性的值設置好，就OK了。注意一點，會有一個header的實體，目的是為了記錄第一個插入的元素是誰，在遍歷的時候能夠找到第一個元素。

實際上存儲的樣子就像上面這個圖一樣，這裡要分清楚哦。實際上的存儲方式是和hashMap一樣，但是同時增加了一個新的東西就是 雙向循環鏈表。就是因為有了這個雙向循環鏈表，LinkedHashMap才和HashMap不一樣。

5、其他一些比如如何實現的循環雙向鏈表，插入順序和訪問順序如何實現的就看下面的詳細講解了。

二、源碼分析

2.1、內部存儲元素的存儲結構源碼和理解LinkedHashMap雙向循環鏈表，

　　　　　　　　　　　　　　　　　　　　

　　　　　　　　

//LinkedHashMap的entry繼承自HashMap的Entry。
    private static class Entry<K,V> extends HashMap.Entry<K,V> {
       // These fields comprise the doubly linked list used for iteration.
   //通過上面這句源碼的解釋，我們可以知道這兩個字段，是用來給迭代時使用的，相當於一個雙向鏈表，實際上用的時候，操作LinkedHashMap的entry和操作HashMap的Entry是一樣的，只操作相同的四個屬性，這兩個字段是由linkedHashMap中一些方法所操作。所以LinkedHashMap的很多方法度是直接繼承自HashMap。
//before：指向前一個entry元素。after：指向後一個entry元素
        Entry<K,V> before, after;
   //使用的是HashMap的Entry構造
        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
           super(hash, key, value, next);
        }

//下面是維護這個雙向循環鏈表的一些操作。在HashMap中沒有這些操作，因為HashMap不需要維護，
        /**
        * Removes this entry from the linked list.
        */

//我們知道在雙向循環鏈表時移除一個元素需要進行哪些操作把，比如有A,B,C，將B移除，那麼A.next要指向c，c.before要指向A。下面就是進行這樣的操作，但是會有點繞，他省略了一些東西。

//有的人會問，要是刪除的是最後一個元素呢，那這個方法還適用嗎？有這個疑問的人應該注意一下這個是雙向循環鏈表，雙向，刪除哪個度適用。
        private void remove() {

　　　　　　//this.before.after = this.after;

　　　　　　//this.after.before = this.before; 這樣看可能會更好理解，this指的就是要刪除的哪個元素。


            before.after= after;
            after.before= before;
        }

       /**
        * Inserts this entry before the specified existing entry in the list.
        */

//插入一個元素之後做的一些操作，就是將第一個元素，和最後一個元素的一些指向改變。傳進來的existingEntry就是header。


        private void addBefore(Entry<K,V> existingEntry) {
            after = existingEntry;
            before= existingEntry.before;
            before.after= this;
            after.before= this;
        }

       /**
        * This method is invoked by the superclass whenever the value
        * of a pre-existing entry is read by Map.get or modified by Map.set.
        * If the enclosing Map is access-ordered, it moves the entry
        * to the end of the list; otherwise, it does nothing.
        */

//這個方法就是我們一開始說的，accessOrder為true時，就是使用的訪問順序，訪問次數最少到訪問次數最多，此時要做特殊處理。處理機制就是訪問了一次，就將自己往後移一位，這裡就是先將自己刪除了，然後在把自己添加，

//這樣，近期訪問的少的就在鏈表的開始，最近訪問的元素就會在鏈表的末尾。如果為false。那麼默認就是插入順序，直接通過鏈表的特點就能依次找到插入元素，不用做特殊處理。


        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
           if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

       void recordRemoval(HashMap<K,V> m) {
            remove();
        }
    }

通過查看LinkedHashMap的entry，就驗證了我們上面說的特性3.

2.2、構造方法

有五個構造方法。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

1 //使用父類中的構造，初始化容量和加載因子，該初始化容量是指數組大小。
2    public LinkedHashMap(int initialCapacity, float loadFactor) {
3        super(initialCapacity, loadFactor);
4        accessOrder = false;
5     }
6 //一個參數的構造
7    public LinkedHashMap(int initialCapacity) {
8        super(initialCapacity);
9        accessOrder = false;
10     }
11 //無參構造
12    public LinkedHashMap() {
13        super();
14        accessOrder = false;
15     }
16 //這個不用多說，用來接受map類型的值轉換為LinkedHashMap 17    public LinkedHashMap(Map<? extends K, ? extends V> m) {
18        super(m);
19        accessOrder = false;
20     }
21 //真正有點特殊的就是這個，多了一個參數accessOrder。存儲順序，LinkedHashMap關鍵的參數之一就在這個，
　　//true：指定迭代的順序是按照訪問順序(近期訪問最少到近期訪問最多的元素)來迭代的。 false：指定迭代的順序是按照插入順序迭代，也就是通過插入元素的順序來迭代所有元素
//如果你想指定訪問順序，那麼就只能使用該構造方法，其他三個構造方法默認使用插入順序。

22    public LinkedHashMap(int initialCapacity,
23                          float loadFactor,
24                          boolean accessOrder) {
25        super(initialCapacity, loadFactor);
26        this.accessOrder = accessOrder;
27    }

2.3、驗證header的存在

//linkedHashMap中的init()方法，就使用header，hash值為-1，其他度為null，也就是說這個header不放在數組中，就是用來指示開始元素和標志結束元素的。
    void init() {
        header = new Entry<>(-1, null, null, null);
//一開始是自己指向自己，沒有任何元素。HashMap中也有init()方法是個空的，所以這裡的init()方法就是為LinkedHashMap而寫的。
        header.before = header.after = header;
    }
//在HashMap的構造方法中就會使用到init()，
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }

2.4、LinkedHashMap是如何和其父類HashMap共享一些方法的。比如，put操作等。

1、LinkedHashMap構造方法完成後，調用put往其中添加元素，查看父類中的put源碼

put

 1 //這個方法應該挺熟悉的，如果看了HashMap的解析的話
 2    public V put(K key, V value) {
 3     //剛開始其存儲空間啥也沒有，在這裡初始化
 4         if (table == EMPTY_TABLE) {
 5             inflateTable(threshold);
 6         }
 7 //key為null的情況
 8         if (key == null)
 9             return putForNullKey(value);
10 //通過key算hash，進而算出在數組中的位置，也就是在第幾個桶中
11         int hash = hash(key);
12         int i = indexFor(hash, table.length);
13 //查看桶中是否有相同的key值，如果有就直接用新植替換舊值，而不用在創建新的entry了
14         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
15             Object k;
16             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
17                 V oldValue = e.value;
18                 e.value = value;
19                 e.recordAccess(this);
20                 return oldValue;
21             }
22         }
23 
24         modCount++;
25 //上面度是熟悉的東西，最重要的地方來了，就是這個方法，LinkedHashMap執行到這裡，addEntry()方法不會執行HashMap中的方法，而是執行自己類中的addEntry方法，這裡就要
　　提一下LinkedHashMap重寫HashMap中兩個個關鍵的方法了。看下面的分析。
26         addEntry(hash, key, value, i);
27         return null;
28     }

重寫了void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)

//重寫的addEntry。其中還是會調用父類中的addEntry方法，但是此外會增加額外的功能，
   void addEntry(int hash, K key, V value, int bucketIndex) {
        super.addEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }

//HashMap的addEntry，就是在將元素加入桶中前判斷桶中的大小或者數組的大小是否合適，總之就是做一些數組容量上的判斷和hash值的問題。
    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
//這裡就是真正創建entry的時候了。也被LinkedHashMap重寫了。
        createEntry(hash, key, value, bucketIndex);
    }

//重寫的createEntry，這裡要注意的是，新元素放桶中，是放第一位，而不是往後追加，所以下面方法中前面三行應該知道了
    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
//這個方法的作用就是將e放在雙向循環鏈表的末尾，需要將一些指向進行修改的操作。。
        e.addBefore(header);
        size++;
    }

到這裡，應該就對LinkedHashMap的存儲過程有一定的了解了。並且也應該知道是如何存儲的了。存儲時有何特殊之處。

2.5、來看看迭代器的使用。對雙向循環鏈表的遍歷操作。但是這個迭代器是abstract的，不能直接被對象所用，但是能夠間接使用，就是通過keySet().interator()，就是使用的這個迭代器

//這個也非常簡單，無非就是對雙向循環鏈表進行遍歷。
    private abstract class LinkedHashIterator<T> implements Iterator<T> {
    //先拿到header的after指向的元素，也就是第一個元素。
        Entry<K,V> nextEntry    = header.after;
    //記錄前一個元素是誰，因為剛到第一個元素，第一個元素之前的元素理論上就是null。實際上是指向最後一個元素的。知道就行。
        Entry<K,V> lastReturned = null;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        int expectedModCount = modCount;

    //判斷有沒有到循環鏈表的末尾，就看元素的下一個是不是header。
        public boolean hasNext() {
            return nextEntry != header;
        }
    //移除操作，也就一些指向問題
        public void remove() {
            if (lastReturned == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
    
            LinkedHashMap.this.remove(lastReturned.key);
            lastReturned = null;
            expectedModCount = modCount;
        }
//下一個元素。一些指向問題，度是雙向循環鏈表中的操作。
        Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();

            Entry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
        }
    }    

keySet()是如何間接使用了LinkedHashIterator的

　　　　　　　　　　　　　　hashMap中的keySet()

　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　找到newKeyIterator()

　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　是LinkedHashMap對象調用的，而LinkedHashMap中重寫了KeyIterator方法，所以就這樣間接的使用了LinkedHashIterator迭代器

　　　　　　　　　　　　　　　　　　

2.6、看看迭代時使用訪問順序如何實現的，其實關鍵也就是在哪個recordAccess方法，來看看流程

linkedHashMap中有get方法，不會使用父類中的get方法

    public V get(Object key) {
        Entry<K,V> e = (Entry<K,V>)getEntry(key);
        if (e == null)
            return null;
//關鍵的就是這個方法
        e.recordAccess(this);
        return e.value;
    }
//這個方法在上面已經分析過了，如果accessOrder為true，那麼就會用訪問順序。if條件下的語句會執行，作用就是將最近訪問的元素放鏈表的末尾。
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

2.7、使用默認的插入順序就不用多分析了，也就是上面這個if下的代碼不生效，就會使用插入順序。

三、驗證LinkedHashMap的功能

注意、map是不能夠只能拿到迭代器的，只能夠拿到keySet().iterator(); 也就是說迭代器是不能夠迭代map的，到時能夠間接的使用迭代器。就比如先拿到key的迭代器，然後在通過key找到對應的value值，或者直接用values()方法，拿到所有的map的value。values()方法的底層也是使用的迭代器。

1、使用訪問順序，結果確實是如我們所預期那樣

　　　　　　　　　　　　　　

注意：如果使用for循環來遍歷，肯定就不是這個結果了，原因是for循環是按照key值的順序來查找的呀，從1到6，這裡如果需要驗證訪問順序，就必須使用迭代器，而map使用迭代器有兩種方式，一種就是我上面所用的使values()，另一種是使用keySet().Iterator()；自己可以嘗試一下。

四、總結

1、知道LinkedHashMap的實現原理。

1.1、實現原理，跟HashMap一模一樣。HashMap有的特性，LinkedHashMap基本上都有。

1.2、具體的存儲實現，就看一開始的那兩張圖。雖然第二張畫得比較亂，但是仔細去看，就能夠弄懂其中的道理。

2、知道LinkedHashMap迭代的訪問順序和插入順序

　　　　　　　　　　　2.1、關鍵屬性accessOrder

　　　　　　　　　　　2.2、關鍵方法recordAccess

3、知道LinekdHashMap和HashMap的區別。

　　　　　　　　　　　　3.1、LinkedHashMap是HashMap的子類，實現的原理跟HashMap差不多，唯一的區別就是LinkedHashMap多了一個雙向循環鏈表。

　　　　　　　　　　　　3.2、因為有雙向循環列表，所以LinkedHashMap能夠記錄插入元素的順序，而HashMap不能，

4、map使用迭代的兩種方式，知道其內部是如何使用迭代器的。

　　　　　　　　　　keySet().iterator()

　　　　　　　　　　values()