LinkedHashMap簡(jiǎn)介

• 首先LinkedHashMap是HashMap的子類喜庞，和HashMap有著同樣的存儲(chǔ)結(jié)構(gòu)，但是它加入了一個(gè)雙向鏈表的頭結(jié)點(diǎn)吗货，將所有put的元素全部串成了一個(gè)雙向循環(huán)鏈表立轧，因此保留了插入的順序尘执，所以它是有序的鹃祖。
• 而且它也可以用來實(shí)現(xiàn)LRU算法溪椎，我們可以看LruCache源碼知道，內(nèi)部維護(hù)了 一個(gè)LinkedHahMap恬口，同樣它是非線程安全的

源碼解析（基于25的）

• 變量

  private transient LinkedHashMapEntry<K,V> header;
  雙向循環(huán)鏈表的頭結(jié)點(diǎn)校读，整個(gè)LinkedHashMap都只有一個(gè)header，它是將哈希表中所有的實(shí)體連接起來的祖能，header中不保存key-value歉秫，只保存前后結(jié)點(diǎn)的引用
  private final boolean accessOrder; 雙向鏈表中元素排序規(guī)則的標(biāo)志，為false的時(shí)候按照插入順序芯杀，為true按照訪問順序

• 構(gòu)造函數(shù)

public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
這是構(gòu)造函數(shù)端考，調(diào)用父類的構(gòu)造函數(shù)構(gòu)造數(shù)組雅潭，然后這個(gè)是按照插入順序來訪問的揭厚。
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
這個(gè)是支持自定義訪問順序的

• 方法

  @Override
    void init() {
    header = new LinkedHashMapEntry<>(-1, null, null, null);
    header.before = header.after = header;
  }
  這是init方法 是父類的也就是hashmap的 但是父類是空實(shí)現(xiàn)，子類實(shí)現(xiàn)并且創(chuàng)建一個(gè)header結(jié)點(diǎn)
  
    復(fù)寫HashMap中的transfer方法扶供，它在父類的resize方法中調(diào)用筛圆，擴(kuò)容后 將key和value對(duì)重新映射到新table中，復(fù)寫該方法的目的是為了提高復(fù)制的效率椿浓，這里迭代是利用了循環(huán)鏈表進(jìn)行迭代太援，并不對(duì)底層的數(shù)組的進(jìn)行for循環(huán)
  @Override
    void transfer(HashMapEntry[] newTable) {
    int newCapacity = newTable.length;
    for (LinkedHashMapEntry<K,V> e = header.after; e != header; e = e.after) {
        int index = indexFor(e.hash, newCapacity);
        e.next = newTable[index];
        newTable[index] = e;
    }
  }
  

• 內(nèi)部類

    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;  
  
    //調(diào)用父類的構(gòu)造方法  
    Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {  
        super(hash, key, value, next);  
    }  
  
    //雙向循環(huán)鏈表中，刪除當(dāng)前的Entry  注意這里得到的當(dāng)前的對(duì)象  
    private void remove() {  
        before.after = after;  //  this.before.after=this.after;
        after.before = before;  //this.after.brfore=this.before; 這么寫肯定看懂 也就是說將當(dāng)前節(jié)點(diǎn)刪除
    }  
  
    //雙向循環(huán)立鏈表中扳碍，將當(dāng)前的Entry插入到existingEntry的前面  
    private void addBefore(Entry<K,V> existingEntry) {  
        after  = existingEntry;  
        before = existingEntry.before;  
        before.after = this;  
        after.before = this;  
    }  
  
  
    //覆寫HashMap中的recordAccess方法（HashMap中該方法為空）提岔，  
    //當(dāng)調(diào)用父類的put方法，在發(fā)現(xiàn)插入的key已經(jīng)存在時(shí)笋敞，會(huì)調(diào)用該方法碱蒙，  
    //調(diào)用LinkedHashmap覆寫的get方法時(shí)，也會(huì)調(diào)用到該方法夯巷，  
    //該方法提供了LRU算法的實(shí)現(xiàn)赛惩，它將最近使用的Entry放到雙向循環(huán)鏈表的尾部，  
    //accessOrder為true時(shí)趁餐，get方法會(huì)調(diào)用recordAccess方法  
    //put方法在覆蓋key-value對(duì)時(shí)也會(huì)調(diào)用recordAccess方法  
    //它們導(dǎo)致Entry最近使用喷兼，因此將其移到雙向鏈表的末尾  
    void recordAccess(HashMap<K,V> m) {  
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;  
        //如果鏈表中元素按照訪問順序排序，則將當(dāng)前訪問的Entry移到雙向循環(huán)鏈表的尾部后雷，  
        //如果是按照插入的先后順序排序季惯，則不做任何事情吠各。  
        if (lm.accessOrder) {  
            lm.modCount++;  
            //移除當(dāng)前訪問的Entry  
            remove();  
            //將當(dāng)前訪問的Entry插入到鏈表的尾部  
            addBefore(lm.header);  
        }  
    }  
  
    void recordRemoval(HashMap<K,V> m) {  
        remove();  
    }  
  }  
  

  這里在貼一下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;  
  

  }
  //以上就是linkedmap源碼解析 大多數(shù)都是調(diào)用父類的方法，

總結(jié)

image.png

• 從源碼中可以看出LinkedHashmap就是加入了一個(gè)head節(jié)點(diǎn)勉抓，將所有插入到該map中的entry按照插入的先后順序依次插入到以head為頭結(jié)點(diǎn)的雙向循環(huán)鏈表的尾部

• LinkedHashMap由于繼承自HashMap走孽，因此它具有HashMap的所有特性，同樣允許key和value為null琳状。

• 注意源碼中的accessOrder標(biāo)志磕瓷，當(dāng)它false時(shí)，表示雙向鏈表中的元素按照Entry插入LinkedHashMap到中的先后順序排序念逞，即每次put到LinkedHashMap中的Entry都放在雙向鏈表的尾部困食，這樣遍歷雙向鏈表時(shí)，Entry的輸出順序便和插入的順序一致翎承，這也是默認(rèn)的雙向鏈表的存儲(chǔ)順序硕盹；當(dāng)它為true時(shí)，表示雙向鏈表中的元素按照訪問的先后順序排列叨咖，可以看到瘩例，雖然Entry插入鏈表的順序依然是按照其put到LinkedHashMap中的順序，但put和get方法均有調(diào)用recordAccess方法（put方法在key相同甸各，覆蓋原有的Entry的情況下調(diào)用recordAccess方法）垛贤，該方法判斷accessOrder是否為true，如果是趣倾，則將當(dāng)前訪問的Entry（put進(jìn)來的Entry或get出來的Entry）移到雙向鏈表的尾部（key不相同時(shí)聘惦，put新Entry時(shí)，會(huì)調(diào)用addEntry儒恋，它會(huì)調(diào)用creatEntry善绎，該方法同樣將新插入的元素放入到雙向鏈表的尾部，既符合插入的先后順序诫尽，又符合訪問的先后順序禀酱，因?yàn)檫@時(shí)該Entry也被訪問了），否則牧嫉，什么也不做剂跟。

• 注意構(gòu)造方法，第一個(gè)構(gòu)造方法是按照插入順序來訪問的驹止，第二個(gè)構(gòu)造方法是你可以自定義的浩聋，因此可以指定雙向循環(huán)鏈表中元素的排序規(guī)則，一般要用LinkedHashMap實(shí)現(xiàn)LRU算法臊恋，就要用該構(gòu)造方法衣洁，將accessOrder置為true。
  5抖仅、LinkedHashMap并沒有覆寫HashMap中的put方法坊夫，而是覆寫了put方法中調(diào)用的addEntry方法和recordAccess方法