WeakHashMap 和 HashMap 區別及使用場景

Posted on 2022-11-14 by WalkonNet

引言

在之前的文章裡，我們聊到瞭 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 的強引用。

類型	優點	缺點	場景
Key 弱引用	外部不需要持有 Value 的強引用，使用更簡單	重建 Key 不等價	未重寫 equals
Value 弱引用	重建 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;
    }
}

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.75
WeakHashMap	數組 + 鏈表	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> {
        // 與 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 對象已經被回收的無效鍵值對。其中會遍歷 ReferenceQueu 中持有的弱引用對象（即 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;
            }
        }
    }
}

總結

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 的區別是什麼，何時使用的詳細內容，更多關於WeakHashMap HashMap區別的資料請關註WalkonNet其它相關文章！

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 如何清理無效數據？

總結

推薦閱讀：

發佈留言取消回覆

近期文章

目錄

引言

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 如何清理無效數據？

總結

推薦閱讀：

發佈留言 取消回覆

近期文章

標籤

發佈留言取消回覆