引言

在之前的文章里，我們聊到了 Java 標(biāo)準(zhǔn)庫(kù)中 HashMap 與 LinkedHashMap 的實(shí)現(xiàn)原理。HashMap 是一個(gè)標(biāo)準(zhǔn)的散列表數(shù)據(jù)結(jié)構(gòu)，而 LinkedHashMap 是在 HashMap 的基礎(chǔ)上實(shí)現(xiàn)的哈希鏈表。

今天，我們來討論 WeakHashMap，其中的 “Weak” 是指什么，與前兩者的使用場(chǎng)景有何不同？我們就圍繞這些問題展開。

學(xué)習(xí)路線圖：

1. 回顧 HashMap 和 LinkedHashMap

其實(shí)，WeakHashMap 與 HashMap 和 LinkedHashMap 的數(shù)據(jù)結(jié)構(gòu)大同小異，所以我們先回顧后者的實(shí)現(xiàn)原理。

1.1 說一下 HashMap 的實(shí)現(xiàn)結(jié)構(gòu)

HashMap 是基于分離鏈表法解決散列沖突的動(dòng)態(tài)散列表。

• 1、HashMap 在 Java 7 中使用的是 “數(shù)組 + 鏈表”，發(fā)生散列沖突的鍵值對(duì)會(huì)用頭插法添加到單鏈表中；
• 2、HashMap 在 Java 8 中使用的是 “數(shù)組 + 鏈表 + 紅黑樹”，發(fā)生散列沖突的鍵值對(duì)會(huì)用尾插法添加到單鏈表中。如果鏈表的長(zhǎng)度大于 8 時(shí)且散列表容量大于 64，會(huì)將鏈表樹化為紅黑樹。

散列表示意圖

HashMap 實(shí)現(xiàn)示意圖

1.2 說一下 LinkedHashMap 的實(shí)現(xiàn)結(jié)構(gòu)

LinkedHashMap 是繼承于 HashMap 實(shí)現(xiàn)的哈希鏈表。

• 1、LinkedHashMap 同時(shí)具備雙向鏈表和散列表的特點(diǎn)。當(dāng) LinkedHashMap 作為散列表時(shí)，主要體現(xiàn)出 O(1) 時(shí)間復(fù)雜度的查詢效率。當(dāng) LinkedHashMap 作為雙向鏈表時(shí)，主要體現(xiàn)出有序的特性；
• 2、LinkedHashMap 支持 FIFO 和 LRU 兩種排序模式，默認(rèn)是 FIFO 排序模式，即按照插入順序排序。Android 中的 LruCache 內(nèi)存緩存和 DiskLruCache 磁盤緩存也是直接復(fù)用 LinkedHashMap 提供的緩存管理能力。

LinkedHashMap 示意圖

FIFO 與 LRU 策略

2. 認(rèn)識(shí) WeakHashMap

2.1 WeakReference 弱引用的特點(diǎn)

WeakHashMap 中的 “Weak” 指鍵 Key 是弱引用，也叫弱鍵。弱引用是 Java 四大引用類型之一，一共有四種引用類型，分別是強(qiáng)引用、軟引用、弱引用和虛引用。我將它們的區(qū)別概括為 3 個(gè)維度：

維度 1 - 對(duì)象可達(dá)性狀態(tài)的區(qū)別： 強(qiáng)引用指向的對(duì)象是強(qiáng)可達(dá)的，只有強(qiáng)可達(dá)的對(duì)象才會(huì)認(rèn)為是存活的對(duì)象，才能保證在垃圾收集的過程中不會(huì)被回收；

維度 2 - 垃圾回收策略的區(qū)別： 不同的引用類型的回收激進(jìn)程度不同，

• 強(qiáng)引用指向的對(duì)象不會(huì)被回收；
• 軟引用指向的對(duì)象在內(nèi)存充足時(shí)不會(huì)被回收，在內(nèi)存不足時(shí)會(huì)被回收；
• 弱引用和虛引用指向的對(duì)象無論在內(nèi)存是否充足的時(shí)候都會(huì)被回收；

維度 3 - 感知垃圾回收時(shí)機(jī)： 當(dāng)引用對(duì)象關(guān)聯(lián)的實(shí)際對(duì)象被垃圾回收時(shí)，引用對(duì)象會(huì)進(jìn)入關(guān)聯(lián)的引用隊(duì)列，程序可以通過觀察引用隊(duì)列的方式，感知對(duì)象被垃圾回收的時(shí)機(jī)。

感知垃圾回收示意圖

提示： 關(guān)于 “Java 四種引用類型” 的區(qū)別，在小彭的 Java 專欄中深入討論過 《吊打面試官：說一下 Java 的四種引用類型》，去看看。

2.2 WeakHashMap 的特點(diǎn)

WeakHashMap 是使用弱鍵的動(dòng)態(tài)散列表，用于實(shí)現(xiàn) “自動(dòng)清理” 的內(nèi)存緩存。

• 1、WeakHashMap 使用與 Java 7 HashMap 相同的 “數(shù)組 + 鏈表” 解決散列沖突，發(fā)生散列沖突的鍵值對(duì)會(huì)用頭插法添加到單鏈表中；
• 2、WeakHashMap 依賴于 Java 垃圾收集器自動(dòng)清理不可達(dá)對(duì)象的特性。當(dāng) Key 對(duì)象不再被持有強(qiáng)引用時(shí)，垃圾收集器會(huì)按照弱引用策略自動(dòng)回收 Key 對(duì)象，并在下次訪問 WeakHashMap 時(shí)清理全部無效的鍵值對(duì)。因此，WeakHashMap 特別適合實(shí)現(xiàn) “自動(dòng)清理” 的內(nèi)存活動(dòng)緩存，當(dāng)鍵值對(duì)有效時(shí)保留，在鍵值對(duì)無效時(shí)自動(dòng)被垃圾收集器清理；
• 3、需要注意，因?yàn)?WeakHashMap 會(huì)持有 Value 對(duì)象的強(qiáng)引用，所以在 Value 對(duì)象中一定不能持有 key 的強(qiáng)引用。否則，會(huì)阻止垃圾收集器回收 “本該不可達(dá)” 的 Key 對(duì)象，使得 WeakHashMap 失去作用。
• 4、與 HashMap 相同，LinkedHashMap 也不考慮線程同步，也會(huì)存在線程安全問題。可以使用 Collections.synchronizedMap 包裝類，其原理也是在所有方法上增加 synchronized 關(guān)鍵字。

WeakHashMap 示意圖

2.3 說一下 WeakHashMap 與 HashMap 和 LinkedHashMap 的區(qū)別？

WeakHashMap 與 HashMap 都是基于分離鏈表法解決散列沖突的動(dòng)態(tài)散列表，兩者的主要區(qū)別在鍵 Key 的引用類型上：

HashMap 會(huì)持有鍵 Key 的強(qiáng)引用，除非手動(dòng)移除，否則鍵值對(duì)會(huì)長(zhǎng)期存在于散列表中。而 WeakHashMap 只持有鍵 Key 的弱引用，當(dāng) Key 對(duì)象不再被外部持有強(qiáng)引用時(shí)，鍵值對(duì)會(huì)被自動(dòng)被清理。

WeakHashMap 與 LinkedHashMap 都有自動(dòng)清理的能力，兩者的主要區(qū)別在于淘汰數(shù)據(jù)的策略上：

LinkedHashMap 會(huì)按照 FIFO 或 LRU 的策略 “嘗試” 淘汰數(shù)據(jù)，需要開發(fā)者重寫 removeEldestEntry() 方法實(shí)現(xiàn)是否刪除最早節(jié)點(diǎn)的判斷邏輯。而 WeakHashMap 會(huì)按照 Key 對(duì)象的可達(dá)性淘汰數(shù)據(jù)，當(dāng) Key 對(duì)象不再被持有強(qiáng)引用時(shí)，會(huì)自動(dòng)清理無效數(shù)據(jù)。

2.4 重建 Key 對(duì)象不等價(jià)的問題

WeakHashMap 的 Key 使用弱引用，也就是以 Key 作為清理數(shù)據(jù)的判斷錨點(diǎn)，當(dāng) Key 變得不可達(dá)時(shí)會(huì)自動(dòng)清理數(shù)據(jù)。此時(shí)，如果使用多個(gè) equals 相等的 Key 對(duì)象訪問鍵值對(duì)，就會(huì)出現(xiàn)第 1 個(gè) Key 對(duì)象不可達(dá)導(dǎo)致鍵值對(duì)被回收，而第 2 個(gè) Key 查詢鍵值對(duì)為 null 的問題。這說明 equals 相等的 Key 對(duì)象在 HashMap 等散列表中是等價(jià)的，但是在 WeakHashMap 散列表中是不等價(jià)的。

因此，如果 Key 類型沒有重寫 equals 方法，那么 WeakHashMap 就表現(xiàn)良好，否則會(huì)存在歧義。例如下面這個(gè) Demo 中，首先創(chuàng)建了指向 image_url1 的圖片 Key1，再重建了同樣指向 image_url1 的圖片 Key2。在 HashMap 中，Key1 和 Key2 等價(jià)，但在 WeakHashMap 中，Key1 和 Key2 不等價(jià)。

Demo

class ImageKey {
    private String url;
    ImageKey(String url) {
        this.url = url;
    }
    public boolean equals(Object obj) {
        return (obj instanceOf ImageKey) && Objects.equals(((ImageKey)obj).url, this.url);
    }
}
WeakHashMap<ImageKey, Bitmap> map = new WeakHashMap<>();
ImageKey key1 = new ImageKey("image_url1");
ImageKey key2 = new ImageKey("image_url2");
// key1 equalsTo key3
ImageKey key3 = new ImageKey("image_url1");
map.put(key1, bitmap1);
map.put(key2, bitmap2);
System.out.println(map.get(key1)); // 輸出 bitmap1
System.out.println(map.get(key2)); // 輸出 bitmap2
System.out.println(map.get(key3)); // 輸出 bitmap1
// 使 key1 不可達(dá)，key3 保持
key1 = null;
// 說明重建 Key 與原始 Key 不等價(jià)
System.out.println(map.get(key1)); // 輸出 null
System.out.println(map.get(key2)); // 輸出 bitmap2
System.out.println(map.get(key3)); // 輸出 null

默認(rèn)的 Object#equals 是判斷兩個(gè)變量是否指向同一個(gè)對(duì)象：

Object.java

public boolean equals(Object obj) {
    return (this == obj);
}

2.5 Key 弱引用和 Value 弱引用的區(qū)別

不管是 Key 還是 Value 使用弱引用都可以實(shí)現(xiàn)自動(dòng)清理，至于使用哪一種方法各有優(yōu)缺點(diǎn)，適用場(chǎng)景也不同。

Key 弱引用： 以 Key 作為清理數(shù)據(jù)的判斷錨點(diǎn)，當(dāng) Key 不可達(dá)時(shí)清理數(shù)據(jù)。優(yōu)點(diǎn)是容器外不需要持有 Value 的強(qiáng)引用，缺點(diǎn)是重建的 Key 與原始 Key 不等價(jià)，重建 Key 無法阻止數(shù)據(jù)被清理；

Value 弱引用： 以 Value 作為清理數(shù)據(jù)的判斷錨點(diǎn)，當(dāng) Value 不可達(dá)時(shí)清理數(shù)據(jù)。優(yōu)點(diǎn)是重建 Key 與與原始 Key 等價(jià)，缺點(diǎn)是容器外需要持有 Value 的強(qiáng)引用。

舉例 1： 在 Android Glide 圖片框架的多級(jí)緩存中，因?yàn)閳D片的 EngineKey 是可重建的，存在多個(gè) EngineKey 對(duì)象指向同一個(gè)圖片 Bitmap，所以 Glide 最頂層的活動(dòng)緩存采用的是 Value 弱引用。

EngineKey.java

class EngineKey implements Key {
    // 重寫 equals
    @Override
    public boolean equals(Object o) {
        if (o instanceof EngineKey) {
            EngineKey other = (EngineKey) o;
            return model.equals(other.model)
                && signature.equals(other.signature)
                && height == other.height
                && width == other.width
                && transformations.equals(other.transformations)
                && resourceClass.equals(other.resourceClass)
                && transcodeClass.equals(other.transcodeClass)
                && options.equals(other.options);
        }
        return false;
    }
}

舉例 2： 在 ThreadLocal 的 ThreadLocalMap 線程本地存儲(chǔ)中，因?yàn)?ThreadLocal 沒有重寫 equals，不存在多個(gè) ThreadLocal 對(duì)象指向同一個(gè)鍵值對(duì)的情況，所以 ThreadLocal 采用的是 Key 弱引用。

ThreadLocal.java

static class Entry extends WeakReference<ThreadLocal<?>> {
    /** The value associated with this ThreadLocal. */
    Object value;
    Entry(ThreadLocal<?> k, Object v) {
        super(k);
        value = v;
    }
}

3. WeakHashMap 源碼分析

這一節(jié)，我們來分析 WeakHashMap 中主要流程的源碼。

事實(shí)上，WeakHashMap 就是照著 Java 7 版本的 HashMap 依葫蘆畫瓢的，沒有樹化的邏輯?？紤]到我們已經(jīng)對(duì) HashMap 做過詳細(xì)分析，所以我們沒有必要重復(fù)分析 WeakHashMap 的每個(gè)細(xì)節(jié)，而是把重心放在 WeakHashMap 與 HashMap 不同的地方。

3.1 WeakHashMap 的屬性

先用一個(gè)表格整理 WeakHashMap 的屬性：

WeakHashMap.java

public class WeakHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V> {
    // 默認(rèn)數(shù)組容量
    private static final int DEFAULT_INITIAL_CAPACITY = 16;
    // 數(shù)組最大容量：2^30（高位 0100，低位都是 0）
    private static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默認(rèn)裝載因子上限：0.75
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 底層數(shù)組
    Entry<K,V>[] table;
    // 鍵值對(duì)數(shù)量
    private int size;
    // 擴(kuò)容閾值（容量 * 裝載因子）
    private int threshold;
    // 裝載因子上限
    private final float loadFactor;
    // 引用隊(duì)列
    private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
    // 修改計(jì)數(shù)
    int modCount;
    // 鏈表節(jié)點(diǎn)（一個(gè) Entry 等于一個(gè)鍵值對(duì)）
    private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
        // 與 HashMap 和 LinkedHashMap 相比，少了 key 的強(qiáng)引用
        // final K key;
        // Value（強(qiáng)引用）
        V value;
        // 哈希值
        final int hash;
        Entry<K,V> next;
        Entry(Object key, V value, ReferenceQueue<Object> queue, int hash, Entry<K,V> next) {
            super(key /*注意：只有 Key 是弱引用*/, queue);
            this.value = value;
            this.hash  = hash;
            this.next  = next;
        }
    }
}

WeakHashMap 與 HashMap 的屬性幾乎相同，主要區(qū)別有 2 個(gè)：

• 1、ReferenceQueue： WeakHashMap 的屬性里多了一個(gè) queue 引用隊(duì)列；
• 2、Entry： WeakHashMap#Entry 節(jié)點(diǎn)繼承于 WeakReference，表面看是 WeakHashMap 持有了 Entry 的強(qiáng)引用，其實(shí)不是。注意看 Entry 的構(gòu)造方法，WeakReference 關(guān)聯(lián)的實(shí)際對(duì)象是 Key。 所以，WeakHashMap 依然持有 Entry 和 Value 的強(qiáng)引用，僅持有 Key 的弱引用。

引用關(guān)系示意圖

不出意外的話又有小朋友出來舉手提問了????‍♀?：

• ????‍♀?疑問 1：說一下 ReferenceQueue queue 的作用?

ReferenceQueue 與 Reference 配合能夠?qū)崿F(xiàn)感知對(duì)象被垃圾回收的能力。在創(chuàng)建引用對(duì)象時(shí)可以關(guān)聯(lián)一個(gè)實(shí)際對(duì)象和一個(gè)引用隊(duì)列，當(dāng)實(shí)現(xiàn)對(duì)象被垃圾回收后，引用對(duì)象會(huì)被添加到這個(gè)引用隊(duì)列中。在 WeakHashMap 中，就是根據(jù)這個(gè)引用隊(duì)列來自動(dòng)清理無效鍵值對(duì)。

• ????‍♀?疑問 2：為什么 Key 是弱引用，而不是 Entry 或 Value 是弱引用？

首先，Entry 一定要持有強(qiáng)引用，而不能持有弱引用。這是因?yàn)?Entry 是 WeakHashMap 內(nèi)部維護(hù)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)細(xì)節(jié)，并不會(huì)暴露到 WeakHashMap 外部，即除了 WeakHashMap 本身之外沒有其它地方持有 Entry 的強(qiáng)引用。所以，如果持有 Entry 的弱引用，即使 WeakHashMap 外部依然在使用 Key 對(duì)象，WeakHashMap 內(nèi)部依然會(huì)回收鍵值對(duì)，這與預(yù)期不符。

其次，不管是 Key 還是 Value 使用弱引用都可以實(shí)現(xiàn)自動(dòng)清理。至于使用哪一種方法各有優(yōu)缺點(diǎn)，適用場(chǎng)景也不同，這個(gè)在前文分析過了。

3.2 WeakHashMap 如何清理無效數(shù)據(jù)？

在通過 put / get /size 等方法訪問 WeakHashMap 時(shí)，其內(nèi)部會(huì)調(diào)用 expungeStaleEntries() 方法清理 Key 對(duì)象已經(jīng)被回收的無效鍵值對(duì)。其中會(huì)遍歷 ReferenceQueu 中持有的弱引用對(duì)象（即 Entry 節(jié)點(diǎn)），并將該結(jié)點(diǎn)從散列表中移除。

private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
// 添加鍵值對(duì)
public V put(K key, V value) {
    ...
    // 間接 expungeStaleEntries()
    Entry<K,V>[] tab = getTable();
    ...
}
// 擴(kuò)容
void resize(int newCapacity) {
    // 間接 expungeStaleEntries()
    Entry<K,V>[] oldTable = getTable();
    ...
}
// 獲取鍵值對(duì)
public V get(Object key) {
    ...
    // 間接 expungeStaleEntries()
    Entry<K,V>[] tab = getTable();
    ...
}
private Entry<K,V>[] getTable() {
    // 清理無效鍵值對(duì)
    expungeStaleEntries();
    return table;
}
// ->清理無效鍵值對(duì)
private void expungeStaleEntries() {
    // 遍歷引用隊(duì)列
    for (Object x; (x = queue.poll()) != null; ) {
        // 疑問 3：既然 WeakHashMap 不考慮線程同步，為什么這里要做加鎖，豈不是突兀？
        synchronized (queue) {
            Entry<K,V> e = (Entry<K,V>) x;
            // 根據(jù)散列值定位數(shù)組下標(biāo)
            int i = indexFor(e.hash /*散列值*/, table.length);
            // 遍歷桶尋找節(jié)點(diǎn) e 的前驅(qū)結(jié)點(diǎn)
            Entry<K,V> prev = table[i];
            Entry<K,V> p = prev;
            while (p != null) {
                Entry<K,V> next = p.next;
                if (p == e) {
                    // 刪除節(jié)點(diǎn) e
                    if (prev == e)					
                        // 節(jié)點(diǎn) e 是根節(jié)點(diǎn)
                        table[i] = next;
                    else
                        // 節(jié)點(diǎn) e 是中間節(jié)點(diǎn)
                        prev.next = next;
                    // Must not null out e.next;
                    // stale entries may be in use by a HashIterator
                    e.value = null; // Help GC
                    size--;
                    break;
                }
                prev = p;
                p = next;
            }
        }
    }
}

總結(jié)

1、WeakHashMap 使用與 Java 7 HashMap 相同的 “數(shù)組 + 鏈表” 解決散列沖突，發(fā)生散列沖突的鍵值對(duì)會(huì)用頭插法添加到單鏈表中；

2、WeakHashMap 能夠?qū)崿F(xiàn) “自動(dòng)清理” 的內(nèi)存緩存，其中的 “Weak” 指鍵 Key 是弱引用。當(dāng) Key 對(duì)象不再被持有強(qiáng)引用時(shí)，垃圾收集器會(huì)按照弱引用策略自動(dòng)回收 Key 對(duì)象，并在下次訪問 WeakHashMap 時(shí)清理全部無效的鍵值對(duì)；

3、WeakHashMap 和 LinkedHashMap 都具備 “自動(dòng)清理” 的 能力，WeakHashMap 根據(jù) Key 對(duì)象的可達(dá)性淘汰數(shù)據(jù)，而 LinkedHashMap 根據(jù) FIFO 或 LRU 策略嘗試淘汰數(shù)據(jù)；

4、WeakHashMap 使用 Key 弱引用，會(huì)存在重建 Key 對(duì)象不等價(jià)問題。

以上就是WeakHashMap 和 HashMap 的區(qū)別是什么，何時(shí)使用的詳細(xì)內(nèi)容，更多關(guān)于WeakHashMap HashMap區(qū)別的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論