天天看點
傳回

Java8源碼-WeakHashMap

前段時間學習了HashMap，HashTable，LinkedHashMap，今天學習WeakHashMap，參考的JDK版本為1.8。

WeakHashMap和HashMap相似，也是哈希表的實作，以鍵值對的形式存儲資料，key和value都可以為null。不同的是WeakHashMap的鍵為“弱鍵”。什麼是“弱鍵”？弱鍵會對WeakHashMap産生什麼影響？“弱鍵”是如何實作的？本文會通過源碼來一一解答。

部分頂部注釋

Hash table based implementation of the Map interface, with weak keys. An entry in a WeakHashMap will automatically be removed when its key is no longer in ordinary use. More precisely, the presence of a mapping for a given key will not prevent the key from being discarded by the garbage collector, that is, made finalizable, finalized, and then reclaimed. When a key has been discarded its entry is effectively removed from the map, so this class behaves somewhat differently from other Map implementations.

WeakHashMap是Map接口的基于弱鍵的哈希表實作。當一個鍵不再正常使用，鍵對應的鍵值對将自動從WeakHashMap中删除。更嚴謹的說法是，鍵對應的鍵值對的存在并不阻止key被垃圾回收期回收，這就使該鍵稱為可被終止的，最終被終止，被回收。當某個鍵被回收，它對應的鍵值對也就被從map中有效地删除了。是以WeakHashMap類表現地有些和其他的Map接口實作不同。

Both null values and the null key are supported. This class has performance characteristics similar to those of the HashMap class, and has the same efficiency parameters of initial capacity and load factor.

WeakHashMap特性與HashMap相似，WeakHashMap同樣支援key和value為null，也有初始化容量和負載因子等參數。

Like most collection classes, this class is not synchronized. A synchronized WeakHashMap may be constructed using the Collections.synchronizedMap method.

像大多的集合類一樣，WeakHashMap是非同步的。可以使用Collections.synchronizedMap來構造同步的WeakHashMap。

下面還有很多，不翻譯了。

從以上的内容中我們可以總結出WeakHashMap的特點：

  1. WeakHashMap特性與HashMap相似，也是哈希表的實作，以鍵值對的形式存儲資料，同樣支援key和value為null，也有初始化容量和負載因子等參數，也是非同步的。
  2. WeakHashMap的鍵為“弱鍵”。

類層次結構圖

public class WeakHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>
  • WeakHashMap<K,V>：HashMap是以key-value形式存儲資料的
  • extends AbstractMap<K,V>：繼承了AbstractMap，大大減少了實作Map接口的工作量。
  • implements Map<K,V>：實作了Map。AbstractMap已經繼承了Map接口，為什麼WeakHashMap還要實作Map接口呢？仔細看過Java容器其他源碼的朋友會發現，不僅僅WeakHashMap這樣做，其他實作類也經常這樣做。網上的一些看法是這樣做可以直覺地表達出WeakHashMap實作了Map。如果大家有其他看法，歡迎留言。

說到直覺地展示出一個類的繼承實作結構，eclipse的類層次結構圖就可以實作這個功能。下圖是WeakHashMap類結構層次圖

Java8源碼-WeakHashMap

與HashMap相比

Java8源碼-WeakHashMap

我們發現WeakHashMap并沒有實作Cloneable和Serializable接口。

如何檢視類層次結構圖可以參考我寫過的一篇文章：

eclipse-檢視繼承層次圖/繼承實作層次圖

全局變量

靜态全局變量 

/**
 * 預設初始化容量，值為16
 * 必須是2的n次幂.
 */
private static final int DEFAULT_INITIAL_CAPACITY = ;

/**
 * 最大容量, 如果一個更大的值在構造函數總被指定，将被MAXIMUM_CAPACITY 替換.
 * 必須是2的倍數。最大容量為1<<30，即2的30次方。
 */
private static final int MAXIMUM_CAPACITY =  << ;

/**
 * 預設的負載因子。
 */
private static final float DEFAULT_LOAD_FACTOR = f;

與HashMap相比，缺少了TREEIFY_THRESHOLD 、UNTREEIFY_THRESHOLD、MIN_TREEIFY_CAPACITY三個靜态全局變量，而這三個靜态全局變量是針對紅黑樹與連結清單的轉換的。從這裡可以驗證WeakHashMap的資料結構為哈希表+連結清單。

普通全局變量 

/**
 * 存儲鍵值對的數組，一般是2的幂
 */
Entry<K,V>[] table;

/**
 * 鍵值對的實際個數
 */
private int size;

/**
 * 擴容的臨界值，通過capacity * load factor可以計算出來。超過這個值HashMap将進行擴容
 * @serial
 */
private int threshold;

/**
 * 負載因子
 */
private final float loadFactor;

/**
 * 會儲存被GC回收的“弱鍵”的隊列
 */
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

/**
 * 記錄HashMap被修改結構的次數。
 * 修改包括改變鍵值對的個數或者修改内部結構，比如rehash
 * 這個域被用作HashMap的疊代器的fail-fast機制中（參考ConcurrentModificationException）
 */
int modCount;

與HashMap相比，WeakHashMap缺少了

/**
 * 鍵值對緩存，它們的映射關系集合儲存在entrySet中。即使Key在外部修改導緻hashCode變化，緩存中還可以找到映射關系
 */
transient Set<Map.Entry<K,V>> entrySet;

多了queue這個成員。

構造方法

WeakHashMap有四個構造方法：

  1. 用指定的初始化容量initial capacity 和負載因子load factor構造一個空WeakHashMap。
  2. 使用指定的初始化容量initial capacity和預設負載因子DEFAULT_LOAD_FACTOR（0.75）構造一個空WeakHashMap。
  3. 使用指定的初始化容量（16）和預設負載因子DEFAULT_LOAD_FACTOR（0.75）構造一個空WeakHashMap。
  4. 使用指定map構造新的WeakHashMap。使用指定的初始化容量（16）和預設負載因子DEFAULT_LOAD_FACTOR（0.75）。

WeakHashMap( int initialCapacity, float loadFactor) 

@SuppressWarnings("unchecked")
private Entry<K,V>[] newTable(int n) {
    return (Entry<K,V>[]) new Entry<?,?>[n];
}

/**
 * 使用指定的初始化容量initial capacity 和負載因子load factor構造一個空WeakHashMap
 *
 * @param  initialCapacity 初始化容量
 * @param  loadFactor      負載因子
 * @throws IllegalArgumentException 如果指定的初始化容量為負數或者加載因子為非正數。
 */
public WeakHashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < )
        throw new IllegalArgumentException("Illegal Initial Capacity: "+
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;

    if (loadFactor <=  || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load factor: "+ loadFactor);
    int capacity = ;
    while (capacity < initialCapacity)
        capacity <<= ;
    table = newTable(capacity);
    this.loadFactor = loadFactor;
    threshold = (int)(capacity * loadFactor);
}

WeakHashMap( int initialCapacity) 

/**
 * 使用指定的初始化容量initial capacity和預設負載因子DEFAULT_LOAD_FACTOR（0.75）構造一個空WeakHashMap
 *
 * @param  initialCapacity 初始化容量
 * @throws IllegalArgumentException 如果指定的初始化容量為負數
 */
public WeakHashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

WeakHashMap() 

/**
 * 使用指定的初始化容量（16）和預設負載因子DEFAULT_LOAD_FACTOR（0.75）構造一個空WeakHashMap
 */
public WeakHashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

WeakHashMap( Map<? extends K, ? extends V> m) 

/**
使用指定Map m構造新的HashMap。使用指定的初始化容量（16）和預設負載因子DEFAULT_LOAD_FACTOR（0.75）
 * @param   m 指定的map
 * @throws  NullPointerException 如果指定的map是null
 * @since   1.3
 */
public WeakHashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + , DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    putAll(m);
}

私有方法 

/**
 * 當key為null時，NULL_KEY表示key
 */
private static final Object NULL_KEY = new Object();

maskNull( Object key) 

/**
 * 當key為null時，使用NULL_KEY表示key
 */
private static Object maskNull(Object key) {
    return (key == null) ? NULL_KEY : key;
}

unmaskNull( Object key) 

/**
 * 将key為NULL_KEY時，将key表示為null
 */
static Object unmaskNull(Object key) {
    return (key == NULL_KEY) ? null : key;
}

eq( Object x, Object y) 

/**
 * 判斷兩個非null對象是否相等
 */
private static boolean eq(Object x, Object y) {
    return x == y || x.equals(y);
}

hash( Object k) 

/**
 * 計算key的哈希值
 */
final int hash(Object k) {
    int h = k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> ) ^ (h >>> );
    return h ^ (h >>> ) ^ (h >>> );
}

indexFor( int h, int length) 

/**
 * 傳回哈希值對應的index
 */
private static int indexFor(int h, int length) {
    return h & (length-);
}

expungeStaleEntries()

文章開始提了一個問題：“弱鍵”是如何實作的？下面這個方法就是弱鍵實作的關鍵。

expungeStaleEntries方法會在引用隊列queue中尋找是否有被回收的entry，如果有則在table中找到其映射，并将value置為null，next指針也置為null。

一旦垃圾收集器把某個key回收了，那麼該key對應的entry就會被自動添加到這個隊列裡面，何時添加，如何添加，這些操作對WeakHashMap是透明的。

/**
 * 從哈希表中删除被回收的key的映射
 */
private void expungeStaleEntries() {
    //周遊隊列
    for (Object x; (x = queue.poll()) != null; ) {
        synchronized (queue) {
            @SuppressWarnings("unchecked")
                //由此可以看出隊列中的元素是Entry
                Entry<K,V> e = (Entry<K,V>) x;
            //擷取entry對應桶的index
            int i = indexFor(e.hash, table.length);

            //根據index擷取table中對應的桶
            Entry<K,V> prev = table[i];
            Entry<K,V> p = prev;
            //如果桶不為null，周遊桶中節點，找到并删除與e相等的節點
            while (p != null) {
                Entry<K,V> next = p.next;
                //這段沒看懂
                if (p == e) {
                    if (prev == e)
                        table[i] = next;
                    else
                        prev.next = next;
                    e.value = null; // 将e的value置為null
                    size--;//table大小減1
                    break;//跳出循環
                }
                //準備周遊下個節點
                prev = p;
                p = next;
            }
        }
    }
}

getTable() 

/**
 * 從哈希表中删除被回收的key的映射後傳回新的哈希表
 */
private Entry<K,V>[] getTable() {
    expungeStaleEntries();
    return table;
}

常用方法

size() 

/**
 * 從哈希表中删除被回收的key的映射後傳回新的哈希表的大小
 */
public int size() {
    if (size == )
        return ;
    expungeStaleEntries();
    return size;
}

isEmpty() 

/**
 * 判斷哈希表大小是否為0
 */
public boolean isEmpty() {
    return size() == ;
}

get( Object key) 

/**
 * 傳回指定的key對應的value，如果value為null，則傳回null
 *
 * @see #put(Object, Object)
 */
public V get(Object key) {
    Object k = maskNull(key);
    int h = hash(k);
    Entry<K,V>[] tab = getTable();
    //擷取桶在table中的index
    int index = indexFor(h, tab.length);
    //擷取桶
    Entry<K,V> e = tab[index];
    //周遊桶中節點
    while (e != null) {
        if (e.hash == h && eq(k, e.get()))
            return e.value;
        e = e.next;
    }
    return null;
}

從周遊桶中節點的方式中可以看出，桶中節點為連結清單，并沒有紅黑樹。

containsKey( Object key) 

/**
 * 如果map中含有key為指定參數key的鍵值對，傳回true
 * 
 * @param   key   指定參數key
 * @return 如果map中含有key為指定參數key的鍵值對，傳回true
 */
public boolean containsKey(Object key) {
    return getEntry(key) != null;
}

 /**
 * 根據key擷取對應的節點
 * 
 * @param key 指定參數key
 * @return 傳回node，如果沒有則傳回null
 */
Entry<K,V> getEntry(Object key) {
    Object k = maskNull(key);
    int h = hash(k);
    Entry<K,V>[] tab = getTable();
    int index = indexFor(h, tab.length);
    Entry<K,V> e = tab[index];
    while (e != null && !(e.hash == h && eq(k, e.get())))
        e = e.next;
    return e;
}

put( K key, V value) 

/**
 * 将指定參數key和指定參數value插入map中，如果key已經存在，那就替換key對應的value
 *
 * @param key 指定key
 * @param value 指定value
 * @return 如果value被替換，則傳回舊的value，否則傳回null。當然，可能key對應的value就是null。
 */
public V put(K key, V value) {
    Object k = maskNull(key);
    int h = hash(k);
    Entry<K,V>[] tab = getTable();
    int i = indexFor(h, tab.length);

    for (Entry<K,V> 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<K,V> e = tab[i];
    tab[i] = new Entry<>(k, value, queue, h, e);
    if (++size >= threshold)
        resize(tab.length * );
    return null;
}

resize( int newCapacity) 

/**
 * 
 * 擴容，并将舊的map中的鍵值對插入到新的table中。當map大小超過threshold時，方法會自動調用。
 * 如果現在的容量為MAXIMUM_CAPACITY，方法不會擴容，但會設定threshold為Integer.MAX_VALUE。
 * 
 * @param newCapacity 新的容量，大小為2的幂。必須大于現在的容量，除非現在的容量為MAXIMUM_CAPACITY 。
 */
void resize(int newCapacity) {
    Entry<K,V>[] oldTable = getTable();
    //記錄table大小
    int oldCapacity = oldTable.length;
    //如果table大小為MAXIMUM_CAPACITY，就将threshold調整為Integer.MAX_VALUE，終止執行
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    // 建立newTable 
    Entry<K,V>[] newTable = newTable(newCapacity);
    //将舊的table中的鍵值對複制到newTable中
    transfer(oldTable, newTable);
    //使用newTable替換舊table
    table = newTable;

    /*
     * If ignoring null elements and processing ref queue caused massive
     * shrinkage, then restore old table.  This should be rare, but avoids
     * unbounded expansion of garbage-filled tables.
     */
    //如果table大小大于等于threshold / 2
    if (size >= threshold / ) {
        //重新計算threshold
        threshold = (int)(newCapacity * loadFactor);
    } else {//如果table小于threshold / 2
        //沒看懂為什麼要這麼做
        expungeStaleEntries();
        transfer(newTable, oldTable);
        table = oldTable;
    }
}

transfer( Entry<K,V>[] src, Entry<K,V>[] dest) 

/** Transfers all entries from src to dest tables */
/**
 * 将src的所有鍵值對複制到dest中。
 */
private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
    for (int j = ; j < src.length; ++j) {
        Entry<K,V> e = src[j];
        src[j] = null;
        while (e != null) {
            Entry<K,V> next = e.next;
            Object key = e.get();
            if (key == null) {
                e.next = null;  // Help GC
                e.value = null; //  "   "
                size--;
            } else {
                int i = indexFor(e.hash, dest.length);
                e.next = dest[i];
                dest[i] = e;
            }
            e = next;
        }
    }
}

putAll(Map<? extends K, ? extends V> m) 

/**
 * 複制參數m中所有的鍵值對到weakHashMap中
 *
 * @param m the map
 * @param evict 初始化map時使用false，否則使用truenull.
 */
public void putAll(Map<? extends K, ? extends V> m) {
    int numKeysToBeAdded = m.size();
    if (numKeysToBeAdded == )
        return;

    /*
     * Expand the map if the map if the number of mappings to be added
     * is greater than or equal to threshold.  This is conservative; the
     * obvious condition is (m.size() + size) >= threshold, but this
     * condition could result in a map with twice the appropriate capacity,
     * if the keys to be added overlap with the keys already in this map.
     * By using the conservative calculation, we subject ourself
     * to at most one extra resize.
     */
    if (numKeysToBeAdded > threshold) {
        int targetCapacity = (int)(numKeysToBeAdded / loadFactor + );
        if (targetCapacity > MAXIMUM_CAPACITY)
            targetCapacity = MAXIMUM_CAPACITY;
        int newCapacity = table.length;
        while (newCapacity < targetCapacity)
            newCapacity <<= ;
        if (newCapacity > table.length)
            resize(newCapacity);
    }

    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
        put(e.getKey(), e.getValue());
}

remove( Object key) 

/**
 * 删除weakHashMap中key為參數key的鍵值對
 *
 * @param  key 參數key
 * @return 如果沒有對應的鍵值對，傳回null，否則傳回對應的value。
 */
public V remove(Object key) {
    Object k = maskNull(key);
    int h = hash(k);
    Entry<K,V>[] tab = getTable();
    int i = indexFor(h, tab.length);
    Entry<K,V> prev = tab[i];
    Entry<K,V> e = prev;

    while (e != null) {
        Entry<K,V> 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;
}

removeMapping( Object o) 

/**
 * 删除weakHashMap中為值為o的entry
 */
boolean removeMapping(Object o) {
    if (!(o instanceof Map.Entry))
        return false;
    Entry<K,V>[] tab = getTable();
    Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
    Object k = maskNull(entry.getKey());
    int h = hash(k);
    int i = indexFor(h, tab.length);
    Entry<K,V> prev = tab[i];
    Entry<K,V> e = prev;

    while (e != null) {
        Entry<K,V> next = e.next;
        if (h == e.hash && e.equals(entry)) {
            modCount++;
            size--;
            if (prev == e)
                tab[i] = next;
            else
                prev.next = next;
            return true;
        }
        prev = e;
        e = next;
    }

    return false;
}

clear() 

/**
 * 删除weakHashMap中所有的鍵值對
 */
public void clear() {
    // clear out ref queue. We don't need to expunge entries
    // since table is getting cleared.
    while (queue.poll() != null)
        ;

    modCount++;
    Arrays.fill(table, null);
    size = ;

    // Allocation of array may have caused GC, which may have caused
    // additional entries to go stale.  Removing these entries from the
    // reference queue will make them eligible for reclamation.
    while (queue.poll() != null)
        ;
}

containsValue( Object value) 

/**
 * 如果weakHashMap中的鍵值對有一對或多對的value為參數value，傳回true
 *
 * @param value 參數value
 * @return 如果weakHashMap中的鍵值對有一對或多對的value為參數value，傳回true
 */
public boolean containsValue(Object value) {
    if (value==null)
        return containsNullValue();

    Entry<K,V>[] tab = getTable();
    for (int i = tab.length; i-- > ;)
        for (Entry<K,V> e = tab[i]; e != null; e = e.next)
            if (value.equals(e.value))
                return true;
    return false;
}

containsNullValue() 

/**
 * 如果weakHashMap中的鍵值對有一對或多對的value為null，傳回true
 *
 * @return 如果weakHashMap中的鍵值對有一對或多對的value為null，傳回true
 */
private boolean containsNullValue() {
    Entry<K,V>[] tab = getTable();
    for (int i = tab.length; i-- > ;)
        for (Entry<K,V> e = tab[i]; e != null; e = e.next)
            if (e.value==null)
                return true;
    return false;
}

總結

WeakHashMap與HashMap比較

不同點

不同點 HashMap WeakHashMap
資料結構 數組+連結清單+紅黑樹 數組+連結清單+隊列
鍵 強引用 弱引用
是否實作Cloneable和Serializable 是 否

相同點

  • 都是基于哈希表的實作。
  • 都以鍵值對的形式存儲資料。
  • 都繼承了AbstractMap，實作了Map接口。
  • 都支援key和value為null。
  • 都是非同步的。
  • 都是無序的。

什麼是“弱鍵”？

先了解下什麼是“弱引用”

弱引用， 在進行垃圾回收時，無論目前記憶體是否足夠，都會回收掉隻被弱引用關聯着的對象，是以其生命周期隻存在于一個垃圾回收周期内。

WeakHashMap的鍵就是弱引用。當某個鍵不再正常使用時，便自動移除其條目。

“弱鍵”會對WeakHashMap産生什麼影響？

當一個鍵不再正常使用，鍵對應的鍵值對将自動從WeakHashMap中删除。鍵對應的鍵值對的存在并不阻止key被垃圾回收期回收，這就使該鍵稱為可被終止的，最終被終止，被回收。當某個鍵被回收，它對應的鍵值對也就被從map中有效地删除了。是以WeakHashMap類表現地有些和其他的Map接口實作不同。

“弱鍵”是如何實作的？

WeakHashMap 中的Entry對象繼承了 WeakReference，它把key封裝成一個弱引用對象。

WeakHashMap .Entry

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
    V value;
    final int hash;
    Entry<K,V> next;

    /**
     * Creates new entry.
     */
    Entry(Object key, V value,
          ReferenceQueue<Object> queue,
          int hash, Entry<K,V> next) {
        super(key, queue);
        this.value = value;
        this.hash  = hash;
        this.next  = next;
    }
    ...
    ...
    ...

HashMap.Node

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    ...
    ...
    ...

對比從上面WeakHashMap和HashMap節點類的實作可以看出，WeakHashMap把key封裝成一個弱引用對象。

想深入了解WeakHashMap的弱鍵，那麼就必須先了解 ReferenceQueue 和 WeakReference。文章篇幅有限，不多做講解，有興趣的朋友可以自己研究。

本文已收錄于Java8容器源碼劄記專欄。

Java8容器源碼劄記 weakhashma hashmap JAVA8 源碼 jdk8
上一篇: Jdk8 HashMap源碼閱讀
下一篇: KMP基本思路

繼續閱讀