java8 WeakHashMap接口實作源碼解析

一、類繼承關系

二、概述

    WeakHashMap是基于基于弱引用key和哈希表的Map接口實作類，通常用于實作對記憶體敏感的本地緩存。使用WeakHashMap時要求key不能被其他常駐記憶體的執行個體（如WeakHashMap中的value）引用，如果必須引用，則将引用方包裝成WeakReference，如：m.put(key, new WeakReference(value))。當隻有WeakHashMap執行個體保留了對目标key的引用時，下一次垃圾回收可能将該key從記憶體中删除掉，注意key删除了但是key對應的WeakReference執行個體還在WeakHashMap中。如果被删除了，則下一次調用WeakHashMap的某個方法時，WeakHashMap會首先将被垃圾回收掉的key對應的WeakReference執行個體及其value從WeakHashMap中删除。使用WeakHashMap時需要程式做好某個key突然沒有的應對措施，key的删除是垃圾回收器決定的，對應用程式是不可控不可預知的。參考如下用例：

@Test
    public void test() throws Exception {
        ReferenceQueue queue = new ReferenceQueue();
        WeakReference reference = new WeakReference(new Object(), queue);
        System.out.println(reference);
        System.gc();
        Reference reference1 = queue.remove();
        System.out.println(reference1);
        System.out.println(reference1.get());//為null
    }

    @Test
    public void test2() throws Exception {
        Map<User,String> map=new WeakHashMap<>();
        map.put(new User("shl",12),"shl");
        map.put(new User("shl2",12),"shl2");
        System.out.println(map.size());
        //調用gc()方法時不保證垃圾回收器一直執行垃圾回收
        System.gc();
        System.gc();
        System.gc();
        System.out.println(map.size());
    }
           

三、源碼實作

1、全局變量定義

/**
     * 預設初始容量
     */
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * 最大容量
     */
    private static final int MAXIMUM_CAPACITY = 1 << 30;

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

    /**
     * 哈希表
     */
    Entry<K,V>[] table;

    /**
     * 儲存的元素個數
     */
    private int size;

    /**
     * 執行擴容的門檻值 (capacity * load factor).
     */
    private int threshold;

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

    /**
     * 儲存弱引用的隊列，當垃圾回收器回收了某個弱引用對應的對象時，會将該弱引用放入隊列中
     */
    private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
    /**
     * 代表為null的key
     */
    private static final Object NULL_KEY = new Object();

    /**
     * 記錄修改次數
     */
    int modCount;
           

2、構造方法

public WeakHashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Initial Capacity: "+
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;

        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load factor: "+
                                               loadFactor);
        int capacity = 1;
        //計算大于initialCapacity的最小的2的整數次方,跟HashMap中的實作相比，運算的次數更多
        while (capacity < initialCapacity)
            capacity <<= 1;
        table = newTable(capacity);
        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
    }

    
    public WeakHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

   
    public WeakHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    
    public WeakHashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                DEFAULT_INITIAL_CAPACITY),
             DEFAULT_LOAD_FACTOR);
        putAll(m);
    }
           

3、存儲key/value的資料結構

/**
     * Entry繼承自WeakReference
     */
    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) {
            //此處自動将key包裝成WeakReference
            super(key, queue);
            this.value = value;
            this.hash  = hash;
            this.next  = next;
        }

        //此處擷取key是從WeakReference中擷取key的
        @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();
        }
    }
           

4、公用方法

@SuppressWarnings("unchecked")
    //傳回指定容量的哈希表
    private Entry<K,V>[] newTable(int n) {
        return (Entry<K,V>[]) new Entry<?,?>[n];
    }

    /**
     * 插入時對key做預處理，如果key為null轉換為NULL_KEY
     */
    private static Object maskNull(Object key) {
        return (key == null) ? NULL_KEY : key;
    }

    /**
     * 傳回key時對key做預處理，如果key為NULL_KEY轉換為null
     */
    static Object unmaskNull(Object key) {
        return (key == NULL_KEY) ? null : key;
    }

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

    /**
     * 讓低位位元組參與運算，減少hash碰撞,相比HashMap運算次數更多
     */
    final int hash(Object k) {
        int h = k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    /**
     * 傳回哈希表中索引
     */
    private static int indexFor(int h, int length) {
        return h & (length-1);
    }

    /**
     * 從哈希表中删除弱引用隊列儲存的元素，弱引用隊列中儲存的元素是已經被垃圾回收器給回收的元素
     * 注意Entry是繼承自WeakReference對象，此時從引用隊列擷取的Entry執行個體中儲存的key已經被垃圾回收器會回收了
     */
    private void expungeStaleEntries() {
        //不斷的從弱引用隊列中拉取元素
        for (Object x; (x = queue.poll()) != null; ) {
            synchronized (queue) {
                @SuppressWarnings("unchecked")
                    Entry<K,V> e = (Entry<K,V>) x;
                //找到被删除元素所屬的哈希索引
                int i = indexFor(e.hash, table.length);
                //擷取該索引下哈希桶的頭元素
                //prev表示前一個元素
                Entry<K,V> prev = table[i];
                //p表示目前周遊的元素
                Entry<K,V> p = prev;
                //周遊哈希桶的單向連結清單
                while (p != null) {
                    Entry<K,V> next = p.next;
                    //找到目标元素
                    if (p == e) {
                        //p和prev隻有在都指向頭元素時才相等，即待删除元素是頭元素，将下一個元素置為頭元素
                        if (prev == e)
                            table[i] = next;
                        else
                            //如果不是頭元素，将前一個元素和下一個元素關聯起來
                            prev.next = next;
                        //e.key已經為null，将value進一步置為null，進而被垃圾回收器回收
                        e.value = null;
                        //元素被移除，size減1，跳出循環
                        size--;
                        break;
                    }
                    //沒找到key，pre置成目前元素，p置成下一個元素，繼續周遊
                    prev = p;
                    p = next;
                }
            }
        }
    }

    
    private Entry<K,V>[] getTable() {
        expungeStaleEntries();
        return table;
    }
           

5、元素插入

public V put(K key, V value) {
        Object k = maskNull(key);
        int h = hash(k);
        //getTable方法會自動清除被垃圾回收掉的元素
        Entry<K,V>[] tab = getTable();
        //找到該元素所屬的hash桶
        int i = indexFor(h, tab.length);

        //周遊哈希桶中的單向連結清單
        for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
            //存在key相同的，覆寫原值
            if (h == e.hash && eq(k, e.get())) {
                V oldValue = e.value;
                if (value != oldValue)
                    e.value = value;
                return oldValue;
            }
        }
        //沒有相同key的元素
        modCount++;
        //将新元素插入到單向連結清單的頭部
        Entry<K,V> e = tab[i];
        tab[i] = new Entry<>(k, value, queue, h, e);
        //如果目前元素個數超過門檻值則執行擴容
        if (++size >= threshold)
            resize(tab.length * 2);
        return null;
    }
           

6、key/value查找

public boolean containsKey(Object key) {
        return getEntry(key) != 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;
    }

    public boolean containsValue(Object value) {
        if (value==null)
            return containsNullValue();

        Entry<K,V>[] tab = getTable();
        //周遊每個哈希桶
        for (int i = tab.length; i-- > 0;)
            //周遊哈希桶中的單向連結清單
            for (Entry<K,V> e = tab[i]; e != null; e = e.next)
                if (value.equals(e.value))
                    return true;
        return false;
    }
           

7、擴容

void resize(int newCapacity) {
        //清除已被回收元素
        Entry<K,V>[] oldTable = getTable();
        int oldCapacity = oldTable.length;
        //達到最大容量後就無法擴容了，提高門檻值避免二次觸發
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry<K,V>[] newTable = newTable(newCapacity);
        transfer(oldTable, newTable);
        table = newTable;

        /*
         * 因為存在垃圾回收的情況，原來size是大于threshold的，transfer執行時會将被回收的元素删除掉，導緻size有可能小于
         * threshold的二分之一
         */
        if (size >= threshold / 2) {
            //size依然較大，更新threshold值
            threshold = (int)(newCapacity * loadFactor);
        } else {
            //垃圾回收器回收了大部分元素，此時不需要擴容了，将newTable中的元素轉移到oldTable中
            //之前的transfer沒有删除元素，此處的expungeStaleEntries方法會删除元素
            expungeStaleEntries();
            transfer(newTable, oldTable);
            table = oldTable;
        }
    }

    private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
        //周遊原來的哈希桶
        for (int j = 0; 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();
                //因為WeakHashMap對null的key轉換成常量了，當key為null時表示該元素被垃圾回收期回收掉了
                if (key == null) {
                    //此處将該元素儲存的引用都置成null，便于垃圾回收，注意此時沒有将上一個元素對該元素的引用删除掉，即該元素實際還在Map中
                    e.next = null;
                    e.value = null;
                    size--;
                } else {
                    //按照擴容後的哈希桶重新hash，重建立立單向連結清單
                    int i = indexFor(e.hash, dest.length);
                    e.next = dest[i];
                    dest[i] = e;
                }
                e = next;
            }
        }
    }
           

8、元素删除

//與元素查找邏輯相同
public V remove(Object key) {
        Object k = maskNull(key);
        int h = hash(k);
        //清除已被回收元素
        Entry<K,V>[] tab = getTable();
        //找到key所屬的哈希桶
        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;
            //找到目标key
            if (h == e.hash && eq(k, e.get())) {
                modCount++;
                size--;
                if (prev == e)
                    //如果目标key是哈希桶的頭元素，将頭元素置成下一個元素
                    tab[i] = next;
                else
                    //不是頭元素，建立前一個元素和下一個元素的關聯
                    prev.next = next;
                //傳回key原來的value
                return e.value;
            }
            //沒有找到目标key，繼續往下周遊
            prev = e;
            e = next;
        }

        return null;
    }
           

 9、元素周遊，Iterator接口實作

//周遊邏輯跟HashMap基本一緻，隻是為了适應WeakHashMap增加了兩個用于儲存下一個元素key和目前元素key的強引用執行個體
    private abstract class HashIterator<T> implements Iterator<T> {
        private int index;
        private Entry<K,V> entry;
        private Entry<K,V> lastReturned;
        private int expectedModCount = modCount;

        /**
         * 對下一個key的強引用執行個體，避免在周遊時被垃圾回收掉
         */
        private Object nextKey;

        /**
         * 目前key的強引用執行個體，避免在周遊時被垃圾回收掉
         */
        private Object currentKey;

        HashIterator() {
            index = isEmpty() ? 0 : table.length;
        }

        public boolean hasNext() {
            Entry<K,V>[] t = table;
            //nextKey未初始化或者執行了nextEntry方法
            while (nextKey == null) {
                Entry<K,V> e = entry;
                int i = index;
                //找到第一個不為空的哈希桶
                while (e == null && i > 0)
                    e = t[--i];
                //目前元素
                entry = e;
                //目前哈希索引
                index = i;
                //所有哈希桶都是空的
                if (e == null) {
                    currentKey = null;
                    return false;
                }
                //将目前元素的key指派給一個強引用執行個體，避免被回收
                nextKey = e.get(); // hold on to key in strong ref
                //如果已經被回收了，則将目前元素置成下一個元素，下一次循環中執行nextKey = e.get()，然後跳出循環
                if (nextKey == null)
                    entry = entry.next;
            }
            return true;
        }

        protected Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (nextKey == null && !hasNext())
                throw new NoSuchElementException();

            lastReturned = entry;
            entry = entry.next;
            currentKey = nextKey;
            //nextKey置為null，觸發下一次執行hasNext()方法時查找元素的邏輯
            nextKey = null;
            return lastReturned;
        }

        public void remove() {
            if (lastReturned == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            WeakHashMap.this.remove(currentKey);
            expectedModCount = modCount;
            lastReturned = null;
            currentKey = null;
        }

    }

    private class ValueIterator extends HashIterator<V> {
        public V next() {
            return nextEntry().value;
        }
    }

    private class KeyIterator extends HashIterator<K> {
        public K next() {
            return nextEntry().getKey();
        }
    }

    private class EntryIterator extends HashIterator<Map.Entry<K,V>> {
        public Map.Entry<K,V> next() {
            return nextEntry();
        }
    }