WeakHashMap

概述

WeakHashMap 内部的 key 会存储为弱引用，当 JVM GC 的时候，如果这些 key 没有强引用存在的化，会被 GC 回收掉。
WeakHashMap 的存储结构是由 数组 + 链表 实现的。

继承结构

源码实现

基本属性

View Code

/**
 * The default initial capacity -- MUST be a power of two.
 */
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.
 */
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.
 */
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
 */
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

• 默认容量是 16，最大为 2^30；
• 装载因子为 0.75；
• 弱键失效，会把 Entry 添加到引用队列；

构造方法

View Code

/**
 * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
 * capacity and the given load factor.
 *
 * @param  initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
 * @param  loadFactor      The load factor of the <tt>WeakHashMap</tt>
 * @throws IllegalArgumentException if the initial capacity is negative,
 *         or if the load factor is nonpositive.
 */
public WeakHashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Initial Capacity: "+
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;

    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load factor: "+
                                           loadFactor);
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;
    table = newTable(capacity);
    this.loadFactor = loadFactor;
    threshold = (int)(capacity * loadFactor);
}

内部类

View Code

/**
 * The entries in this hash table extend WeakReference, using its main ref
 * field as the key.
 */
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();
    }
}

• 与 HashMap 类似，初始容量为 2^n ；
• 扩容门槛为 capacity * loadFactor

操作方法

put(K key, V value)

View Code

/**
 * 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.
 *
 * @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);
    // 计算hash值
    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) {
        // 如果key存在，则修改
        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;
}

/**
 * Value representing null keys inside tables.
 */
private static final Object NULL_KEY = new Object();

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

/**
 * 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);
}

/**
 * Returns index for hash code h.
 */
private static int indexFor(int h, int length) {
    return h & (length-1);
}

/**
 * Checks for equality of non-null reference x and possibly-null y.  By
 * default uses Object.equals.
 */
private static boolean eq(Object x, Object y) {
    return x == y || x.equals(y);
}

• 计算hash；

HashMap 不同，HashMap 中如果key为空直接返回0，这里是用空对象来计算的。

• 计算在哪个桶中；

• 遍历桶对应的链表，如果找到元素就用新值替换旧值，并返回旧值；

• 如果没找到就在链表头部插入新元素；

• 如果元素数量达到了扩容门槛，就把容量扩大到2倍大小；

HashMap中是大于threshold才扩容，这里等于threshold就开始扩容了。

resize(int newCapacity)

View Code

/**
 * 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.
 *
 * @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).
 */
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);
    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 {
        // 使用旧数组，转移过程中会清除失效的 Entry
        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;
        }
    }
}

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

• 判断旧容量是否达到最大容量，达到最大容量，则不在进行扩容；

• 新建新数组并把元素全部转移到新桶中；

• 如果转移后元素个数不到扩容门槛的一半，则把元素再转移回旧数组，继续使用旧数组，说明不需要扩容；否则使用新数组，并计算新数组的扩容门槛；

• 转移元素的过程中会把key为null的元素清除掉，所以size会变小；

get(Object key)

View Code

/**
 * Returns the value to which the specified key is mapped,
 * or {@code null} if this map contains no mapping for the key.
 *
 * <p>More formally, if this map contains a mapping from a key
 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
 * key.equals(k))}, then this method returns {@code v}; otherwise
 * it returns {@code null}.  (There can be at most one such mapping.)
 *
 * <p>A return value of {@code null} does not <i>necessarily</i>
 * indicate that the map contains no mapping for the key; it's also
 * possible that the map explicitly maps the key to {@code null}.
 * The {@link #containsKey containsKey} operation may be used to
 * distinguish these two cases.
 *
 * @see #put(Object, Object)
 */
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;
}

• 计算元素在数组中的位置
• 遍历链表，如果找到，则返回

remove(Object key)

View Code

/**
 * Removes the mapping for a key from this weak hash map if it is present.
 * More formally, if this map contains a mapping from key <tt>k</tt> to
 * value <tt>v</tt> such that <code>(key==null ?  k==null :
 * key.equals(k))</code>, that mapping is removed.  (The map can contain
 * at most one such mapping.)
 *
 * <p>Returns the value to which this map previously associated the key,
 * or <tt>null</tt> if the map contained no mapping for the key.  A
 * return value of <tt>null</tt> does not <i>necessarily</i> indicate
 * that the map contained no mapping for the key; it's also possible
 * that the map explicitly mapped the key to <tt>null</tt>.
 *
 * <p>The map will not contain a mapping for the specified key once the
 * call returns.
 *
 * @param key key whose mapping is to be removed from the map
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>
 */
public V remove(Object key) {
    Object k = maskNull(key);
    int h = hash(k);
    Entry<K,V>[] tab = getTable();
    // 找到数组中的位置
    int i = indexFor(h, tab.length);
    Entry<K,V> prev = tab[i];
    Entry<K,V> e = prev;

    // 遍历链表
    while (e != null) {
        Entry<K,V> next = e.next;
        if (h == e.hash && eq(k, e.get())) {
            modCount++;
            size--;
            if (prev == e)
                tab[i] = next;
            else
                prev.next = next;
            return e.value;
        }
        prev = e;
        e = next;
    }

    return null;
}

• 计算 hash 并找到数组中的位置；
• 遍历链表，找到则删除；

总结

• WeakHashMap 使用 数组 + 链表 的存储结构；
• WeakHashMap 中的 key 是弱引用，GC 的时候会被清除；
• WeakHashMap 增加元素，会检查元素是否失效，失效的元素会被删除；
• String 作为 key 时，一定要 new String() 这样的方式声明才会失效；

小知识

• 强引用

  如果一个对象具有强引用，它绝对不会被gc回收。如果内存空间不足了，gc宁愿抛出OutOfMemoryError，也不是会回收具有强引用的对象。

• 软引用

  如果一个对象只具有软引用，则内存空间足够时不会回收它，但内存空间不够时就会回收这部分对象。只要这个具有软引用对象没有被回收，程序就可以正常使用。

• 弱引用

  如果一个对象只具有弱引用，则不管内存空间够不够，当gc扫描到它时就会回收它。

• 虚引用

  如果一个对象只具有虚引用，那么它就和没有任何引用一样，任何时候都可能被gc回收。

软（弱、虚）引用必须和一个引用队列（ReferenceQueue）一起使用，当gc回收这个软（弱、虚）引用的对象时，会把这个软（弱、虚）引用放到这个引用队列中。
比如，上述的Entry是一个弱引用，它引用的对象是key，当key被回收时，Entry会被放到queue中。