集合番@WeakHashMap一文通（1.7版）

JAVA COLLECTIONS 源码 1.7版本

• 笔者个人博客 kiraSally的掘金个人博客 感谢支持

1.预备知识：引用的相关知识

1.1 强引用（Strong Reference）

Object o = new Object(); 

• 强引用是Java 默认实现 的引用，JVM会尽可能长时间的保留强引用的存在（直到内存溢出）
• 当内存空间不足，Java虚拟机宁愿抛出OutOfMemoryError错误，使程序异常终止，也不会靠随意回收具有强引用的对象来解决内存不足的问题：只有当没有任何对象指向它时JVM将会回收

1.2 软引用（Soft Reference）

public class SoftReference<T> extends Reference<T> {...} 

• 软引用只会在虚拟机 内存不足 的时候才会被回收
• 软引用可以和一个引用队列（ReferenceQueue）联合使用，如果软引用所引用的对象被垃圾回收器回收，Java虚拟机就会把这个软引用加入到与之关联的引用队列中

1.3 弱引用（Weak Reference）

public class WeakReference<T> extends Reference<T> {...} 

• 弱引用是指当对象没有任何的强引用存在，在 下次GC回收 的时候它将会被回收
• 在垃圾回收器线程扫描它所管辖的内存区域的过程中，一旦发现了只具有弱引用的对象，不管当前内存空间足够与否，都会回收它的内存
• 需要注意的是：由于垃圾回收器是一个优先级很低的线程，因此不一定会很快发现那些只具有弱引用的对象

1.4 虚（或幻影）引用（Phantom Reference）

public class PhantomReference<T> extends Reference<T> {  
...  
    public T get() 
        return null;  
    }  
} 

• 虚引用形同虚设，与其他几种引用都不同，虚引用并不会决定对象的生命周期，get方法只返回null
• 如果一个对象仅持有虚引用，那么它就和没有任何引用一样，在任何时候都可能被垃圾回收器回收
• 唯一的作用就是可以用来 记录对象是什么时候被GC回收的(即跟踪对象被垃圾回收器回收的活动)
• 引用与软引用和弱引用的一个区别在于：虚引用必须和引用队列联合使用。当垃圾回收器准备回收一个对象时，如果发现它还有虚引用，就会在回收对象的内存之前，把这个虚引用加入到与之关联的引用队列中

2.WeakHashMap的定义

• WeakHashMap 是存储键值对(key-value)的非同步且无序的散列表，键和值都允许为null，基本跟 HashMap一致
• 特殊之处在于 WeakHashMap 里的entry可能会被GC自动删除，即使没有主动调用 remove() 或者 clear() 方法
• 其键为弱键，除了自身有对key的引用外，此key没有其他引用那么此map会自动丢弃此值
• 在《Effective Java》一书中第六条，消除陈旧对象时，提到了weakHashMap，用于短时间内就过期的缓存
• 由于与JDK1.7版本的HashMap实现原理一致（具体请参见笔者的 HashMap一文通），这里只讨论不同
• 若有机会写JVM篇的垃圾回收机制时会再进一步描述 Reference

3.WeakHashMap的数据结构

3.1 类定义

public class WeakHashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V> 

3.2 重要全局变量

/**
  * The default initial capacity -- MUST be a power of two.
  * 默认容量，必须是2次幂
  */
private static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
  * The maximum capacity, used if a higher value is implicitly specified by either of the
  * constructors with arguments. MUST be a power of two <= 1<<30.
  * 最大容量，必须为2次幂且 <= 1<<30
  */
private static final int MAXIMUM_CAPACITY = 1 << 30;
/**
  * The load factor used when none specified in constructor.
  * 负载因子
  */
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
  * The table, resized as necessary. Length MUST Always be a power of two.
  * 容量必须为2次幂的数组
  */
Entry<K,V>[] table;
/**
  * The number of key-value mappings contained in this weak hash map.
  * 拥有键值对的数量
  */
private int size;
/**
  * The next size value at which to resize (capacity * load factor).
  * 阈值 -- 扩容判断依据
  */
private int threshold;
/**
  * The load factor for the hash table.
  */
private final float loadFactor;
/**
  * Reference queue for cleared WeakEntries
  * 引用队列，用于存储已被GC清除的WeakEntries
  */
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

3.3 构造器

// 默认构造函数
WeakHashMap()
// 指定"容量大小"的构造函数
WeakHashMap(int capacity)
// 指定"容量大小"和"负载因子"的构造函数
WeakHashMap(int capacity, float loadFactor)
// 包含"子Map"的构造函数
WeakHashMap(Map<? extends K, ? extends V> map)

实现跟JDK1.7版本HashMap的实现一致,具体请参见笔者的 HashMap一文通

3.4 Entry

/**
  * The entries in this hash table extend WeakReference, using its main ref field as the key.
  * 该Enty继承WeakReference，从而具备弱引用的特性
  */
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
    V value;
    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;
    }
    ....
}    

4.WeakHashMap的重点知识

4.1 弱键回收

1. 创建 WeakHashMap 对象，执行 put() 新增键值对
2. 当某 weakKey 不再被其它对象引用，将被GC回收，同时该key会被添加到 ReferenceQueue(queue) 队列中
3. 当 WeakHashMap 执行新的操作时，会先同步 table 和 queue；其中 table 中保存了全部的键值对，而 queue 中保存被GC回收的key（同步即删除 table 中被GC回收的键值对）

4.2 特殊情况

• 当使用 WeakHashMap 时，即使没有显示的添加或删除任何元素，也可能发生如下情况（源自JavaDoc）：

• 调用两次 size() 方法返回不同的值；
• 两次调用 isEmpty() 方法，第一次返回false，第二次返回true；
• 两次调用 containsKey() 方法，第一次返回true，第二次返回false，尽管两次使用的是同一个key；
• 两次调用 get() 方法，第一次返回一个value，第二次返回null，尽管两次使用的是同一个对象。

4.3 应用场景

• 根据其回收特性，可以用作缓存，但由于其的不可控性，导致其的使用非常有限
• stackoverFlow对于该问题的描述
• 解决方案集合 （吐槽一下翻译）

//如当做线程的metaData信息记录，可用于查看当前的alive线程数和相关情况
WeakHashMap<Thread, SomeMetaData>

5.WeakHashMap的重点方法

5.1 put方法

/**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for this key, the old value is replaced.
     *      若该key对应的映射（值）已经存在，会覆盖旧值
     * @param key key with which the specified value is to be associated.
     * @param value value to be associated with the specified key.
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        Object k = maskNull(key);
        int h = hash(k);
        //插入操作会 做一次过期对象清洗操作，其他与HashMap一致
        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];
        //新建的Entry对象需要持有queue引用
        tab[i] = new Entry<>(k, value, queue, h, e);
        if (++size >= threshold)
            resize(tab.length * 2);//同样是扩容2倍
        return null;
    }

5.2 get方法

/**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *      若key所对应的值不存在，返回null
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        Object k = maskNull(key);
        int h = hash(k);
        //为了每次获取map中的元素的时候都能从已经自动清理过后的table数组中获取，会先执行清洗操作
        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;
    }

5.3 resize方法

/**
  * Rehashes the contents of this map into a new array with a
  * larger capacity.  This method is called automatically when the
  * number of keys in this map reaches its threshold.
  * If current capacity is MAXIMUM_CAPACITY, this method does not
  * resize the map, but sets threshold to Integer.MAX_VALUE.
  * This has the effect of preventing future calls.
  *     当前容量若已为MAXIMUM_CAPACITY，则扩容为Integer.MAX_VALUE
  * @param newCapacity the new capacity, MUST be a power of two;
  *        must be greater than current capacity unless current
  *        capacity is MAXIMUM_CAPACITY (in which case value is irrelevant).必须是2次幂
  */
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);
    boolean oldAltHashing = useAltHashing;
    useAltHashing |= sun.misc.VM.isBooted() &&
            (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean rehash = oldAltHashing ^ useAltHashing;
    transfer(oldTable, newTable, rehash);
    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.
     * 若忽视null和处理引用队列将会导致Map中的元素数量大量减少，从而会修复旧数组
     * 这种情况比较稀少，但仍要避免 堆满垃圾对象的数组的无限拓展
     */
    if (size >= threshold / 2) { //当长度>=阈值的一半时，需要重新计算阈值
        threshold = (int)(newCapacity * loadFactor);
    } else {
        //当长度<阈值的一半时（多半是null或弱引用过期导致），会重新修复数组
        expungeStaleEntries();
        transfer(newTable, oldTable, false);
        table = oldTable;
    }
}
/**
  * Returns the table after first expunging stale entries.
  * 返回清洗过后的table
  */
private Entry<K,V>[] getTable() {
    expungeStaleEntries();
    return table;
}

5.4 clear方法

/**
  * Removes all of the mappings from this map.
  * The map will be empty after this call returns.
  * 清空Map
  */
public void clear() {
    // clear out ref queue. We don't need to expunge entries since table is getting cleared.
    // 直接清空queue即可，不需要再额外地执行清洗操作
    while (queue.poll() != null)
        ;
    modCount++;//结构性修改
    Arrays.fill(table, null);//数组清空操作推荐以后时候该封装方法
    size = 0;
    // Allocation of array may have caused GC, which may have caused additional entries to go stale.
    // Removing these entries from the reference queue will make them eligible for reclamation.
    // 数组分配操作可能会触发GC，从而可能导致新增的元素直接过期
    // 这时候需要再执行一次queue清空操作从而使新增元素能被合理地回收
    while (queue.poll() != null)
        ;
}

5.5 expungeStaleEntries方法

• weakKey(弱键)是一个 弱引用(WeakReference) ，其目的：实现对"键值对"的动态回收，
• 当 弱键 不再被使用到时，GC会回收它，WeakReference也会将弱键对应的键值对删除
• 在Java中，WeakReference 和 ReferenceQueue 是联合使用的，入队时机参见 enqueue 方法
• 在 WeakHashMap 中：如果弱引用所引用的对象被垃圾回收，Java虚拟机就会把这个弱引用加入到与之关联的引用队列中，之后 WeakHashMap 会根据引用队列，来删除已被GC回收的 弱键 对应的键值对
• GC判断某个对象是否可被回收的依据是，是否有有效的引用指向该对象

/**
  * Expunges stale entries from the table. -- 删除过时的entry
  * 该方法是实现弱键回收的最关键方法，也是区分HashMap的根本方法
  * 核心：移除table和queue的并集元素（queue中存储是已被GC的key，注意是key！！）
  * 效果：key在GC的时候被清除，value在key清除后访问WeakHashMap被清除
  */
private void expungeStaleEntries() {
    //从队列中出队遍历
    //poll 移除并返问队列头部的元素；如果队列为空，则返回null
    for (Object x; (x = queue.poll()) != null; ) {
        synchronized (queue) {
            //值得一提的是WeakHashMap是非线程安全的，这里却同步了一下
            //大神原本的用意是保证在多线程时能不破坏数据结构，但JavaDoc已经强调这类非安全，如下文
            //http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6425537
            @SuppressWarnings("unchecked")
                Entry<K,V> e = (Entry<K,V>) x;
            //找到该队列中的元素在数组中的位置，并移除该元素（table和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 移除value
                    size--;
                    break;
                }
                prev = p;
                p = next;
            }
        }
    }
}

集合番@WeakHashMap一文通(1.7版) 由 黄志鹏kira 创作，采用 知识共享 署名-非商业性使用 4.0 国际 许可协议 进行许可。

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名。