本文已收錄到 AndroidFamily，技術和職場問題，請關注公衆号 [彭旭銳] 提問。

前言

大家好，我是小彭。

在之前的文章裡，我們聊到了 Java 标準庫中 HashMap 與 LinkedHashMap 的實作原理。HashMap 是一個标準的散清單資料結構，而 LinkedHashMap 是在 HashMap 的基礎上實作的哈希連結清單。

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

提示：本文源碼基于 JDK 1.2 WeakHashMap。

小彭的 Android 交流群 02 群已經建立啦~

思維導圖：

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 示意圖

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 的強引用。

類型優點缺點場景Key 弱引用外部不需要持有 Value 的強引用，使用更簡單重建 Key 不等價未重寫 equalsValue 弱引用重建 Key 等價外部需要持有 Value 的強引用重寫 equals

舉例 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;
    }
    
    // 未重寫 equals
}

3. WeakHashMap 源碼分析

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

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

3.1 WeakHashMap 的屬性

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

版本資料結構節點實作類屬性Java 7 HashMap數組 + 連結清單Entry（單連結清單）1、table（數組）

2、size（尺寸）

3、threshold（擴容門檻值）

4、loadFactor（裝載因子上限）

5、modCount（修改計數）

6、預設數組容量 16

7、最大數組容量 2^30

8、預設負載因子 0.75WeakHashMap數組 + 連結清單Entry（單連結清單，弱引用的子類型）9、queue（引用隊列）

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> {
        // Key：與 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 的弱引用。

引用關系示意圖

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

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

ReferenceQueue 與 Reference 配合能夠實作感覺對象被垃圾回收的能力。在建立引用對象時可以關聯一個實際對象和一個引用隊列，當實作對象被垃圾回收後，引用對象會被添加到這個引用隊列中。在 WeakHashMap 中，就是根據這個引用隊列來自動清理無效鍵值對。

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

首先，Entry 一定要持有強引用，而不能持有弱引用。這是因為 Entry 是 WeakHashMap 内部維護資料結構的實作細節，并不會暴露到 WeakHashMap 外部，即除了 WeakHashMap 本身之外沒有其它地方持有 Entry 的強引用。是以，如果持有 Entry 的弱引用，即使 WeakHashMap 外部依然在使用 Key 對象，WeakHashMap 内部依然會回收鍵值對，這與預期不符。

其次，不管是 Key 還是 Value 使用弱引用都可以實作自動清理。至于使用哪一種方法各有優缺點，适用場景也不同，這個在前文分析過了。

3.2 WeakHashMap 如何清理無效資料？

在通過 put / get /size 等方法通路 WeakHashMap 時，其内部會調用 expungeStaleEntries() 方法清理 Key 對象已經被回收的無效鍵值對。其中會周遊 ReferenceQueue 中持有的弱引用對象（即 Entry 節點），并将該結點從散清單中移除。

private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

// 添加鍵值對
public V put(K key, V value) {
    ...
    // 間接 expungeStaleEntries()
    Entry<K,V>[] tab = getTable();
    ...
}

// 擴容
void resize(int newCapacity) {
    // 間接 expungeStaleEntries()
    Entry<K,V>[] oldTable = getTable();
    ...
}

// 擷取鍵值對
public V get(Object key) {
    ...
    // 間接 expungeStaleEntries()
    Entry<K,V>[] tab = getTable();
    ...
}

private Entry<K,V>[] getTable() {
    // 清理無效鍵值對
    expungeStaleEntries();
    return table;
}

// ->清理無效鍵值對
private void expungeStaleEntries() {
    // 周遊引用隊列
    for (Object x; (x = queue.poll()) != null; ) {
        // 疑問 3：既然 WeakHashMap 不考慮線程同步，為什麼這裡要做加鎖，豈不是突兀？
        synchronized (queue) {
            Entry<K,V> e = (Entry<K,V>) x;
            // 根據散列值定位數組下标
            int i = indexFor(e.hash /*散列值*/, table.length);
            // 周遊桶尋找節點 e 的前驅結點
            Entry<K,V> prev = table[i];
            Entry<K,V> p = prev;
            while (p != null) {
                Entry<K,V> next = p.next;
                if (p == e) {
                    // 删除節點 e
                    if (prev == e)     
                        // 節點 e 是根節點
                        table[i] = next;
                    else
                        // 節點 e 是中間節點
                        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;
            }
        }
    }
}

4. 總結

1、WeakHashMap 使用與 Java 7 HashMap 相同的 “數組 + 連結清單” 解決散列沖突，發生散列沖突的鍵值對會用頭插法添加到單連結清單中；
2、WeakHashMap 能夠實作 “自動清理” 的記憶體緩存，其中的 “Weak” 指鍵 Key 是弱引用。當 Key 對象不再被持有強引用時，垃圾收集器會按照弱引用政策自動回收 Key 對象，并在下次通路 WeakHashMap 時清理全部無效的鍵值對；
3、WeakHashMap 和 LinkedHashMap 都具備 “自動清理” 的能力，WeakHashMap 根據 Key 對象的可達性淘汰資料，而 LinkedHashMap 根據 FIFO 或 LRU 政策嘗試淘汰資料；
4、WeakHashMap 使用 Key 弱引用，會存在重建 Key 對象不等價問題。

WeakHashMap 和 HashMap 的差別是什麼，何時使用？

前言

1. 回顧 HashMap 和 LinkedHashMap

1.1 說一下 HashMap 的實作結構

1.2 說一下 LinkedHashMap 的實作結構

2. 認識 WeakHashMap

2.1 WeakReference 弱引用的特點

2.2 WeakHashMap 的特點

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

2.4 重建 Key 對象不等價的問題

2.5 Key 弱引用和 Value 弱引用的差別

3. WeakHashMap 源碼分析

3.1 WeakHashMap 的屬性

3.2 WeakHashMap 如何清理無效資料？

4. 總結

繼續閱讀

Java集合架構（五）—— Map、HashMap、Hashtable、Properties、SortedMap、TreeMap、WeakHashMap、IdentityHashMap、EnumMap

死磕 java集合之WeakHashMap源碼分析

weakreference實作原理分析

深入淺出的分析 WeakHashMap

WeakHashMap回收時機結合JVM 虛拟機GC的一些了解

Java中WeakHashMap實作原理深究

快速評估圖資料庫何時使用：與關系型資料庫簡要對比，離圖更進一步

API網關、入口控制器或服務網格：何時使用什麼以及為什麼

WeakReference and WeakHashMap

WeakReference(弱引用)與WeakHashMapWeakReference(弱引用)與WeakHashMap

WeakHashMap實作及使用場景目的用途實作方式代碼詳解執行個體解析：tomcat中緩存

深讀源碼-java集合之WeakHashMap源碼分析

Java reference詳解

java8 WeakHashMap接口實作源碼解析

何時使用Kafka而不是RabbitMQ

Java集合之WeakHashMap