歡迎光臨
每天分享高質量文章

Map 大家族的那點事兒 ( 5 ) :WeakHashMap

(點擊上方公眾號,可快速關註)


來源:SylvanasSun’s Blog ,

sylvanassun.github.io/2018/03/16/2018-03-16-map_family/

WeakHashMap是一個基於Map接口實現的散串列,實現細節與HashMap類似(都有負載因子、散列函式等等,但沒有HashMap那麼多優化手段),它的特殊之處在於每個key都是一個弱取用。

首先我們要明白什麼是弱取用,Java將取用分為四類(從JDK1.2開始),強度依次逐漸減弱:

  • 強取用: 就是平常使用的普通取用物件,例如Object obj = new Object(),這就是一個強取用,強取用只要還存在,就不會被垃圾收集器回收。

  • 軟取用: 軟取用表示一個還有用但並非必需的物件,不像強取用,它還需要通過SoftReference類來間接取用標的物件(除了強取用都是如此)。被軟取用關聯的物件,在將要發生記憶體上限溢位異常之前,會被放入回收範圍之中以進行第二次回收(如果第二次回收之後依舊沒有足夠的記憶體,那麼就會丟擲OOM異常)。

  • 弱取用: 同樣是表示一個非必需的物件,但要比軟取用的強度還要弱,需要通過WeakReference類來間接取用標的物件。被弱取用關聯的物件只能存活到下一次垃圾回收發生之前,當觸發垃圾回收時,無論當前記憶體是否足夠,都會回收掉只被弱取用關聯的物件(如果這個物件還被強取用所取用,那麼就不會被回收)。

  • 虛取用: 這是一種最弱的取用關係,需要通過PhantomReference類來間接取用標的物件。一個物件是否有虛取用的存在,完全不會對其生存時間構成影響,也無法通過虛取用來獲得物件實體。虛取用的唯一作用就是能在這個物件被回收時收到一個系統通知(結合ReferenceQueue使用)。基於這點可以通過虛取用來實現物件的解構式,這比使用finalize()函式是要靠譜多了。

WeakHashMap適合用來當做一個快取來使用。假設你的快取系統是基於強取用實現的,那麼你就必須以手動(或者用一條執行緒來不斷輪詢)的方式來刪除一個無效的快取項,而基於弱取用實現的快取項只要沒被其他強取用物件關聯,就會被直接放入回收佇列。

需要註意的是,只有key是被弱取用關聯的,而value一般都是一個強取用物件。因此,需要確保value沒有關聯到它的key,否則會對key的回收產生阻礙。在極端的情況下,一個value物件A取用了另一個key物件D,而與D相對應的value物件C又反過來取用了與A相對應的key物件B,這就會產生一個取用迴圈,導致D與B都無法被正常回收。想要解決這個問題,就只能把value也變成一個弱取用,例如m.put(key, new WeakReference(value)),弱取用之間的互相取用不會產生影響。

查找操作的實現跟HashMap相比簡單了許多,只要讀懂了HashMap,基本都能看懂,原始碼如下:

/**

 * Value representing null keys inside tables.

 */

private static final Object NULL_KEY = new Object();

/**

 * Use NULL_KEY for key if it is null.

 */

private static Object maskNull(Object key) {

    return (key == null) ? NULL_KEY : key;

}

/**

 * Returns index for hash code h.

 */

private static int indexFor(int h, int length) {

    return h & (length-1);

}

public V get(Object key) {

    // WeakHashMap允許null key與null value

    // null key會被替換為一個虛擬值

    Object k = maskNull(key); 

    int h = hash(k);

    Entry[] tab = getTable();

    int index = indexFor(h, tab.length);

    Entry e = tab[index];

    // 遍歷鏈表

    while (e != null) {

        if (e.hash == h && eq(k, e.get()))

            return e.value;

        e = e.next;

    }

    return null;

}

儘管key是一個弱取用,但仍需手動地回收那些已經無效的Entry。這個操作會在getTable()函式中執行,不管是查找、添加還是刪除,都需要呼叫getTable()來獲得buckets陣列,所以這是種防止記憶體泄漏的被動保護措施。

/**

 * The table, resized as necessary. Length MUST Always be a power of two.

 */

Entry[] table;

/**

 * Reference queue for cleared WeakEntries

 */

private final ReferenceQueuequeue = new ReferenceQueue<>();

/**

 * Expunges stale entries from the table.

 */

private void expungeStaleEntries() {

    // 遍歷ReferenceQueue,然後清理table中無效的Entry

    for (Object x; (x = queue.poll()) != null; ) {

        synchronized (queue) {

            @SuppressWarnings(“unchecked”)

                Entry e = (Entry) x;

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

            Entry prev = table[i];

            Entry p = prev;

            while (p != null) {

                Entry next = p.next;

                if (p == e) {

                    if (prev == e)

                        table[i] = next;

                    else

                        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;

            }

        }

    }

}

/**

 * Returns the table after first expunging stale entries.

 */

private Entry[] getTable() {

    expungeStaleEntries();

    return table;

}

然後是插入操作與刪除操作,實現都比較簡單:

public V put(K key, V value) {

    Object k = maskNull(key);

    int h = hash(k);

    Entry[] tab = getTable();

    int i = indexFor(h, tab.length);

    for (Entry e = tab[i]; e != null; e = e.next) {

        if (h == e.hash && eq(k, e.get())) {

            V oldValue = e.value;

            if (value != oldValue)

                e.value = value;

            return oldValue;

        }

    }

    modCount++;

    Entry e = tab[i];

    // e被連接在new Entry的後面

    tab[i] = new Entry<>(k, value, queue, h, e);

    if (++size >= threshold)

        resize(tab.length * 2);

    return null;

}

public V remove(Object key) {

    Object k = maskNull(key);

    int h = hash(k);

    Entry[] tab = getTable();

    int i = indexFor(h, tab.length);

    Entry prev = tab[i];

    Entry e = prev;

    while (e != null) {

        Entry next = e.next;

        if (h == e.hash && eq(k, e.get())) {

            modCount++;

            size–;

            if (prev == e)

                tab[i] = next;

            else

                prev.next = next;

            return e.value;

        }

        prev = e;

        e = next;

    }

    return null;

}

我們並沒有在put()函式中發現key被轉換成弱取用,這是怎麼回事?key只有在第一次被放入buckets陣列時才需要轉換成弱取用,也就是new Entry<>(k, value, queue, h, e),WeakHashMap的Entry實現其實就是WeakReference的子類。

/**

 * The entries in this hash table extend WeakReference, using its main ref

 * field as the key.

 */

private static class Entry extends WeakReferenceimplements Map.Entry {

    V value;

    final int hash;

    Entry next;

    /**

     * Creates new entry.

     */

    Entry(Object key, V value,

          ReferenceQueuequeue,

          int hash, Entry next) {

        super(key, queue);

        this.value = value;

        this.hash  = hash;

        this.next  = next;

    }

    @SuppressWarnings(“unchecked”)

    public K getKey() {

        return (K) WeakHashMap.unmaskNull(get());

    }

    public V getValue() {

        return value;

    }

    public V setValue(V newValue) {

        V oldValue = value;

        value = newValue;

        return oldValue;

    }

    public boolean equals(Object o) {

        if (!(o instanceof Map.Entry))

            return false;

        Map.Entry,?> e = (Map.Entry,?>)o;

        K k1 = getKey();

        Object k2 = e.getKey();

        if (k1 == k2 || (k1 != null && k1.equals(k2))) {

            V v1 = getValue();

            Object v2 = e.getValue();

            if (v1 == v2 || (v1 != null && v1.equals(v2)))

                return true;

        }

        return false;

    }

    public int hashCode() {

        K k = getKey();

        V v = getValue();

        return Objects.hashCode(k) ^ Objects.hashCode(v);

    }

    public String toString() {

        return getKey() + “=” + getValue();

    }

}

有關使用WeakReference的一個典型案例是ThreadLocal,感興趣的讀者可以參考我之前寫的博客聊一聊Spring中的執行緒安全性。

系列


【關於投稿】


如果大家有原創好文投稿,請直接給公號發送留言。


① 留言格式:
【投稿】+《 文章標題》+ 文章鏈接

② 示例:
【投稿】《不要自稱是程式員,我十多年的 IT 職場總結》:http://blog.jobbole.com/94148/

③ 最後請附上您的個人簡介哈~



看完本文有收穫?請轉發分享給更多人

關註「ImportNew」,提升Java技能

赞(0)

分享創造快樂