简介

WeakHashMap 继承于AbstractMap，实现了Map接口。

和HashMap一样，WeakHashMap 也是一个散列表，它存储的内容也是键值对(key-value)映射，而且键和值都可以是null。
不一样的是，JDK1.8开始，HashMap中引入了红黑树，节点名从entry改成了node，而WeakHashMap还是没有被修改，还是采用链表形式的拉链法解决哈希冲突。

所谓weak，就是WeakHashMap中存储的键值是弱引用的，是很有可能被GC回收的，所以，WeakHashMap中需要对被GC的键的键值对进行清除，其实现原理：

WeakHashMap中有一个ReferenceQueue用来存储被GC回收的弱键；
当每次操作WeakHashMap的时候，就会需要同步table和queue，通过同步的行为，就可以删除table中已经被回收了的键的键值对。

源码分析

定义

public class WeakHashMap<K,V>

    extends AbstractMap<K,V>

    implements Map<K,V> {}

字段

	// 默认初始容量，和hashmap一样

    private static final int DEFAULT_INITIAL_CAPACITY = 16;

	// 最大容量

    private static final int MAXIMUM_CAPACITY = 1 << 30;

	// 默认负载因子

    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

	// 存储键值对链表头节点的数组

    Entry<K,V>[] table;

	// 当前节点数量

    private int size;

	// 扩容阈值

    private int threshold;

	// 加因子实际大小

    private final float loadFactor;

	// 被垃圾回收的弱引用键队列

    private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

	// 修改次数

    int modCount;

和参数和HashMap大致相同，不同的是，多了一个引用队列，用来存储被GC的引用，用于之后的同步。

构造函数

	// 初始化容量和加载因子的构造函数

    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;

        //	通过比较位移的方式，得到第一个大于等于设定容量的2的幂次的合法容量

        while (capacity < initialCapacity)

            capacity <<= 1;

        // 这个newtbale就是初始化了一个capactiy大小的空数组

        table = newTable(capacity);

        this.loadFactor = loadFactor;

        // 计算扩容阈值

        threshold = (int)(capacity * loadFactor);

    }

	// 初始化容量的构造

    public WeakHashMap(int initialCapacity) {

        this(initialCapacity, DEFAULT_LOAD_FACTOR);

    }

	// 默认构造

    public WeakHashMap() {

        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);

    }

	// 添加其他map的构造

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

    }

内部类

1.节点的结构

	// 继承了弱引用，实现了Map.Entry，所以它的节点键值都是弱引用，不会防止GC

    private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {

    	// 节点存储值

        V value;

        // 节点哈希值

        final int hash;

        // 下一个节点引用

        Entry<K,V> next;

        // 构造，新建节点

        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;

        }

		// 重写了hashCode函数，然会键值的哈希值而不是对象的哈希值

        public int hashCode() {

            K k = getKey();

            V v = getValue();

            return Objects.hashCode(k) ^ Objects.hashCode(v);

        }

        public String toString() {

            return getKey() + "=" + getValue();

        }

    }

2.迭代器

    private abstract class HashIterator<T> implements Iterator<T> {

    	// 当前索引

        private int index;

        // 当前元素

        private Entry<K,V> entry;

        // 上一次返回的元素

        private Entry<K,V> lastReturned;

        // 实现fast-faiul机制

        private int expectedModCount = modCount;

		// 指向下一个键值（强引用）

        private Object nextKey;

		// 当前节点（强引用）

        private Object currentKey;

		// 构造

        HashIterator() {

            index = isEmpty() ? 0 : table.length;

        }

		// 判断是否存在下一个节点

        public boolean hasNext() {

            Entry<K,V>[] t = table;

			// 如果下一个而节点是空的，就需要遍历table，将下一个节点指向table中下一个不为空的头节点

            while (nextKey == null) {

                Entry<K,V> e = entry;

                int i = index;

                while (e == null && i > 0)

                    e = t[--i];

                entry = e;

                index = i;

                if (e == null) {

                    currentKey = null;

                    return false;

                }

                nextKey = e.get(); // hold on to key in strong ref

                if (nextKey == null)

                    entry = entry.next;

            }

            return true;

        }

        // 获取下一个节点

        protected Entry<K,V> nextEntry() {

            if (modCount != expectedModCount)

                throw new ConcurrentModificationException();

            if (nextKey == null && !hasNext())

                throw new NoSuchElementException();

            lastReturned = entry;

            entry = entry.next;

            currentKey = nextKey;

            nextKey = null;

            return lastReturned;

        }

		// 删除当前节点

        public void remove() {

            if (lastReturned == null)

                throw new IllegalStateException();

            if (modCount != expectedModCount)

                throw new ConcurrentModificationException();

            WeakHashMap.this.remove(currentKey);

            expectedModCount = modCount;

            lastReturned = null;

            currentKey = null;

        }

    }

	// 值遍历

    private class ValueIterator extends HashIterator<V> {

        public V next() {

            return nextEntry().value;

        }

    }

	// 键的遍历

    private class KeyIterator extends HashIterator<K> {

        public K next() {

            return nextEntry().getKey();

        }

    }

	// 键值对的遍历

    private class EntryIterator extends HashIterator<Map.Entry<K,V>> {

        public Map.Entry<K,V> next() {

            return nextEntry();

        }

    }

3.集合

	// 键的集合

    private class KeySet extends AbstractSet<K> {

    	// 调用迭代器的接口

        public Iterator<K> iterator() {

            return new KeyIterator();

        }

        public int size() {

            return WeakHashMap.this.size();

        }

        public boolean contains(Object o) {

            return containsKey(o);

        }

        public boolean remove(Object o) {

            if (containsKey(o)) {

                WeakHashMap.this.remove(o);

                return true;

            }

            else

                return false;

        }

        public void clear() {

            WeakHashMap.this.clear();

        }

		// 分割迭代器，用于并行

        public Spliterator<K> spliterator() {

            return new KeySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);

        }

    }

   // 键值对集合

   private class EntrySet extends AbstractSet<Map.Entry<K,V>> {

        public Iterator<Map.Entry<K,V>> iterator() {

            return new EntryIterator();

        }

        public boolean contains(Object o) {

            if (!(o instanceof Map.Entry))

                return false;

            Map.Entry<?,?> e = (Map.Entry<?,?>)o;

            Entry<K,V> candidate = getEntry(e.getKey());

            return candidate != null && candidate.equals(e);

        }

        public boolean remove(Object o) {

            return removeMapping(o);

        }

        public int size() {

            return WeakHashMap.this.size();

        }

        public void clear() {

            WeakHashMap.this.clear();

        }

		// 深拷贝接口

        private List<Map.Entry<K,V>> deepCopy() {

            List<Map.Entry<K,V>> list = new ArrayList<>(size());

            // 将键值对都添加到新的链表当中

            for (Map.Entry<K,V> e : this)

                list.add(new AbstractMap.SimpleEntry<>(e));

            return list;

        }

		// 转化为数组

        public Object[] toArray() {

            return deepCopy().toArray();

        }

		// 模板方法的数组

        public <T> T[] toArray(T[] a) {

            return deepCopy().toArray(a);

        }

		// 分割迭代

        public Spliterator<Map.Entry<K,V>> spliterator() {

            return new EntrySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);

        }

    }

方法

1.哈希函数

	// 获取键的哈希值

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

    }

2.元素获取

	// 获取最新的表

    private Entry<K,V>[] getTable() {

    	// 之所以要获取最新的表，是因为需要先删除GC的Key

        expungeStaleEntries();

        return table;

    }

	// 获取对应键的元素值

    public V get(Object key) {

    	// 如果key是null那么就用一个final的空对象，这样保证每次null的对象相同

        Object k = maskNull(key);

        // 获取key的哈希值

        int h = hash(k);

        // 获取最新的表，在这里会触发一次表的更新，就是将GC了的key给移除

        Entry<K,V>[] tab = getTable();

        // 根据哈希值获取当前table中对应的索引

        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;

    }

3.元素添加

	// 添加获取修改键值

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

		// 遍历链表，如果有相同的key，那就直接修改值

        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;

    }

4.删除被GC的节点

WeakHashTable就是通过这个函数实现弱引用被GC后的表中节点的回收。

    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; // 将键对应得值指向空，这样就可以让GC来回收原来得对象

                        size--;

                        break;

                    }

                    prev = p;

                    p = next;

                }

            }

        }

    }

5.扩容

扩容的大致其实和HashMap差不多

	// 扩容到新得容量

    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;

		// 查看size是不是大于，扩容阈值的一半，如果不是，说明size又变小了，不需要扩容了

        if (size >= threshold / 2) {

        	// 更新扩容阈值

            threshold = (int)(newCapacity * loadFactor);

        } else {

        	// 更新GC后的key

            expungeStaleEntries();

            // 返回原有大小的表

            transfer(newTable, oldTable);

            table = oldTable;

        }

    }

	// 将原表复制到目标表

    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) {

                	// 用于GC

                    e.next = null;

                    e.value = null;

                    size--;

                } else {

                	// 获取到对应的索引

                    int i = indexFor(e.hash, dest.length);

                    e.next = dest[i];

                    dest[i] = e;

                }

                e = next;

            }

        }

    }

6.元素删除

    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;

    }

总结

源码总结

大致的1.7的哈希表差不多，采用拉链法解决哈希冲突，只有链表，采用头插法，包括初始容量、扩容阈值和大小。
表中的节点继承了弱引用，这说明它的引用的键是会被垃圾回收的。
主要的区别就是它再对表进行修改的时候，都会调用expungeStaleEntries函数，用来删除那些已经被垃圾回收了的键，所对应的键值对。需要删除的键会存放在ReferenceQueue 中，每次去获取需要被删除的key。
和其他集合的重要区别，WeakHashMap没有实现克隆和序列化的接口。

巴特西

Java集合源码分析（八）——WeakHashMap

简介