WeakHashMap 和 HashMap 區別及使用場景

引言

在之前的文章裡，我們聊到了 Java 標準庫中 HashMap 與 LinkedHashMap 的實現原理。HashMap 是一個標準的雜湊表資料結構，而 LinkedHashMap 是在 HashMap 的基礎上實現的雜湊連結串列。

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

學習路線圖：

1. 回顧 HashMap 和 LinkedHashMap

其實，WeakHashMap 與 HashMap 和 LinkedHashMap 的資料結構大同小異，所以我們先回顧後者的實現原理。

1.1 說一下 HashMap 的實現結構

HashMap 是基於分離連結串列法解決雜湊衝突的動態雜湊表。

• 1、HashMap 在 Java 7 中使用的是 “陣列 + 連結串列”，發生雜湊衝突的鍵值對會用頭插法新增到單連結串列中；
• 2、HashMap 在 Java 8 中使用的是 “陣列 + 連結串列 + 紅黑樹”，發生雜湊衝突的鍵值對會用尾插法新增到單連結串列中。如果連結串列的長度大於 8 時且雜湊表容量大於 64，會將連結串列樹化為紅黑樹。

雜湊表示意圖

HashMap 實現示意圖

1.2 說一下 LinkedHashMap 的實現結構

LinkedHashMap 是繼承於 HashMap 實現的雜湊連結串列。

• 1、LinkedHashMap 同時具備雙向連結串列和雜湊表的特點。當 LinkedHashMap 作為雜湊表時，主要體現出 O(1) 時間複雜度的查詢效率。當 LinkedHashMap 作為雙向連結串列時，主要體現出有序的特性；
• 2、LinkedHashMap 支援 FIFO 和 LRU 兩種排序模式，預設是 FIFO 排序模式，即按照插入順序排序。Android 中的 LruCache 記憶體快取和 DiskLruCache 磁碟快取也是直接複用 LinkedHashMap 提供的快取管理能力。

LinkedHashMap 示意圖

FIFO 與 LRU 策略

2. 認識 WeakHashMap

2.1 WeakReference 弱參照的特點

WeakHashMap 中的 “Weak” 指鍵 Key 是弱參照，也叫弱鍵。弱參照是 Java 四大參照型別之一，一共有四種參照型別，分別是強參照、軟參照、弱參照和虛參照。我將它們的區別概括為 3 個維度：

維度 1 - 物件可達性狀態的區別： 強參照指向的物件是強可達的，只有強可達的物件才會認為是存活的物件，才能保證在垃圾收集的過程中不會被回收；

維度 2 - 垃圾回收策略的區別： 不同的參照型別的回收激程序度不同，

• 強參照指向的物件不會被回收；
• 軟參照指向的物件在記憶體充足時不會被回收，在記憶體不足時會被回收；
• 弱參照和虛參照指向的物件無論在記憶體是否充足的時候都會被回收；

維度 3 - 感知垃圾回收時機： 當參照物件關聯的實際物件被垃圾回收時，參照物件會進入關聯的參照佇列，程式可以通過觀察參照佇列的方式，感知物件被垃圾回收的時機。

感知垃圾回收示意圖

提示： 關於 “Java 四種參照型別” 的區別，在小彭的 Java 專欄中深入討論過 《吊打面試官：說一下 Java 的四種參照型別》，去看看。

2.2 WeakHashMap 的特點

WeakHashMap 是使用弱鍵的動態雜湊表，用於實現 “自動清理” 的記憶體快取。

• 1、WeakHashMap 使用與 Java 7 HashMap 相同的 “陣列 + 連結串列” 解決雜湊衝突，發生雜湊衝突的鍵值對會用頭插法新增到單連結串列中；
• 2、WeakHashMap 依賴於 Java 垃圾收集器自動清理不可達物件的特性。當 Key 物件不再被持有強參照時，垃圾收集器會按照弱參照策略自動回收 Key 物件，並在下次存取 WeakHashMap 時清理全部無效的鍵值對。因此，WeakHashMap 特別適合實現 “自動清理” 的記憶體活動快取，當鍵值對有效時保留，在鍵值對無效時自動被垃圾收集器清理；
• 3、需要注意，因為 WeakHashMap 會持有 Value 物件的強參照，所以在 Value 物件中一定不能持有 key 的強參照。否則，會阻止垃圾收集器回收 “本該不可達” 的 Key 物件，使得 WeakHashMap 失去作用。
• 4、與 HashMap 相同，LinkedHashMap 也不考慮執行緒同步，也會存線上程安全問題。可以使用 Collections.synchronizedMap 包裝類，其原理也是在所有方法上增加 synchronized 關鍵字。

WeakHashMap 示意圖

2.3 說一下 WeakHashMap 與 HashMap 和 LinkedHashMap 的區別？

WeakHashMap 與 HashMap 都是基於分離連結串列法解決雜湊衝突的動態雜湊表，兩者的主要區別在鍵 Key 的參照型別上：

HashMap 會持有鍵 Key 的強參照，除非手動移除，否則鍵值對會長期存在於雜湊表中。而 WeakHashMap 只持有鍵 Key 的弱參照，當 Key 物件不再被外部持有強參照時，鍵值對會被自動被清理。

WeakHashMap 與 LinkedHashMap 都有自動清理的能力，兩者的主要區別在於淘汰資料的策略上：

LinkedHashMap 會按照 FIFO 或 LRU 的策略 “嘗試” 淘汰資料，需要開發者重寫 removeEldestEntry() 方法實現是否刪除最早節點的判斷邏輯。而 WeakHashMap 會按照 Key 物件的可達性淘汰資料，當 Key 物件不再被持有強參照時，會自動清理無效資料。

2.4 重建 Key 物件不等價的問題

WeakHashMap 的 Key 使用弱參照，也就是以 Key 作為清理資料的判斷錨點，當 Key 變得不可達時會自動清理資料。此時，如果使用多個 equals 相等的 Key 物件存取鍵值對，就會出現第 1 個 Key 物件不可達導致鍵值對被回收，而第 2 個 Key 查詢鍵值對為 null 的問題。這說明 equals 相等的 Key 物件在 HashMap 等雜湊表中是等價的，但是在 WeakHashMap 雜湊表中是不等價的。

因此，如果 Key 型別沒有重寫 equals 方法，那麼 WeakHashMap 就表現良好，否則會存在歧義。例如下面這個 Demo 中，首先建立了指向 image_url1 的圖片 Key1，再重建了同樣指向 image_url1 的圖片 Key2。在 HashMap 中，Key1 和 Key2 等價，但在 WeakHashMap 中，Key1 和 Key2 不等價。

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 不可達，key3 保持
key1 = null;
// 說明重建 Key 與原始 Key 不等價
System.out.println(map.get(key1)); // 輸出 null
System.out.println(map.get(key2)); // 輸出 bitmap2
System.out.println(map.get(key3)); // 輸出 null

預設的 Object#equals 是判斷兩個變數是否指向同一個物件：

Object.java

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

2.5 Key 弱參照和 Value 弱參照的區別

不管是 Key 還是 Value 使用弱參照都可以實現自動清理，至於使用哪一種方法各有優缺點，適用場景也不同。

Key 弱參照： 以 Key 作為清理資料的判斷錨點，當 Key 不可達時清理資料。優點是容器外不需要持有 Value 的強參照，缺點是重建的 Key 與原始 Key 不等價，重建 Key 無法阻止資料被清理；

Value 弱參照： 以 Value 作為清理資料的判斷錨點，當 Value 不可達時清理資料。優點是重建 Key 與與原始 Key 等價，缺點是容器外需要持有 Value 的強參照。

舉例 1： 在 Android Glide 圖片框架的多級快取中，因為圖片的 EngineKey 是可重建的，存在多個 EngineKey 物件指向同一個圖片 Bitmap，所以 Glide 最頂層的活動快取採用的是 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 執行緒本地儲存中，因為 ThreadLocal 沒有重寫 equals，不存在多個 ThreadLocal 物件指向同一個鍵值對的情況，所以 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 原始碼分析

這一節，我們來分析 WeakHashMap 中主要流程的原始碼。

事實上，WeakHashMap 就是照著 Java 7 版本的 HashMap 依葫蘆畫瓢的，沒有樹化的邏輯。考慮到我們已經對 HashMap 做過詳細分析，所以我們沒有必要重複分析 WeakHashMap 的每個細節，而是把重心放在 WeakHashMap 與 HashMap 不同的地方。

3.1 WeakHashMap 的屬性

先用一個表格整理 WeakHashMap 的屬性：

WeakHashMap.java

public class WeakHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V> {
    // 預設陣列容量
    private static final int DEFAULT_INITIAL_CAPACITY = 16;
    // 陣列最大容量：2^30（高位 0100，低位都是 0）
    private static final int MAXIMUM_CAPACITY = 1 << 30;
    // 預設裝載因子上限：0.75
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 底層陣列
    Entry<K,V>[] table;
    // 鍵值對數量
    private int size;
    // 擴容閾值（容量 * 裝載因子）
    private int threshold;
    // 裝載因子上限
    private final float loadFactor;
    // 參照佇列
    private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
    // 修改計數
    int modCount;
    // 連結串列節點（一個 Entry 等於一個鍵值對）
    private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
        // 與 HashMap 和 LinkedHashMap 相比，少了 key 的強參照
        // final K key;
        // Value（強參照）
        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 的屬性幾乎相同，主要區別有 2 個：

• 1、ReferenceQueue： WeakHashMap 的屬性裡多了一個 queue 參照佇列；
• 2、Entry： WeakHashMap#Entry 節點繼承於 WeakReference，表面看是 WeakHashMap 持有了 Entry 的強參照，其實不是。注意看 Entry 的構造方法，WeakReference 關聯的實際物件是 Key。 所以，WeakHashMap 依然持有 Entry 和 Value 的強參照，僅持有 Key 的弱參照。

參照關係示意圖

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