WeakHashMap的原理

大家好，又见面了，我是你们的朋友全栈君。

简介

WeakHashMap和HashMap一样，WeakHashMap也是一个散列表，它存储的内容也是键值对(key-value)映射，而且键和值都可以为null。不过WeakHashMap的键是“弱键”(注：源码中Entry中的定义是这样的：private static class Entry<K,V> extends WeakReference implements Map.Entry<K,V>，即Entry实现了WeakReference类)，当WeakHashMap某个键不再正常使用时，会被从WeakHashMap自动删除。更精确的说，对于一个给定的键，其映射的存在并不能阻止垃圾回收器对该键的丢弃，这就使该键称为被终止的，被终止，然后被回收，这样，这就可以认为该键值对应该被WeakHashMap删除。因此，WeakHashMap使用了弱引用作为内部数据的存储方案，，WeakHashMap可以作为简单缓存表的解决方案，当系统内存不足时，垃圾收集器会自动的清除没有在任何其他地方被引用的键值对。如果需要用一张很大的Map作为缓存表时，那么可以考虑使用WeakHashMap。

在WeakHashMap实现中，借用了ReferenceQueue这个“监听器”来保存被GC回收的”弱键”，然后在每次使用WeakHashMap时，就在WeakHashMap中删除ReferenceQueue中保存的键值对。即WeakHashMap的实现是通过借用ReferenceQueue这个“监听器”来优雅的实现自动删除那些引用不可达的key的。这个我在上一篇的博客中已经做了说明。Java引用Reference学习

WeakHashMap是通过数组table保存Entry(键值对)；每个Entry实际上就是一个链表来实现的。当某“弱键”不再被其它对象引用，就会被GC回收时，这个“弱键”也同时被添加到ReferenceQueue队列中。当下一步我们需要操作WeakHashMap时，会先同步table、queue，table中保存了全部的键值对，而queue中保存的是GC回收的键值对；同步他们，就是删除table中被GC回收的键值对。

我们可以在WeakHashMap的源码中看到这样的一个属性：

/**
* 申明的WeakEntries的queue指针
*/
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

我们来看一下内部Entry类的定义，你就会明白很多事情了：

/*
 * 原来将Entry定义为WeakReference，这样就会自动消失。
 */
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
    V value;
    int hash;
    Entry<K,V> next;

    /**
    * 创建一个新的Entry
    */
    Entry(Object key, V value,
            ReferenceQueue<Object> queue,
            int hash, Entry<K,V> next) {
        // 传入ReferenceQueue和hash，这个可能是在已有头Entry的基础上使用
        super(key, queue);
        this.value = value;
        this.hash  = hash;
        this.next  = next;
    }
    ......
}

如何创建Entry

在进行put操作的时候，会进行Key的建立。大家注意这个弱引用不是指我们put的key是弱引用，而是指内部定义的Entry是弱引用，不要忘记这一点。

public V put(K key, V value) {
    // null key的处理
    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 * 2);
    return null;
}

移除失效元素

进一步研读代码我们可以发现，size方法，getTable等一些的操作中，都会调用一个叫expungeStaleEntries的方法，这个方法的内容如下：

/**
 * 从桶中移除失效的key-value（Entry）
 */
private void expungeStaleEntries() {
    // 从Queue中取被回收的数据，然后进行删除操作
    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;
            }
        }
    }
}

其实就是从Queue中取得，被垃圾回收机制回收的Entry，然后从Map中删除这个Entry，这是一种懒删除的方式，我们之前已经学习了Java的Reference机制，这里就不多研究了。

总结

我觉得这种数据结构，可能面临丢失数据的风险，所以使用场景是哪些不怕丢失数据的地方。我想了一下，什么数据不怕丢，最容易想到的就是可以恢复的数据；然后我想到了内存缓存，的确缓存数据最不怕丢失，因为缓存数据往往都是可以想办法恢复的。所以当我们缓存的数据比较多的时候，使用这个数据结构的确可以帮助我们在系统内存紧张的时候，放弃缓存，然后重新缓存。但是Weak的特性是每次gc都极可能丢失，也会带来不少的问题。总之呢，这种开发的思想真的很好。