LinkedHashMap是繼承自HashMap,并實(shí)現(xiàn)Map接口.所以他擁有HashMap的結(jié)構(gòu),同時(shí)他又有LinkedList的結(jié)構(gòu)(雙向鏈表的結(jié)構(gòu)-環(huán)形的).由于LinkedHashMap中維護(hù)了一個(gè)雙向鏈表結(jié)構(gòu),所以在LinkedHashMap中的某些遍歷操作是直接針對(duì)的雙向鏈表的(例如:contains操作,Iterator操作).

下面是LinkedHashMap中entry結(jié)構(gòu):

// 繼承自HashMap中的entry,并增加了兩個(gè)額外的屬性
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);
    }
}

類定義

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

成員變量(擁有HashMap中所有的非私有成員變量)

方法

初始化方法init()
在構(gòu)造函數(shù)中被調(diào)用,會(huì)初始化鏈表的頭結(jié)點(diǎn)header

@Override
void init() {
    header = new Entry<>(-1, null, null, null);
    header.before = header.after = header;
}

添加元素put()
繼承自HashMap方法,且沒有重寫,所以它的數(shù)組結(jié)構(gòu)跟HashMap是一樣的;只是它重寫了addEntry()和createEntry()方法(這兩個(gè)方法會(huì)在put的時(shí)候被調(diào)用到),這兩個(gè)方法會(huì)增多一個(gè)雙向鏈表的結(jié)構(gòu).下面講解:

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 調(diào)用父類HashMap中的addEntry()方法(會(huì)調(diào)用createEntry()方法)
    super.addEntry(hash, key, value, bucketIndex); 

    // Remove eldest entry if instructed
    Entry<K,V> eldest = header.after;
    // 移除老的Entry(不會(huì)執(zhí)行,除非子類重寫removeEldestEntry方法)
    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    }
}

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;
    
    // 雙向鏈表的操作,在header節(jié)點(diǎn)前面鏈接e節(jié)點(diǎn)
    // 所以每次添加的新的entry,在雙向鏈表中的位置始終是在header前面
    e.addBefore(header);
    size++;
}

/**
* Entry類中的addBefore()方法
* 在existingEntry節(jié)點(diǎn)前增加當(dāng)前調(diào)用方法的實(shí)例節(jié)點(diǎn)
**/
private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

獲取元素get()
跟HashMap是一樣的, 直接調(diào)用的父類HashMap中的getEntry()方法.

public V get(Object key) {
    Entry<K,V> e = (Entry<K,V>)getEntry(key);
    if (e == null)
        return null;
    
    // 增加隨機(jī)訪問性
    e.recordAccess(this);
    return e.value;
}

/**
* Entry類中的方法
**/
void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    // 如果允許隨機(jī)訪問則移除此節(jié)點(diǎn),再把該節(jié)點(diǎn)重新放在雙向鏈表的header前面
    if (lm.accessOrder) {
        lm.modCount++;
        remove();
        addBefore(lm.header);
    }
}