天天看點

【Java集合源碼剖析】LinkedHashmap源碼剖析    LinkedHashMap簡介    LinkedHashMap源碼剖析    幾點總結

轉載請注明出處:http://blog.csdn.net/ns_code/article/details/37867985

    前言:有網友建議分析下LinkedHashMap的源碼,于是花了一晚上時間研究了下,分享出此文(這個系列的最後一篇博文了),希望大家互相學習。LinkedHashMap的源碼了解起來也不難(當然,要建立在對HashMap源碼有較好了解的基礎上)。

    LinkedHashMap簡介

    LinkedHashMap是HashMap的子類,與HashMap有着同樣的存儲結構,但它加入了一個雙向連結清單的頭結點,将所有put到LinkedHashmap的節點一一串成了一個雙向循環連結清單,是以它保留了節點插入的順序,可以使節點的輸出順序與輸入順序相同。

    LinkedHashMap可以用來實作LRU算法(這會在下面的源碼中進行分析)。

    LinkedHashMap同樣是非線程安全的,隻在單線程環境下使用。

    LinkedHashMap源碼剖析

    LinkedHashMap源碼如下(加入了詳細的注釋):

package java.util;
import java.io.*;


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

    private static final long serialVersionUID = 3801124242820219131L;

	//雙向循環連結清單的頭結點,整個LinkedHa隻喲shMap中隻有一個header,
	//它将哈希表中所有的Entry貫穿起來,header中不儲存key-value對,隻儲存前後節點的引用
    private transient Entry<K,V> header;

	//雙向連結清單中元素排序規則的标志位。
	//accessOrder為false,表示按插入順序排序
	//accessOrder為true,表示按通路順序排序
    private final boolean accessOrder;

	//調用HashMap的構造方法來構造底層的數組
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;	//連結清單中的元素預設按照插入順序排序
    }

	//加載因子取預設的0.75f
    public LinkedHashMap(int initialCapacity) {
		super(initialCapacity);
        accessOrder = false;
    }

	//加載因子取預設的0.75f,容量取預設的16
    public LinkedHashMap() {
		super();
        accessOrder = false;
    }

	//含有子Map的構造方法,同樣調用HashMap的對應的構造方法
	public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super(m);
        accessOrder = false;
    }

	//該構造方法可以指定連結清單中的元素排序的規則
    public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

	//覆寫父類的init()方法(HashMap中的init方法為空),
	//該方法在父類的構造方法和Clone、readObject中在插入元素前被調用,
	//初始化一個空的雙向循環連結清單,頭結點中不儲存資料,頭結點的下一個節點才開始儲存資料。
    void init() {
        header = new Entry<K,V>(-1, null, null, null);
        header.before = header.after = header;
    }


	//覆寫HashMap中的transfer方法,它在父類的resize方法中被調用,
	//擴容後,将key-value對重新映射到新的newTable中
	//覆寫該方法的目的是為了提高複制的效率,
	//這裡充分利用雙向循環連結清單的特點進行疊代,不用對底層的數組進行for循環。
    void transfer(HashMap.Entry[] newTable) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e = header.after; e != header; e = e.after) {
            int index = indexFor(e.hash, newCapacity);
            e.next = newTable[index];
            newTable[index] = e;
        }
    }


	//覆寫HashMap中的containsValue方法,
	//覆寫該方法的目的同樣是為了提高查詢的效率,
	//利用雙向循環連結清單的特點進行查詢,少了對數組的外層for循環
    public boolean containsValue(Object value) {
        // Overridden to take advantage of faster iterator
        if (value==null) {
            for (Entry e = header.after; e != header; e = e.after)
                if (e.value==null)
                    return true;
        } else {
            for (Entry e = header.after; e != header; e = e.after)
                if (value.equals(e.value))
                    return true;
        }
        return false;
    }


	//覆寫HashMap中的get方法,通過getEntry方法擷取Entry對象。
	//注意這裡的recordAccess方法,
	//如果連結清單中元素的排序規則是按照插入的先後順序排序的話,該方法什麼也不做,
	//如果連結清單中元素的排序規則是按照通路的先後順序排序的話,則将e移到連結清單的末尾處。
    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;
    }

	//清空HashMap,并将雙向連結清單還原為隻有頭結點的空連結清單
    public void clear() {
        super.clear();
        header.before = header.after = header;
    }

	//Enty的資料結構,多了兩個指向前後節點的引用
    private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;

		//調用父類的構造方法
		Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }

		//雙向循環連結清單中,删除目前的Entry
        private void remove() {
            before.after = after;
            after.before = before;
        }

		//雙向循環立連結清單中,将目前的Entry插入到existingEntry的前面
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }


		//覆寫HashMap中的recordAccess方法(HashMap中該方法為空),
		//當調用父類的put方法,在發現插入的key已經存在時,會調用該方法,
		//調用LinkedHashmap覆寫的get方法時,也會調用到該方法,
		//該方法提供了LRU算法的實作,它将最近使用的Entry放到雙向循環連結清單的尾部,
		//accessOrder為true時,get方法會調用recordAccess方法
		//put方法在覆寫key-value對時也會調用recordAccess方法
		//它們導緻Entry最近使用,是以将其移到雙向連結清單的末尾
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
			//如果連結清單中元素按照通路順序排序,則将目前通路的Entry移到雙向循環連結清單的尾部,
			//如果是按照插入的先後順序排序,則不做任何事情。
            if (lm.accessOrder) {
                lm.modCount++;
				//移除目前通路的Entry
                remove();
				//将目前通路的Entry插入到連結清單的尾部
                addBefore(lm.header);
            }
        }

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

	//疊代器
    private abstract class LinkedHashIterator<T> implements Iterator<T> {
	Entry<K,V> nextEntry    = header.after;
	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;

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

	//從head的下一個節點開始疊代
	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;
	}
    }

	//key疊代器
    private class KeyIterator extends LinkedHashIterator<K> {
	public K next() { return nextEntry().getKey(); }
    }

	//value疊代器
    private class ValueIterator extends LinkedHashIterator<V> {
	public V next() { return nextEntry().value; }
    }

	//Entry疊代器
    private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
	public Map.Entry<K,V> next() { return nextEntry(); }
    }

    // These Overrides alter the behavior of superclass view iterator() methods
    Iterator<K> newKeyIterator()   { return new KeyIterator();   }
    Iterator<V> newValueIterator() { return new ValueIterator(); }
    Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }


	//覆寫HashMap中的addEntry方法,LinkedHashmap并沒有覆寫HashMap中的put方法,
	//而是覆寫了put方法所調用的addEntry方法和recordAccess方法,
	//put方法在插入的key已存在的情況下,會調用recordAccess方法,
	//在插入的key不存在的情況下,要調用addEntry插入新的Entry
    void addEntry(int hash, K key, V value, int bucketIndex) {
		//建立新的Entry,并插入到LinkedHashMap中
        createEntry(hash, key, value, bucketIndex);

        //雙向連結清單的第一個有效節點(header後的那個節點)為近期最少使用的節點
        Entry<K,V> eldest = header.after;
		//如果有必要,則删除掉該近期最少使用的節點,
		//這要看對removeEldestEntry的覆寫,由于預設為false,是以預設是不做任何處理的。
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        } else {
			//擴容到原來的2倍
            if (size >= threshold)
                resize(2 * table.length);
        }
    }

    void createEntry(int hash, K key, V value, int bucketIndex) {
		//建立新的Entry,并将其插入到數組對應槽的單連結清單的頭結點處,這點與HashMap中相同
        HashMap.Entry<K,V> old = table[bucketIndex];
		Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
        table[bucketIndex] = e;
		//每次插入Entry時,都将其移到雙向連結清單的尾部,
		//這便會按照Entry插入LinkedHashMap的先後順序來疊代元素,
		//同時,新put進來的Entry是最近通路的Entry,把其放在連結清單末尾 ,符合LRU算法的實作
        e.addBefore(header);
        size++;
    }

	//該方法是用來被覆寫的,一般如果用LinkedHashmap實作LRU算法,就要覆寫該方法,
	//比如可以将該方法覆寫為如果設定的記憶體已滿,則傳回true,這樣當再次向LinkedHashMap中put
	//Entry時,在調用的addEntry方法中便會将近期最少使用的節點删除掉(header後的那個節點)。
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }
}
           

    幾點總結

    關于LinkedHashMap的源碼,給出以下幾點比較重要的總結:

    1、從源碼中可以看出,LinkedHashMap中加入了一個head頭結點,将所有插入到該LinkedHashMap中的Entry按照插入的先後順序依次加入到以head為頭結點的雙向循環連結清單的尾部。

【Java集合源碼剖析】LinkedHashmap源碼剖析    LinkedHashMap簡介    LinkedHashMap源碼剖析    幾點總結
【Java集合源碼剖析】LinkedHashmap源碼剖析    LinkedHashMap簡介    LinkedHashMap源碼剖析    幾點總結

    實際上就是HashMap和LinkedList兩個集合類的存儲結構的結合。在LinkedHashMapMap中,所有put進來的Entry都儲存在如第一個圖所示的哈希表中,但它又額外定義了一個以head為頭結點的空的雙向循環連結清單,每次put進來Entry,除了将其儲存到對哈希表中對應的位置上外,還要将其插入到雙向循環連結清單的尾部。

    2、LinkedHashMap由于繼承自HashMap,是以它具有HashMap的所有特性,同樣允許key和value為null。

    3、注意源碼中的accessOrder标志位,當它false時,表示雙向連結清單中的元素按照Entry插入LinkedHashMap到中的先後順序排序,即每次put到LinkedHashMap中的Entry都放在雙向連結清單的尾部,這樣周遊雙向連結清單時,Entry的輸出順序便和插入的順序一緻,這也是預設的雙向連結清單的存儲順序;當它為true時,表示雙向連結清單中的元素按照通路的先後順序排列,可以看到,雖然Entry插傳入連結表的順序依然是按照其put到LinkedHashMap中的順序,但put和get方法均有調用recordAccess方法(put方法在key相同,覆寫原有的Entry的情況下調用recordAccess方法),該方法判斷accessOrder是否為true,如果是,則将目前通路的Entry(put進來的Entry或get出來的Entry)移到雙向連結清單的尾部(key不相同時,put新Entry時,會調用addEntry,它會調用creatEntry,該方法同樣将新插入的元素放入到雙向連結清單的尾部,既符合插入的先後順序,又符合通路的先後順序,因為這時該Entry也被通路了),否則,什麼也不做。

    4、注意構造方法,前四個構造方法都将accessOrder設為false,說明預設是按照插入順序排序的,而第五個構造方法可以自定義傳入的accessOrder的值,是以可以指定雙向循環連結清單中元素的排序規則,一般要用LinkedHashMap實作LRU算法,就要用該構造方法,将accessOrder置為true。

    5、LinkedHashMap并沒有覆寫HashMap中的put方法,而是覆寫了put方法中調用的addEntry方法和recordAccess方法,我們回過頭來再看下HashMap的put方法:

// 将“key-value”添加到HashMap中    
    public V put(K key, V value) {    
        // 若“key為null”,則将該鍵值對添加到table[0]中。    
        if (key == null)    
            return putForNullKey(value);    
        // 若“key不為null”,則計算該key的哈希值,然後将其添加到該哈希值對應的連結清單中。    
        int hash = hash(key.hashCode());    
        int i = indexFor(hash, table.length);    
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {    
            Object k;    
            // 若“該key”對應的鍵值對已經存在,則用新的value取代舊的value。然後退出!    
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {    
                V oldValue = e.value;    
                e.value = value;    
                e.recordAccess(this);    
                return oldValue;    
            }    
        }    
   
        // 若“該key”對應的鍵值對不存在,則将“key-value”添加到table中    
        modCount++;  
        //将key-value添加到table[i]處  
        addEntry(hash, key, value, i);    
        return null;    
    }    
   
           

    當要put進來的Entry的key在哈希表中已經在存在時,會調用recordAccess方法,當該key不存在時,則會調用addEntry方法将新的Entry插入到對應槽的單連結清單的頭部。

    我們先來看recordAccess方法:

//覆寫HashMap中的recordAccess方法(HashMap中該方法為空),
		//當調用父類的put方法,在發現插入的key已經存在時,會調用該方法,
		//調用LinkedHashmap覆寫的get方法時,也會調用到該方法,
		//該方法提供了LRU算法的實作,它将最近使用的Entry放到雙向循環連結清單的尾部,
		//accessOrder為true時,get方法會調用recordAccess方法
		//put方法在覆寫key-value對時也會調用recordAccess方法
		//它們導緻Entry最近使用,是以将其移到雙向連結清單的末尾
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
			//如果連結清單中元素按照通路順序排序,則将目前通路的Entry移到雙向循環連結清單的尾部,
			//如果是按照插入的先後順序排序,則不做任何事情。
            if (lm.accessOrder) {
                lm.modCount++;
				//移除目前通路的Entry
                remove();
				//将目前通路的Entry插入到連結清單的尾部
                addBefore(lm.header);
            }
        }
           

    該方法會判斷accessOrder是否為true,如果為true,它會将目前通路的Entry(在這裡指put進來的Entry)移動到雙向循環連結清單的尾部,進而實作雙向連結清單中的元素按照通路順序來排序(最近通路的Entry放到連結清單的最後,這樣多次下來,前面就是最近沒有被通路的元素,在實作、LRU算法時,當雙向連結清單中的節點數達到最大值時,将前面的元素删去即可,因為前面的元素是最近最少使用的),否則什麼也不做。

    再來看addEntry方法:

//覆寫HashMap中的addEntry方法,LinkedHashmap并沒有覆寫HashMap中的put方法,
	//而是覆寫了put方法所調用的addEntry方法和recordAccess方法,
	//put方法在插入的key已存在的情況下,會調用recordAccess方法,
	//在插入的key不存在的情況下,要調用addEntry插入新的Entry
    void addEntry(int hash, K key, V value, int bucketIndex) {
		//建立新的Entry,并插入到LinkedHashMap中
        createEntry(hash, key, value, bucketIndex);

        //雙向連結清單的第一個有效節點(header後的那個節點)為近期最少使用的節點
        Entry<K,V> eldest = header.after;
		//如果有必要,則删除掉該近期最少使用的節點,
		//這要看對removeEldestEntry的覆寫,由于預設為false,是以預設是不做任何處理的。
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        } else {
			//擴容到原來的2倍
            if (size >= threshold)
                resize(2 * table.length);
        }
    }

    void createEntry(int hash, K key, V value, int bucketIndex) {
		//建立新的Entry,并将其插入到數組對應槽的單連結清單的頭結點處,這點與HashMap中相同
        HashMap.Entry<K,V> old = table[bucketIndex];
		Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
        table[bucketIndex] = e;
		//每次插入Entry時,都将其移到雙向連結清單的尾部,
		//這便會按照Entry插入LinkedHashMap的先後順序來疊代元素,
		//同時,新put進來的Entry是最近通路的Entry,把其放在連結清單末尾 ,符合LRU算法的實作
        e.addBefore(header);
        size++;
    }
           

    同樣是将新的Entry插入到table中對應槽所對應單連結清單的頭結點中,但可以看出,在createEntry中,同樣把新put進來的Entry插入到了雙向連結清單的尾部,從插入順序的層面來說,新的Entry插入到雙向連結清單的尾部,可以實作按照插入的先後順序來疊代Entry,而從通路順序的層面來說,新put進來的Entry又是最近通路的Entry,也應該将其放在雙向連結清單的尾部。

    上面還有個removeEldestEntry方法,該方法如下:

//該方法是用來被覆寫的,一般如果用LinkedHashmap實作LRU算法,就要覆寫該方法,
	//比如可以将該方法覆寫為如果設定的記憶體已滿,則傳回true,這樣當再次向LinkedHashMap中put
	//Entry時,在調用的addEntry方法中便會将近期最少使用的節點删除掉(header後的那個節點)。
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }
}
           

    該方法預設傳回false,我們一般在用LinkedHashMap實作LRU算法時,要覆寫該方法,一般的實作是,當設定的記憶體(這裡指節點個數)達到最大值時,傳回true,這樣put新的Entry(該Entry的key在哈希表中沒有已經存在)時,就會調用removeEntryForKey方法,将最近最少使用的節點删除(head後面的那個節點,實際上是最近沒有使用)。

    6、LinkedHashMap覆寫了HashMap的get方法:

//覆寫HashMap中的get方法,通過getEntry方法擷取Entry對象。
	//注意這裡的recordAccess方法,
	//如果連結清單中元素的排序規則是按照插入的先後順序排序的話,該方法什麼也不做,
	//如果連結清單中元素的排序規則是按照通路的先後順序排序的話,則将e移到連結清單的末尾處。
    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;
    }
           

    先取得Entry,如果不為null,一樣調用recordAccess方法,上面已經說得很清楚,這裡不在多解釋了。

    7、最後說說LinkedHashMap是如何實作LRU的。首先,當accessOrder為true時,才會開啟按通路順序排序的模式,才能用來實作LRU算法。我們可以看到,無論是put方法還是get方法,都會導緻目标Entry成為最近通路的Entry,是以便把該Entry加入到了雙向連結清單的末尾(get方法通過調用recordAccess方法來實作,put方法在覆寫已有key的情況下,也是通過調用recordAccess方法來實作,在插入新的Entry時,則是通過createEntry中的addBefore方法來實作),這樣便把最近使用了的Entry放入到了雙向連結清單的後面,多次操作後,雙向連結清單前面的Entry便是最近沒有使用的,這樣當節點個數滿的時候,删除的最前面的Entry(head後面的那個Entry)便是最近最少使用的Entry。