2019-06-28

WeakHashMap 源码解读

缘起

【1】中我们介绍了弱引用的一种应用场景——ThreadLocal. 当时是为了解决内存泄漏问题而必须要使得ThreadLocalMap的key（ThreadLocal类型）是弱引用. 但是带来的问题就是ThreadLocalMap的value的内存泄漏问题. 解决办法就是在get、set的时候顺便清理一下key已经为null的Entry. 而本文介绍弱引用另一种应用场景——WeakHashMap. 它的key同样是弱引用. 对弱引用不清楚的同学可以参考【2】

分析

了解一个事物之前，我们先说说它的应用背景. 我们知道如果往HashMap中放置一个<K,V>, 则时候我们觉得K可以不要了，令K=null，可以让K被回收吗? 显然是不会的，因为HashMap（确切讲是HashMap的Node<K,V>[] table属性）对其构成强引用. 与业务相违背. 所以如果了解了【1】的话，就知道处理的思路了——让K成为弱引用，而不是强引用. 但是与ThreadLocal面临的问题一样. 与之伴随的问题就是V的内存泄漏问题. ThreadLocal的解决方法是在set、get、remove的时候顺便清除这种K为null，V不为null的Entry（这种Entry在【1】叫做脏项）.那么WeakHashMap是怎么解决这个问题的呢?

咳咳咳~ 好像这与WeakHashMap的应用场景还是无关哈~ 下面正儿八经的应用场景出现了——在tomcat的源码中我们发现了WeakHashMap的身影

package org.apache.tomcat.util.collections;

import java.util.Map;
import java.util.WeakHashMap;
import java.util.concurrent.ConcurrentHashMap;

public final class ConcurrentCache<K,V> {

    private final int size;

    private final Map<K,V> eden;

    private final Map<K,V> longterm;

    public ConcurrentCache(int size) {
        this.size = size;
        this.eden = new ConcurrentHashMap<>(size);
        this.longterm = new WeakHashMap<>(size);
    }

    public V get(K k) {
        V v = this.eden.get(k);
        if (v == null) {
            synchronized (longterm) {
                v = this.longterm.get(k);
            }
            if (v != null) {
                this.eden.put(k, v);
            }
        }
        return v;
    }

    public void put(K k, V v) {
        if (this.eden.size() >= size) {
            synchronized (longterm) {
                this.longterm.putAll(this.eden);
            }
            this.eden.clear();
        }
        this.eden.put(k, v);
    }
}

tomcat实现并发缓存的时候，用eden缓存新生代，longterm缓存老年代. 其中longterm就是一个WeakHashMap.上面的代码到是不难看懂——实现的意图就是让相对常用的对象都能在eden中找到，不常用（甚至被销毁）的对象进入longterm缓存. 而longterm的key指向的实际堆内存对象没有其他引用指向它时，gc就会自动回收heap中该弱引用key指向的实际对象并且弱引用key进入引用队列（WeakHashMap的queue属性）。longterm调用expungeStaleEntries()方法，遍历引用队列中的弱引用，并清除对应的Entry，不会造成内存空间的浪费。

好了，讲完了应用场景. 我们开始分析WeakHashMap的源码（本文基于JDK8）

WeakHashMap和HashMap一样，继承了AbstractMap，而且实现了Map接口，但是和HashMap不一样，它没有实现Cloneable, Serializable接口，所以不需要clone，也不需要序列化（说明WeakHashMap仅仅是做本地缓存）

构造器

一共有四个构造器

public WeakHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); // DEFAULT_LOAD_FACTOR=0.75, DEFAULT_INITIAL_CAPACITY=16
    }
public WeakHashMap(int initialCapacity) {
        this(initialCapacity, 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);
    }
public WeakHashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Initial Capacity: "+
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY) // MAXIMUM_CAPACITY=1073741824 [0x40000000]
            initialCapacity = MAXIMUM_CAPACITY; // 可见WeakHashMap的最大容量是10亿多

        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load factor: "+
                                               loadFactor);
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1; // 可见WeakHashMap的容量一定是不小于入参initialCapacity的2的幂次, 为毛必须要是2的幂次? 和HashMap一样——要用亦或运算进行散列
        table = newTable(capacity); 
        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
    }

源码1

我们的目光主要集中在第13行的构造器上. 而且我们注意力集中在第26、27、28行上. 27、28行比较简单——就是根据入参初始化threshold和loadFactor，至于table的初始化使用了下面的方法

1
2
3

private Entry<K,V>[] newTable(int n) {
        return (Entry<K,V>[]) new Entry<?,?>[n]; // 注意，这一行并不会传入queue参数到Entry构造器中去
    }

源码2

所以table（其实就类比于HashMap的table属性，就是一张哈希表，XXXHashMap用的就是哈希表实现的）就是一个容量为2的幂次的Entry数组.

我们来看看 java.util.WeakHashMap.Entry<K, V>

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;
        }

        @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();
        }
    }

源码3

可见，Entry是弱引用，而且和HashMap的内部类Node一样，实现了Map.Entry接口.

我们注意它的属性——有value，有hash，有next？next说明Entry其实是一根单向链表，所以我们就清楚了WeakHashMap其实是使用拉链法处理哈希冲突(所以没有红黑树的介入，WeakHashMap会比HashMap简单，什么? 为什么没有红黑树的介入? 可能是随时WeakHashMap中的key会被GC掉，所以数量不会长的太大.). 我们看看它的构造器，即第九行，其中super(key, queue);就表示使用了它的爷爷类java.lang.ref.Reference的构造器

Reference(T referent, ReferenceQueue<? super T> queue) {
        this.referent = referent;
        this.queue = (queue == null) ? ReferenceQueue.NULL : queue;
    }

源码4

而这里传入的queue参数就是java.util.WeakHashMap.queue属性. 它的初始化是

/**
     * Reference queue for cleared WeakEntries
     */
    private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

源码5

我们注意源码3的第20行，即java.util.WeakHashMap.unmaskNull(Object)

 /**
     * Returns internal representation of null key back to caller as null.
     */ 
static Object unmaskNull(Object key) {
        return (key == NULL_KEY) ? null : key;
    }
/**
     * Value representing null keys inside tables.
     */
    private static final Object NULL_KEY = new Object();

源码6

即WeakHashMap中key如果为null的话，是使用NULL_KEY表示的，如果key是NULL_KEY的话，则Entry.getKey方法返回的就是null. 否则返回key本身. 这些都很容易读懂. 然后getValue、setValue都很容易. equals方法也很稀松平常. 就是如果地址一样，那肯定可以，不然的话，就基于equals方法.

hashCode方法其实就是拿key、value，但是WeakHashMap的key、value都可能是null的. 所以调用了java.util.Objects.hashCode(Object)

1
2
3

public static int hashCode(Object o) {
        return o != null ? o.hashCode() : 0;
    }

源码7

toString方法我们就不讲解了.

Put方法

我们来看WeakHashMap的put方法

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); // 所有Entry的queue属性都是一样的,但是一旦一个Entry进队之后，此Entry从它的父类Reference继承来的queue属性就会移情别恋——指向ReferenceQueue.ENQUEUED
        if (++size >= threshold)
            resize(tab.length * 2);
        return null;
    }

源码8

其中maskNull 的代码是

/**
    * Use NULL_KEY for key if it is null.
    */
   private static Object maskNull(Object key) {
       return (key == null) ? NULL_KEY : key;
   }

源码9

也就是如果WeakHashMap的key是null的话（说明WeakHashMap允许key、value为null），就用NULL_KEY(一个空的Object)代替. 注意，很有意思，前面有一个方法的名字叫WeakHashMap.unmaskNull（自己搜），那里是如果是NULL_KEY的话，就返回null，这里是如果是null，则返回NULL_KEY，两者恰好相反，所以一个是mask，一个是unmask. 所以名字起的挺有意思哈~

再来看源码8的第三行.

/**
     * Retrieve object hash code and applies a supplemental hash function to the
     * result hash, which defends against poor quality hash functions.  This is
     * critical because HashMap uses power-of-two length hash tables, that
     * otherwise encounter collisions for hashCodes that do not differ
     * in lower bits.
     */
    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 >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

源码10

源码10总体的结果就是h（键key的hashCode）的12-24位比特和20-32位比特， 4-16位比特，7-19位比特做亦或. 为什么要这样将key的hashCode搅个稀巴烂?此方法的注释写的很清楚了——就是为了”against poor quality hash functions”——防止用户覆写的hashCode方法太弱了.导致哈希冲突严重. 其实这种思想在HashMap中也用到了. 可以翻看我之前的文章【3】。

然后来到源码8的第四行，

/**
    * Returns the table after first expunging stale entries.
    */
   private Entry<K,V>[] getTable() {
       expungeStaleEntries(); // 每次获取哈希表前都要打扫一波
       return table;
   }

源码11

注意，我们看到了一个比较感兴趣的函数了——expungeStaleEntries，即清除脏项!!! 这是在数据结构中使用弱引用的关键——必须要做这个，因为弱引用会导致内存泄漏的.

跟进去该方法

/**
     * Expunges stale entries from the table.
     */
    private void expungeStaleEntries() {
        for (Object x; (x = queue.poll()) != null; ) {
            synchronized (queue) {
                @SuppressWarnings("unchecked")
                    Entry<K,V> e = (Entry<K,V>) x; // 因为Entry是WeakReference的子类, 所以理应它进入到queue中去。
                int i = indexFor(e.hash, table.length);

                Entry<K,V> prev = table[i];
                Entry<K,V> p = prev;
                while (p != null) {
                    Entry<K,V> 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--; // 所以WeakHashMap的大小会缩水的
                        break;
                    }
                    prev = p;
                    p = next;
                }
            }
        }
    }

源码12

源码12的注释的含义是”从table中清除脏项”. 其算法是遍历queue属性（这是WeakHashMap的属性）.

通过queue的poll方法. 这个方法是ReferenceQueue的方法，就是移除真正的引用队列（并非是Reference的queue属性）的头结点.

回到源码12，因为根据【4】，queue中保存的都是将被回收的对象对应的弱引用，也就是Entry对应的key. 所以这里就是根据这些即将被回收的key的hash值首先通过indexFor方法找到它应该处于哈希表——table中哪个索引（也就是所谓的槽位）中. 然后遍历这个槽位上的链表，注意，回收的是弱引用引用的那个对象占用的堆内存，而不是回收弱引用对象本身! 这点必须要清楚. 遍历的时候，使用的是==，一旦发现了相等的，就置空相应的value.这样就利于下次GC的时候将”引用的堆内存对象已经回收了的”key对应的value所指向的堆内存对象也回收掉. 这样就解决掉了WeakHashMap使用弱引用做key带来的value的内存泄漏问题.

waitwaitwait~ 源码12的queue是什么鬼? 哦，忘了说了，queue是WeakHashMap的一个属性

/**
     * Reference queue for cleared WeakEntries
     */
    private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

源码13

结合【4】我们知道了，每个java.util.WeakHashMap.Entry<K, V> 都是一个弱引用对象（java.util.WeakHashMap.Entry<K, V> extends WeakReference）. 每个都有一个父亲——Reference. 但是他们父亲中的queue属性是相同的. 因为回到源码8的18行——每个Entry都使用了WeakHashMap的queue属性作为构造器入参之一. 但是如【4】中所言，这个queue属性并不是真正的引用队列，真正的引用队列其实是由每个Entry作为Reference的next属性来维护的.

好了，我们知道了WeakHashMap是如何解决内存泄漏问题的了. 其实和ThreadLocal相比，WeakHashMap解决内存泄漏问题使用了引用队列. 而ThreadLocal仅仅是通过Entry的get方法（注意，ThreadLocal的Entry也是继承WeakReference，而WeakReference的get方法其实是WeakReference的父类Reference的get方法，而其get方法是返回Reference的referent属性, 而这个属性一旦弱引用对象（注意，再次强调，弱引用对象和弱引用对象所引用的堆内存对象是两回事，后者才是被GC回收的东西）进入队列后，或者没有队列可进而弱引用对象直接变成Inactive状态，get方法就会返回null）来判断键是否已经被回收.

WeakHashMap是通过遍历引用队列来找已经回收的对象，则只需要将value置null——让下次gc的时候把value指向的堆内存也回收, 来解决内存泄漏问题.

所以ThreadLocal和WeakHashMap解决值的内存泄漏的思路是不一样的. 个人觉得WeakHashMap的解决思路清晰一些.

回到源码8，其实WeakHashMap的put方法就很清晰了，不再做过多解释.

Get方法

public V get(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) {
            if (e.hash == h && eq(k, e.get()))
                return e.value;
            e = e.next;
        }
        return null;
    }

// java.util.WeakHashMap.eq(Object, Object)的源码如下
    private static boolean eq(Object x, Object y) {
        return x == y || x.equals(y);
    }

源码14

get方法其实很稀松平常——就是和拉链法处理哈希冲突的哈希表查找是一个路数. 但是值得注意的一点是第八行. 首先比较hash值，如果哈希值都不相等的话，后面就不需要比较了（设计者的细节注意的不错）. 只有哈希值相等（哈希值相等是两个对象”相等”的必要条件, 而非充分条件）, 才去用eq方法真正比较key是不是一样, 比较的方法是地址相等或者equals相等. 注意，e.get() 是Reference的get方法，就是获取引用对象Entry引用的那个堆内存对象的强引用.

Remove方法

WeakHashMap的remove方法稀松平常，但是唯一值得注意的是，和HashMap一样——不会resize（即不会缩容，只会扩容）.

Resize方法

resize方法仅仅会在put的时候触发. 这一点其实和HashMap类似.

void resize(int newCapacity) { // 以固定新的容量——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;

        /*
         * 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.
         */
        if (size >= threshold / 2) {
            threshold = (int)(newCapacity * loadFactor);
        } else {
            expungeStaleEntries();
            transfer(newTable, oldTable);
            table = oldTable;
        }
    }

    /** Transfers all entries from src to dest tables */
    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();
                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;
            }
        }
    }

源码15

值得注意的是源码15的第14行的注释，因为第2行以及第10行进行transfer搬运的时候会进行expungeStaleEntries打扫，以及transfer过程中也会用弱引用的get方法进行判断是否是脏项，如果是的话，就清除掉它——置脏项的value（value对应堆内存的强引用）为null.

这两种处理可能导致你事先准备扩容的量——即传入的newCapacity，真正计算一下新的table数组的容量发现其实缩水好多（massive shrinkage）——根本用不到newCapacity那么多，虽然这种情况很少见（This should be rare），但是为了以防万一，我们通过转存回oldTable来解决.

综上，其实分析WeakHashMap最关键就是分析它是怎么处理脏项的. 并且和ThreadLocal进行比较. 可能是ThreadLocal的设计者对自己的散列函数十分有自信，所以采用了开放地址法处理哈希冲突. 但是WeakHashMap的作者使用了较为保守的拉链法处理哈希冲突。嗯? 话说回来，他俩的设计者都是Doug Lea&Josh Bloch啊~

参考

【1】https://yfsyfs.github.io/2019/06/27/ThreadLocal-%E6%BA%90%E7%A0%81%E8%A7%A3%E8%AF%BB/

【2】https://yfsyfs.github.io/2019/06/28/Java%E4%B8%AD%E7%9A%84-%E5%BC%BA%E5%BC%95%E7%94%A8%E3%80%81%E8%BD%AF%E5%BC%95%E7%94%A8%E3%80%81%E5%BC%B1%E5%BC%95%E7%94%A8%E3%80%81%E8%99%9A%E5%BC%95%E7%94%A8/

【3】https://yfsyfs.github.io/2019/06/07/java-util-HashMap-%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/

【4】https://yfsyfs.github.io/2019/07/05/java-lang-ref-Reference-%E6%BA%90%E7%A0%81%E8%A7%A3%E8%AF%BB/