如何理解Java容器中Map的源碼分析

本篇文章為大家展示了如何理解Java容器中Map的源碼分析，內(nèi)容簡明扼要并且容易理解，絕對(duì)能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。

如果沒有特別說明，以下源碼分析基于 JDK 1.8。

一、HashMap

為了便于理解，以下源碼分析以 JDK 1.7 為主。

1. 存儲(chǔ)結(jié)構(gòu)

內(nèi)部包含了一個(gè) Entry 類型的數(shù)組 table。

transient Entry[] table;

Entry 存儲(chǔ)著鍵值對(duì)。它包含了四個(gè)字段，從 next 字段我們可以看出 Entry 是一個(gè)鏈表。 即數(shù)組中的每個(gè)位置被當(dāng)成一個(gè)桶，一個(gè)桶存放一個(gè)鏈表。HashMap 使用拉鏈法來解決沖突， 同一個(gè)鏈表中存放哈希值相同的 Entry。

static class Entry<K,V> implements Map.Entry<K,V> {
    //包含了四個(gè)字段
    final K key;
    V value;
    //next指向下一個(gè)節(jié)點(diǎn)，說明是鏈表結(jié)構(gòu)
    Entry<K,V> next;
    int hash;
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
    public final K getKey() {
        return key;
    }
    public final V getValue() {
        return value;
    }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    public final Boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
                    return false;
        Map.Entry e = (Map.Entry)o;
        Object k1 = getKey();
        Object k2 = e.getKey();
        // k1==k2 比較的是 hashcode 值，
        // k1.equals(k2)比較的是k1和k2的內(nèi)容 equals 未重寫，則等價(jià)于 k1 == k2
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {
            Object v1 = getValue();
            Object v2 = e.getValue();
            if (v1 == v2 || (v1 != null && v1.equals(v2)))
                            return true;
        }
        return false;
    }
    public final int hashCode() {
        return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
    }
    public final String toString() {
        return getKey() + "=" + getValue();
    }
}

2. 拉鏈法的工作原理

HashMap<String, String> map = new HashMap<>();
map.put("K1", "V1");
map.put("K2", "V2");
map.put("K3", "V3");

• 新建一個(gè) HashMap，默認(rèn)大小為 16；

• 插入

  鍵值對(duì)，先計(jì)算 K1 的 hashCode 為 115，使用除留余數(shù)法得到所在的桶下標(biāo) 115%16=3。

• 插入

  鍵值對(duì)，先計(jì)算 K2 的 hashCode 為 118，使用除留余數(shù)法得到所在的桶下標(biāo) 118%16=6。

• 插入

  鍵值對(duì)，先計(jì)算 K3 的 hashCode 為 118，使用除留余數(shù)法得到所在的桶下標(biāo) 118%16=6，插在前面。

應(yīng)該注意到鏈表的插入是以頭插法方式進(jìn)行的，例如上面的不是插在后面，而是插入在鏈表頭部。

查找需要分成兩步進(jìn)行：

• 計(jì)算鍵值對(duì)所在的桶；

• 在鏈表上順序查找，時(shí)間復(fù)雜度顯然和鏈表的長度成正比。

3. put 操作

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 鍵為 null 單獨(dú)處理
    if (key == null)
            return putForNullKey(value);
    int hash = hash(key);
    // 確定桶下標(biāo)
    int i = indexFor(hash, table.length);
    // 先找出是否已經(jīng)存在鍵為 key 的鍵值對(duì)，如果存在的話就更新這個(gè)鍵值對(duì)的值為 value
    // 時(shí)間復(fù)雜度顯然和鏈表的長度成正比。
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    // 插入新鍵值對(duì)
    addEntry(hash, key, value, i);
    return null;
}

HashMap 允許插入鍵為 null 的鍵值對(duì)。但是因?yàn)闊o法調(diào)用 null 的 hashCode() 方法，也就無法確定該鍵值對(duì)的桶下標(biāo)，只能通過強(qiáng)制指定一個(gè)桶下標(biāo)來存放。HashMap 使用第 0 個(gè)桶存放鍵為 null 的鍵值對(duì)。

private V putForNullKey(V value) {
    //HashMap 使用第 0 個(gè)桶 table[0] 存放鍵為 null 的鍵值對(duì)。
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            // 更新值
            e.recordAccess(this);
            return oldValue;
            // 返回舊值
        }
    }
    modCount++;
    //void addEntry(int hash, K key, V value, int bucketIndex)
    addEntry(0, null, value, 0);
    return null;
}

使用鏈表的頭插法，也就是新的鍵值對(duì)插在鏈表的頭部，而不是鏈表的尾部。

//TODO:使用鏈表的頭插法，也就是新的鍵值對(duì)插在鏈表的頭部，而不是鏈表的尾部。
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);
    }
    createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    // 頭插法，鏈表頭部指向新的鍵值對(duì)
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
}

4. 確定桶下標(biāo)

很多操作都需要先確定一個(gè)鍵值對(duì)所在的桶下標(biāo)。

int hash = hash(key);
int i = indexFor(hash, table.length);

①. 計(jì)算 hash 值

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash42((String) k);
    }
    h ^= k.hashCode();
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCode(value);
}

②. 取模

令 x = 1<<4，即 x 為 2 的 4 次方，它具有以下性質(zhì)：

x   : 00010000
x-1 : 00001111

令一個(gè)數(shù) y 與 x-1 做與運(yùn)算，可以去除 y 位級(jí)表示的第 4 位以上數(shù)：

y       : 10110010
x-1     : 00001111
y&(x-1) : 00000010

這個(gè)性質(zhì)和 y 對(duì) x 取模效果是一樣的：

y   : 10110010
x   : 00010000
y%x : 00000010

我們知道，位運(yùn)算的代價(jià)比求模運(yùn)算小的多，因此在進(jìn)行這種計(jì)算時(shí)用位運(yùn)算的話能帶來更高的性能。

確定桶下標(biāo)的最后一步是將 key 的 hash 值對(duì)桶個(gè)數(shù)取模： hash%capacity，如果能保證 capacity 為 2 的 n 次方，那么就可以將這個(gè)操作轉(zhuǎn)換為位運(yùn)算。

static int indexFor(int h, int length) {
    return h & (length-1);
}

就等價(jià)于

static int indexFor(int h, int length) {
    return h % length;
}

但是效率會(huì)更高。

5. 擴(kuò)容-基本原理

設(shè) HashMap 的 table 長度為 M，需要存儲(chǔ)的鍵值對(duì)數(shù)量為 N，如果哈希函數(shù)滿足均勻性的要求，那么每條鏈表的長度大約為 N/M，因此平均查找次數(shù)的復(fù)雜度為 O(N/M)。

為了讓查找的成本降低，應(yīng)該盡可能使得 N/M 盡可能小，因此需要保證 M 盡可能大，也就是說 table 要盡可能大。 HashMap 采用動(dòng)態(tài)擴(kuò)容來根據(jù)當(dāng)前的 N 值來調(diào)整 M 值，使得空間效率和時(shí)間效率都能得到保證。

和擴(kuò)容相關(guān)的參數(shù)主要有：capacity、size、threshold 和 load_factor。

static final int DEFAULT_INITIAL_CAPACITY = 16;
//保證 capacity 為 2 的 n 次方，那么就可以將indexFor方法中操作轉(zhuǎn)換為位運(yùn)算
static final int MAXIMUM_CAPACITY = 1 << 30;
//保證 capacity 為 2 的 n 次方，那么就可以將 indexFor 方法中操作轉(zhuǎn)換為位運(yùn)算
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Entry[] table;
transient int size;
int threshold;
final float loadFactor;
transient int modCount;

從下面的添加元素代碼中可以看出，當(dāng)需要擴(kuò)容時(shí)，令 capacity 為原來的兩倍。

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    if (size++ >= threshold)
            resize(2 * table.length);
    //令 capacity 為原來的兩倍
}

擴(kuò)容使用 resize() 實(shí)現(xiàn)，需要注意的是，擴(kuò)容操作同樣需要把 oldTable 的所有鍵值對(duì)重新插入 newTable 中，因此這一步是很費(fèi)時(shí)的。

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
            while (e != null);
        }
    }
}

6. 擴(kuò)容-重新計(jì)算桶下標(biāo)

在進(jìn)行擴(kuò)容時(shí)，需要把鍵值對(duì)重新放到對(duì)應(yīng)的桶上。HashMap 使用了一個(gè)特殊的機(jī)制，可以提升重新計(jì)算桶下標(biāo)的效率。

假設(shè)原數(shù)組長度 capacity 為 16，擴(kuò)容之后 new capacity 為 32：

capacity     : 00010000
new capacity : 00100000

對(duì)于一個(gè) Key，

• 它的哈希值如果在第 5 位上為 0，那么取模得到的結(jié)果和之前一樣；

• 如果為 1，那么得到的結(jié)果為原來的結(jié)果 +16。

7. 計(jì)算數(shù)組容量

HashMap 構(gòu)造函數(shù)允許用戶傳入的容量不是 2 的 n 次方，因?yàn)樗梢宰詣?dòng)地將傳入的容量轉(zhuǎn)換為 2 的 n 次方。

先考慮如何求一個(gè)數(shù)的掩碼，對(duì)于 10010000，它的掩碼為 11111111，可以使用以下方法得到：

mask |= mask >> 1    11011000
mask |= mask >> 2    11111110
mask |= mask >> 4    11111111

mask+1 是大于原始數(shù)字的最小的 2 的 n 次方。

num     10010000
mask+1  100000000

以下是 HashMap 中計(jì)算數(shù)組容量的代碼：

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    //得到n的掩碼
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

8. 鏈表轉(zhuǎn)紅黑樹

從 JDK 1.8 開始，一個(gè)桶存儲(chǔ)的鏈表長度大于 8 時(shí)會(huì)將鏈表轉(zhuǎn)換為紅黑樹。

9. 與 HashTable 的比較

• HashMap 是非線程安全的，HashTable 使用 synchronized 來進(jìn)行同步，是線程安全的。

• HashMap 要比 HashTable 效率高一點(diǎn)。Hashtable 基本被淘汰，不要在代碼中使用它。

• HashMap 可以插入鍵為 null 的 Entry；HashTable 中插入的鍵只要有一個(gè)為 null，直接拋出 NullPointerException。

• HashMap 的迭代器是 fail-fast 迭代器。

• HashMap 不能保證隨著時(shí)間的推移 Map 中的元素次序是不變的。

• HashMap 在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時(shí)間；Hashtable 沒有這樣的機(jī)制。

• HashMap 默認(rèn)的初始化大小為16。之后每次擴(kuò)充，容量變?yōu)樵瓉淼?倍；Hashtable 容量默認(rèn)的初始大小為11，之后每次擴(kuò)充，容量變?yōu)樵瓉淼?n+1。 在初始化時(shí)如果給定了容量初始值，HashMap 會(huì)將其擴(kuò)充為2的冪次方大?。籋ashtable 會(huì)直接使用初始值。

10. 與 HashSet 的比較

HashSet 底層就是基于HashMap實(shí)現(xiàn)的。 (HashSet 的源碼非常非常少，因?yàn)槌?clone() 方法、writeObject()方法、readObject()方法是 HashSet 自己不得不實(shí)現(xiàn)之外， 其他方法都是直接調(diào)用 HashMap 中的方法。)

二、LinkedHashMap

1.存儲(chǔ)結(jié)構(gòu)

繼承自 HashMap，因此具有和 HashMap 一樣的快速查找特性。

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

內(nèi)部維護(hù)了一個(gè)雙向鏈表，用來維護(hù)插入順序或者 LRU 順序。

/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;
/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> tail;

accessOrder 決定了順序，默認(rèn)為 false，此時(shí)維護(hù)的是插入順序。

final boolean accessOrder;

LinkedHashMap 最重要的是以下用于維護(hù)順序的函數(shù)，它們會(huì)在 put、get 等方法中調(diào)用。

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }

2.afterNodeAccess()

當(dāng)一個(gè)節(jié)點(diǎn)被訪問時(shí)，如果 accessOrder 為 true，則會(huì)將該節(jié)點(diǎn)移到鏈表尾部。也就是說指定為 LRU 順序之后，在每次訪問一個(gè)節(jié)點(diǎn)時(shí)，會(huì)將這個(gè)節(jié)點(diǎn)移到鏈表尾部，保證鏈表尾部是最近訪問的節(jié)點(diǎn)，那么鏈表首部就是最近最久未使用的節(jié)點(diǎn)。

void afterNodeAccess(Node<K,V> e) {
    // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
                    (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
                    head = a; else
                    b.after = a;
        if (a != null)
                    a.before = b; else
                    last = b;
        if (last == null)
                    head = p; else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

3.afterNodeInsertion()

在 put 等操作之后執(zhí)行，當(dāng) removeEldestEntry() 方法返回 true 時(shí)會(huì)移除最晚的節(jié)點(diǎn)，也就是鏈表首部節(jié)點(diǎn) first。

evict 只有在構(gòu)建 Map 的時(shí)候才為 false，在這里為 true。

void afterNodeInsertion(Boolean evict) {
    // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

removeEldestEntry() 默認(rèn)為 false，如果需要讓它為 true，需要繼承 LinkedHashMap 并且覆蓋這個(gè)方法的實(shí)現(xiàn)，這在實(shí)現(xiàn) LRU 的緩存中特別有用，通過移除最近最久未使用的節(jié)點(diǎn)，從而保證緩存空間足夠，并且緩存的數(shù)據(jù)都是熱點(diǎn)數(shù)據(jù)。

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

4.LRU 緩存

以下是使用 LinkedHashMap 實(shí)現(xiàn)的一個(gè) LRU 緩存：

• 設(shè)定最大緩存空間 MAX_ENTRIES 為 3；

• 使用 LinkedHashMap 的構(gòu)造函數(shù)將 accessOrder 設(shè)置為 true，開啟 LRU 順序；

• 覆蓋 removeEldestEntry() 方法實(shí)現(xiàn)，在節(jié)點(diǎn)多于 MAX_ENTRIES 就會(huì)將最近最久未使用的數(shù)據(jù)移除。

public class LRUCache<K,V> extends LinkedHashMap<K,V>{
    private static final int MAX_ENTRIES = 3;
    LRUCache(){
        super(MAX_ENTRIES,0.75f,true);
    }
    /**
     * removeEldestEntry() 默認(rèn)為 false，
     * 如果需要讓它為 true，需要繼承 LinkedHashMap 并且覆蓋這個(gè)方法的實(shí)現(xiàn)，
     * 這在實(shí)現(xiàn) LRU 的緩存中特別有用，通過移除最近最久未使用的節(jié)點(diǎn)，
     * 從而保證緩存空間足夠，并且緩存的數(shù)據(jù)都是熱點(diǎn)數(shù)據(jù)。
     */
    @Override
        protected Boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }
    public static void main(String[] args) {
        LRUCache<Integer,String> cache=new LRUCache<>();
        cache.put(1, "a");
        cache.put(2, "b");
        cache.put(3, "c");
        cache.get(1);
        //LRU  鍵值1被訪問過了，則最近最久未訪問的就是2
        cache.put(4, "d");
        System.out.println(cache.keySet());
    }
}

[3, 1, 4]

三、WeakHashMap

1.存儲(chǔ)結(jié)構(gòu)

WeakHashMap 的 Entry 繼承自 WeakReference，被 WeakReference 關(guān)聯(lián)的對(duì)象在下一次垃圾回收時(shí)會(huì)被回收。

WeakHashMap 主要用來實(shí)現(xiàn)緩存，通過使用 WeakHashMap 來引用緩存對(duì)象，由 JVM 對(duì)這部分緩存進(jìn)行回收。

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V>

2.ConcurrentCache

Tomcat 中的 ConcurrentCache 使用了 WeakHashMap 來實(shí)現(xiàn)緩存功能。

ConcurrentCache 采取的是分代緩存：

• 經(jīng)常使用的對(duì)象放入 eden 中，eden 使用 ConcurrentHashMap 實(shí)現(xiàn)，不用擔(dān)心會(huì)被回收；

• 不常用的對(duì)象放入 longterm，longterm 使用 WeakHashMap 實(shí)現(xiàn)，這些老對(duì)象會(huì)被垃圾收集器回收。

• 當(dāng)調(diào)用 get() 方法時(shí)，會(huì)先從 eden 區(qū)獲取，如果沒有找到的話再到 longterm 獲取，當(dāng)從 longterm 獲取到就把對(duì)象放入 eden 中，從而保證經(jīng)常被訪問的節(jié)點(diǎn)不容易被回收。

• 當(dāng)調(diào)用 put() 方法時(shí)，如果 eden 的大小超過了 size，那么就將 eden 中的所有對(duì)象都放入 longterm 中，利用虛擬機(jī)回收掉一部分不經(jīng)常使用的對(duì)象。

public final class ConcurrentCache<K, V> {
    private final int size;
    private final Map<K, V> eden;
    private final Map<K, V> longterm;
    public ConcurrentCache(int size) {
        this.size = size;
        this.eden = new ConcurrentHashMap<>(size);
        this.longterm = new WeakHashMap<>(size);
    }
    public V get(K k) {
        V v = this.eden.get(k);
        if (v == null) {
            v = this.longterm.get(k);
            if (v != null)
                            this.eden.put(k, v);
        }
        return v;
    }
    public void put(K k, V v) {
        if (this.eden.size() >= size) {
            this.longterm.putAll(this.eden);
            this.eden.clear();
        }
        this.eden.put(k, v);
    }
}

上述內(nèi)容就是如何理解Java容器中Map的源碼分析，你們學(xué)到知識(shí)或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備，歡迎關(guān)注億速云行業(yè)資訊頻道。