Java中的WeakHashMap源碼分析

更新時(shí)間：2023年09月06日 09:24:49 作者：weixin_30692143

這篇文章主要介紹了Java中的WeakHashMap源碼分析,WeakHashMap可能平時(shí)使用的頻率并不高,但是你可能聽過(guò)WeakHashMap會(huì)進(jìn)行自動(dòng)回收吧,下面就對(duì)其原理進(jìn)行分析,需要的朋友可以參考下

1.WeakHashMap介紹

WeakHashMap是一種弱引用的map，底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組+鏈表，內(nèi)部的key存儲(chǔ)為弱引用，在GC時(shí)如果key不存在強(qiáng)引用的情況下會(huì)被回收掉，而對(duì)于value的回收會(huì)在下一次操作map時(shí)回收掉，所以WeakHashMap適合緩存處理。

1 java.lang.Object
2        java.util.AbstractMap<K, V>
3              java.util.WeakHashMap<K, V>
4 
5 public class WeakHashMap<K,V>
6     extends AbstractMap<K,V>
7     implements Map<K,V> {}

從WeakHashMap的繼承關(guān)系上來(lái)看，可知其繼承AbstractMap，實(shí)現(xiàn)了Map接口。

其底層數(shù)據(jù)結(jié)構(gòu)是Entry數(shù)組，Entry的數(shù)據(jù)結(jié)構(gòu)如下：

從源碼上可知，Entry的內(nèi)部并沒有存儲(chǔ)key的值，而是通過(guò)調(diào)用父類的構(gòu)造方法，傳入key和ReferenceQueue，最終key和queue會(huì)關(guān)聯(lián)到Reference中

這里是GC時(shí)，清清除key的關(guān)鍵，這里大致看下Reference的源碼：

private static class ReferenceHandler extends Thread {
        private static void ensureClassInitialized(Class<?> clazz) {
            try {
                Class.forName(clazz.getName(), true, clazz.getClassLoader());
            } catch (ClassNotFoundException e) {
                throw (Error) new NoClassDefFoundError(e.getMessage()).initCause(e);
            }
        }
        static {
            // pre-load and initialize InterruptedException and Cleaner classes
            // so that we don't get into trouble later in the run loop if there's
            // memory shortage while loading/initializing them lazily.
            ensureClassInitialized(InterruptedException.class);
            ensureClassInitialized(Cleaner.class);
        }
        ReferenceHandler(ThreadGroup g, String name) {
            super(g, name);
        }
        public void run() {
            // 注意這里為一個(gè)死循環(huán)
            while (true) {
                tryHandlePending(true);
            }
        }
    }
    static boolean tryHandlePending(boolean waitForNotify) {
        Reference<Object> r;
        Cleaner c;
        try {
            synchronized (lock) {
                if (pending != null) {
                    r = pending;
                    // 'instanceof' might throw OutOfMemoryError sometimes
                    // so do this before un-linking 'r' from the 'pending' chain...
                    c = r instanceof Cleaner ? (Cleaner) r : null;
                    // unlink 'r' from 'pending' chain
                    pending = r.discovered;
                    r.discovered = null;
                } else {
                    // The waiting on the lock may cause an OutOfMemoryError
                    // because it may try to allocate exception objects.
                    if (waitForNotify) {
                        lock.wait();
                    }
                    // retry if waited
                    return waitForNotify;
                }
            }
        } catch (OutOfMemoryError x) {
            // Give other threads CPU time so they hopefully drop some live references
            // and GC reclaims some space.
            // Also prevent CPU intensive spinning in case 'r instanceof Cleaner' above
            // persistently throws OOME for some time...
            Thread.yield();
            // retry
            return true;
        } catch (InterruptedException x) {
            // retry
            return true;
        }
        // Fast path for cleaners
        if (c != null) {
            c.clean();
            return true;
        }
        // 加入對(duì)列
        ReferenceQueue<? super Object> q = r.queue;
        if (q != ReferenceQueue.NULL) q.enqueue(r);
        return true;
    }
    static {
        ThreadGroup tg = Thread.currentThread().getThreadGroup();
        for (ThreadGroup tgn = tg;
             tgn != null;
             tg = tgn, tgn = tg.getParent());
        // 創(chuàng)建handler
        Thread handler = new ReferenceHandler(tg, "Reference Handler");
        /* If there were a special system-only priority greater than
         * MAX_PRIORITY, it would be used here
         */
        // 線程優(yōu)先級(jí)最大
        handler.setPriority(Thread.MAX_PRIORITY);
        // 設(shè)置為守護(hù)線程
        handler.setDaemon(true);
        handler.start();
        // provide access in SharedSecrets
        SharedSecrets.setJavaLangRefAccess(new JavaLangRefAccess() {
            @Override
            public boolean tryHandlePendingReference() {
                return tryHandlePending(false);
            }
        });
    }

通過(guò)查看Reference源碼可知，在實(shí)例化時(shí)會(huì)創(chuàng)建一個(gè)守護(hù)線程，然后不斷循環(huán)將GC時(shí)的Entry入隊(duì)，關(guān)于如何清除value值的下面會(huì)進(jìn)行分析。

2.具體源碼分析

put操作：

public V put(K key, V value) {
        // 確定key值，允許key為null
        Object k = maskNull(key);
        // 獲取器hash值
        int h = hash(k);
        // 獲取tab
        Entry<K,V>[] tab = getTable();
        // 確定在tab中的位置 簡(jiǎn)單的&操作
        int i = indexFor(h, tab.length);
        // 遍歷，是否要進(jìn)行覆蓋操作
        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;
            }
        }
        // 修改次數(shù)自增
        modCount++;
        // 取出i上的元素
        Entry<K,V> e = tab[i];
        // 構(gòu)建鏈表，新元素在鏈表頭
        tab[i] = new Entry<>(k, value, queue, h, e);
        // 檢查是否需要擴(kuò)容
        if (++size >= threshold)
            resize(tab.length * 2);
        return null;
    }

分析：

WeakHashMap的put操作與HashMap相似，都會(huì)進(jìn)行覆蓋操作(相同key)，但是注意插入新節(jié)點(diǎn)是放在鏈表頭。

上述代碼中還要一個(gè)關(guān)鍵的函數(shù)getTable，后面會(huì)對(duì)其進(jìn)行具體分析，先記下。

get操作：

public V get(Object key) {
        // 確定key
        Object k = maskNull(key);
        // 計(jì)算其hashCode
        int h = hash(k);
        Entry<K,V>[] tab = getTable();
        int index = indexFor(h, tab.length);
        // 獲取對(duì)應(yīng)位置上的元素
        Entry<K,V> e = tab[index];
        while (e != null) {
            // 如果hashCode相同，并且key也相同，則返回，否則繼續(xù)循環(huán)
            if (e.hash == h && eq(k, e.get()))
                return e.value;
            e = e.next;
        }
        // 未找到，則返回null
        return null;
    }

分析：

get操作邏輯簡(jiǎn)單，根據(jù)key遍歷對(duì)應(yīng)元素即可。

remove操作：

public V remove(Object key) {
        Object k = maskNull(key);
        int h = hash(k);
        Entry<K,V>[] tab = getTable();
        int i = indexFor(h, tab.length);
        // 數(shù)組上第一個(gè)元素
        Entry<K,V> prev = tab[i];
        Entry<K,V> e = prev;
        // 循環(huán)
        while (e != null) {
            Entry<K,V> next = e.next;
            // 如果hash值相同，并且key一樣，則進(jìn)行移除操作
            if (h == e.hash && eq(k, e.get())) {
                // 修改次數(shù)自增
                modCount++;
                // 元素個(gè)數(shù)自減
                size--;
                // 如果就是頭元素，則直接移除即可
                if (prev == e)
                    tab[i] = next;
                else
                    // 否則將前驅(qū)元素的next賦值為next，則將e移除
                    prev.next = next;
                return e.value;
            }
            // 更新prev和e，繼續(xù)循環(huán)
            prev = e;
            e = next;
        }
        return null;
    }

分析：

移除元素操作的整體邏輯并不復(fù)雜，就是進(jìn)行鏈表的常規(guī)操作，注意元素是鏈表頭時(shí)的特別處理，通過(guò)上述注釋，理解應(yīng)該不困難。

resize操作（WeakHashMap的擴(kuò)容操作）

void resize(int newCapacity) {
    Entry<K,V>[] oldTable = getTable();
    // 原數(shù)組長(zhǎng)度
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    // 創(chuàng)建新的數(shù)組
    Entry<K,V>[] newTable = newTable(newCapacity);
    // 數(shù)據(jù)轉(zhuǎn)移
    transfer(oldTable, newTable);
    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.
     */
    // 確定擴(kuò)容閾值
    if (size >= threshold / 2) {
        threshold = (int)(newCapacity * loadFactor);
    } else {
        // 清除被GC的value
        expungeStaleEntries();
        // 數(shù)組轉(zhuǎn)移
        transfer(newTable, oldTable);
        table = oldTable;
    }
}
 private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
    // 遍歷原數(shù)組
    for (int j = 0; j < src.length; ++j) {
        // 取出元素
        Entry<K,V> e = src[j];
        src[j] = null;
        // 鏈?zhǔn)秸以?
        while (e != null) {
            Entry<K,V> next = e.next;
            Object key = e.get();
            // key被回收的情況
            if (key == null) {
                e.next = null;  // Help GC
                e.value = null; //  "   "
                size--;
            } else {
                // 確定在新數(shù)組的位置
                int i = indexFor(e.hash, dest.length);
                // 插入元素 注意這里為頭插法，會(huì)倒序
                e.next = dest[i];
                dest[i] = e;
            }
            e = next;
        }
    }
}

分析：

WeakHashMap的擴(kuò)容函數(shù)中有點(diǎn)特別，因?yàn)閗ey可能被GC掉，所以在擴(kuò)容時(shí)也許要考慮這種情況，其他并沒有什么特別的，通過(guò)以上注釋理解應(yīng)該不難。

在以上源碼分析中多次出現(xiàn)一個(gè)函數(shù)：expungeStaleEntries

private void expungeStaleEntries() {
        // 從隊(duì)列中取出被GC的Entry
        for (Object x; (x = queue.poll()) != null; ) {
            synchronized (queue) {
                @SuppressWarnings("unchecked")
                    Entry<K,V> e = (Entry<K,V>) x;
                // 確定元素在隊(duì)列中的位置
                int i = indexFor(e.hash, table.length);
                // 取出數(shù)組中的第一個(gè)元素 prev
                Entry<K,V> prev = table[i];
                Entry<K,V> p = prev;
                // 循環(huán)
                while (p != null) {
                    Entry<K,V> next = p.next;
                    // 找到
                    if (p == e) {
                        // 判斷是否是鏈表頭元素 第一次時(shí)
                        if (prev == e)
                            // 將next直接掛在i位置
                            table[i] = next;
                        else
                            // 進(jìn)行截?cái)?
                            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
                    prev = p;
                    p = next;
                }
            }
        }
    }

分析：

該函數(shù)的主要作用就是清除Entry的value，該Entry是在GC清除key的過(guò)程中入隊(duì)的。函數(shù)的邏輯并不復(fù)雜，通過(guò)上述注釋理解應(yīng)該不難。

接下來(lái)看下該函數(shù)會(huì)在什么時(shí)候調(diào)用：

從以上調(diào)用鏈可知，在獲取size（獲取WeakHashMap的元素個(gè)數(shù)）和resize（擴(kuò)容時(shí)）會(huì)調(diào)用該函數(shù)清除被GC的key對(duì)應(yīng)的value值。但還有一個(gè)getTable函數(shù)也會(huì)調(diào)用該函數(shù)：

從以上調(diào)用鏈可知，在get/put等操作中都會(huì)調(diào)用expungeStaleEntries函數(shù)進(jìn)GC后的收尾工作，其實(shí)WeakHashMap清除無(wú)強(qiáng)引用的核心也就是該函數(shù)了，因此理解該函數(shù)的作用是非常重要的。