WeakHashMap

1. 简介

WeakHashMap 是一种使用弱项（WeakEntry）的哈希映射表，本质上是一种特殊的HashMap，其关于哈希表部分的实现与HashMap 没有什么不同，而弱项就是使用弱引用实例作为 Map 的表项（表元素）。

2. WeakHashMap弱项的实现

WeakHashMap 的表项类型 Entry 继承了弱引用类 java.lang.ref.WeakReference<Object> （代码1），并且内部维护了一个引用队列 queue（代码2），是 java.lang.ref.ReferenceQueue<Object> 的实例，用于收集被 GC 回收了弱键的表项 。

public class WeakHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V> {
    ...
     /**
     * Reference queue for cleared WeakEntries
     */
    1. private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
    ...
    2. 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;
        }

        ...
    }
    ...
    /**
     * Expunges stale entries from the table.
     */
    3. 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);

                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--;
                        break;
                    }
                    prev = p;
                    p = next;
                }
            }
        }
    }
    /**
     * Returns the table after first expunging stale entries.
     */
    private Entry<K,V>[] getTable() {
        expungeStaleEntries();
        return table;
    }
    ...
}

所以每一个表项 Entry 本身就是一个弱引用实例，Entry 的构造函数通过调用父类 WeakReference 构造函数 super(key, queue) 将表项的键 key 的值关联到弱引用上；所以当我们将键值对放入到 WeakHashMap 中时，WeakHashMap 使用弱引用 Entry 来持有 key，这不同于 HashMap （HashMap 是在 Entry 对象中用强引用来持有 key）。所以一旦某个键在 WeakHashMap 外部没有其他强引用关联，GC 就会将该键回收，同时将该键关联的弱引用实例添加到注册的引用队列queue中，尽管该键并未从WeakHashMap 中移除。虽然 key 已经被回收了，但是表项 Entry 还保存在 WeakHashMap 中，所以WeakHashMap 在进行每一次操作之前，都要进行数据同步工作，就是将被GC回收了键对象的Entry实例（保存在 queue 里面）从WeakHashMap 中移除（代码3）。

3. WeakHashMap应用

前文我们讲解了 WeakHashMap 弱项的实现，因为 WeakHashMap 的弱项本质上是弱引用实例，所以它的键在下一次 GC 时间就会被回收。那么 WeakHashMap 适合用在什么地方呢？有些书根据 WeakHashMap 弱项的特性，认为 WeakHashMap 适合用来做缓存，但是如果直接用 WeakHashMap 做缓存，可能会有以下几个问题：

• 因为弱项在下一次 GC 就会被回收，所以缓存元素的生命周期太短，并且无论元素的使用频率如何，都会在下一次 GC 被回收，会导致缓存命中率过低。
• 缓存元素过期时间不可控，因为使用 WeakHashMap 做缓存时，完全依赖 GC 时间和频率来控制元素的过期时间，这对用户来说时透明的，是不可控制的。
• WeakHashMap 每次访问 WeakHashMap 时，都会触发数据同步工作 expungeStaleEntries，通过其实现源码，我们看到这个方法还是比较耗时的，因此如果用 WeakHashMap 做缓存，尤其是实时性要求较高的场景，会有性能方面的问题
• 由于弱项本质上是弱引用实例，是一种特殊引用，JVM 在每一个 GC 周期，都会有专门的时间周期对这些特殊引用进行特殊处理（是引用处理 Ref Proc 和引用排队 Ref Enq 两个处理阶段），如果缓存中的元素数量比较多时，就会出现大量的弱引用实例，这会导致这两个处理阶段耗时较高。

我们看到，用 WeakHashMap 直接做缓存会有很多问题，所以 WeakHashMap 不适合用来做直接缓存，但是 WeakHashMap 特别适合来做辅助缓存。比如下面的例子，我们开发了一个有回收站功能的缓存，主缓存功能使用 Guava 的缓存实现，回收站缓存使用 WeakHashMap 实现。当主缓存 mainCache 中某个键过期后，缓存并没有将其直接放弃，而是先移动到回收站 recycleBin 中，在下一次 GC 时间来临之前，如果这个键被重新访问了，那么就会被从回收站中复活，重新被放入缓存中，否则，这个键会在下一次 GC 时被回收，辅助回收站的设计可以有效提高缓存的命中率。
这样设计的主要基本思路在于弱可达与不可达的区别：由于 JVM 的 GC 需要在某些条件下才触发，所以，当缓存中的元素过期之后，一般会将该元素移除，使其变为不可达对象，等待 GC 回收，但是 GC 并不会马上回收，需要等待进入下一次 GC 时间，在下一次 GC 来临之前的这段时间，虽然对象是不可达的，但它仍然会保存在内存中，而且在这段时间内，已经过期的元素也有被重新访问的可能性，所以为了充分利用这段时间，可以将过期的元素先用弱引用关联起来，虽然对于过期的元素来说，即使有了弱引用，也会在下次GC被回收，但其区别在于，在过期的元素被回收之前，可以通过弱引用获取到该对象，并关联到其他强引用来拯救该对象，防止其被回收，但一个不可达的对象，由于已经无法通过 GC Roots 访问，所以已经无法被拯救了。

/**
 * 携带回收站的缓存
 */
public class MyCache extends CacheLoader<String, Object> implements RemovalListener<String, Object>{

    private ScheduledExecutorService cacheExecutor = Executors.newScheduledThreadPool(1);

    private final LoadingCache<String, Object> mainCache = CacheBuilder.
            newBuilder().
            expireAfterAccess(1, TimeUnit.MINUTES).
            removalListener(RemovalListeners.asynchronous(this, this.cacheExecutor)).
            build(this);

    private final WeakHashMap<String, Object> recycleBin = new WeakHashMap<String, Object>();

    public MyCache() {
        super();
        this.cacheExecutor.scheduleAtFixedRate(this.mainCache::cleanUp, 1, 1, TimeUnit.MINUTES);
    }
    
    public Object get(String key) {
        try {
            return this.mainCache.get(key);
        } catch (ExecutionException e) {}
        return null;
    }
    
    public void put(String key, Object value) {
        this.mainCache.put(key, value);
    }
    
    @Override
    public synchronized Object load(String key) throws Exception {
        return this.recycleBin.remove(key);
    }

    @Override
    public synchronized void onRemoval(RemovalNotification<String, Object> notification) {
        this.recycleBin.put(notification.getKey(), notification.getValue());
    }
}