java源码-WeakHashMap

开篇

作为Map系列的最后一篇，我觉得有必要讲讲WeakHashMap这个类，因为这个类可以解决一些oom的问题，典型的场景是在一个HashMap中put不同的key/value对象，如果此时设置key为null而未清除map当中的key对象，那么就无法通过gc回收该对象。
在这篇文章中我希望能够讲明白WeakHashMap是如何解决key和value的gc回收问题，希望能够对一些应用场景产生帮助。

WeakHashMap使用举例

在下面这个例子当中通过设置w1=null，会触发gc对WeakHashMap当中的w1进行主动回收。

import java.util.Iterator; import java.util.Map; import java.util.WeakHashMap; import java.util.Date; import java.lang.ref.WeakReference; public class WeakHashMapTest { public static void main(String[] args) throws Exception { testWeakHashMapAPIs(); } private static void testWeakHashMapAPIs() { // 初始化3个“弱键” String w1 = new String("one"); String w2 = new String("two"); String w3 = new String("three"); // 新建WeakHashMap Map wmap = new WeakHashMap(); // 添加键值对 wmap.put(w1, "w1"); wmap.put(w2, "w2"); wmap.put(w3, "w3"); // 打印出wmap System.out.printf("\nwmap:%s\n",wmap ); // containsKey(Object key) :是否包含键key System.out.printf("contains key two : %s\n",wmap.containsKey("two")); System.out.printf("contains key five : %s\n",wmap.containsKey("five")); // containsValue(Object value) :是否包含值value System.out.printf("contains value 0 : %s\n",wmap.containsValue(new Integer(0))); // remove(Object key) ： 删除键key对应的键值对 wmap.remove("three"); System.out.printf("wmap: %s\n",wmap ); // ---- 测试 WeakHashMap 的自动回收特性 ---- // 将w1设置null。 // 这意味着“弱键”w1再没有被其它对象引用，调用gc时会回收WeakHashMap中与“w1”对应的键值对 w1 = null; // 内存回收。这里，会回收WeakHashMap中与“w1”对应的键值对 System.gc(); // 遍历WeakHashMap Iterator iter = wmap.entrySet().iterator(); while (iter.hasNext()) { Map.Entry en = (Map.Entry)iter.next(); System.out.printf("next : %s - %s\n",en.getKey(),en.getValue()); } // 打印WeakHashMap的实际大小 System.out.printf(" after gc WeakHashMap size:%s\n", wmap.size()); } } --------------------------------输出结果-------------------------------- wmap:{three=w3, one=w1, two=w2} contains key two : true contains key five : false contains value 0 : false wmap: {one=w1, two=w2} next : two - w2 after gc WeakHashMap size:1 

WeakHashMap类图

WeakHashMap的类图非常简单，简单跟HashMap很像，基本上实现了Map接口而已，所以可以按照HashMap的角度进行解读。

WeakHashMap的工作原理

WeakHashMap的核心在于key通过WeakReference进行包装，弱引用(Weak Reference)简单来说就是将对象留在内存的能力不是那么强的引用。使用WeakReference，垃圾回收器会帮你来决定引用的对象何时回收并且将对象从内存移除。

创建弱引用如下： WeakReference<Widget> weakWidget = new WeakReference<Widget>(widget); 使用weakWidget.get()就可以得到真实的Widget对象，因为弱引用不能阻挡垃圾回收器对其回收，你会发现（当没有任何强引用到widget对象时）使用get时突然返回null。

解决上述的widget序列数记录的问题，最简单的办法就是使用Java内置的WeakHashMap类。WeakHashMap和HashMap几乎一样，唯一的区别就是它的键（不是值!!!）使用WeakReference引用。当WeakHashMap的键标记为垃圾的时候，这个键对应的条目就会自动被移除。这就避免了上面不需要的Widget对象手动删除的问题。使用WeakHashMap可以很便捷地转为HashMap或者Map。

引用队列(Reference Queue)，一旦弱引用对象开始返回null，该弱引用指向的对象就被标记成了垃圾。而这个弱引用对象（非其指向的对象）就没有什么用了。通常这时候需要进行一些清理工作。比如WeakHashMap会在这时候移除没用的条目来避免保存无限制增长的没有意义的弱引用。

引用队列可以很容易地实现跟踪不需要的引用。当你在构造WeakReference时传入一个ReferenceQueue对象，当该引用指向的对象被标记为垃圾的时候，这个引用对象会自动地加入到引用队列里面。接下来，你就可以在固定的周期，处理传入的引用队列，比如做一些清理工作来处理这些没有用的引用对象。

WeakHashMap类定义

WeakHashMap当中对于保存key/value的数据结构其实和HashMap是一致的，真正差别的在于Entry<K,V>变量的不同。
Entry是继承自WeakReference类，其构造函数内部通过super(key, queue)方法重新构建了key的对象，这个作用包括key能够被gc回收，同时value也在具体的map的操作类似size()/put()等方法中被回收。
WeakReference的用法可以参见下面的章节或者参考文章，弄懂了WeakReference也就明白了WeakHashMap。

public class WeakHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V> { 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; //存储map的key/value的数据结构 Entry<K,V>[] table; private int size; private int threshold; private final float loadFactor; //用于回收map当中value数据结构的核心queue变量 private final ReferenceQueue<Object> queue = new ReferenceQueue<>(); 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; } } 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); //省略相同代码的判断 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; } } 

WeakHashMap的Entry初始化过程

WeakHashMap本身的构建函数其实跟HashMap是一致的，所以没有需要说明的，核心的Entry才是WeakHashMap的核心实现。
Entry的初始化过程其实逐步通过super()调用到WeakReference进行初始化的，就是说真正放到table当中Entry的key继承了WeakReference从而实现了WeakHashMapkey的可回收，而value的回收是通过ReferenceQueue<Object> queue来实现的。

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; } } public class WeakReference<T> extends Reference<T> { public WeakReference(T referent, ReferenceQueue<? super T> q) { super(referent, q); } } public abstract class Reference<T> { Reference(T referent, ReferenceQueue<? super T> queue) { this.referent = referent; this.queue = (queue == null) ? ReferenceQueue.NULL : queue; } } 

WeakHashMap常用操作

WeakHashMap的回收机制

WeakHashMap的Key使用WeakReference进行包装，垃圾回收器会帮你来决定引用的对象何时回收并且将对象从内存移除。
构造WeakReference的时候我们传入了ReferenceQueue对象super(key, queue)，当该引用指向的对象被标记为垃圾的时候，这个引用对象会自动地加入到引用队列里面。在WeakHashMap的源码当中执行这个操作的函数是expungeStaleEntries，而且是在WeakHashMap的get/set/size这种操作中嵌入了expungeStaleEntries操作。删除的逻辑就是比较Entry对象是否相等。

WeakHashMap的put操作

之所以分析put操作是因为在put操作过程中我们可以清晰地看到Entry的创建过程，可以看到通过WeakReference 和ReferenceQueue来对key进行包装，从而保证了key在对象被设置为null的时候可以被自动清除。
在put的过程中可以看到resize()的过程，我们以2倍的长度进行resize，resize的内部操作就是将数据从oldTable拷贝到newTable的过程，中间有一段反向的逻辑应该是为了节省空间猜测。

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); 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; } 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; } } 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 (size >= threshold / 2) { threshold = (int)(newCapacity * loadFactor); } else { expungeStaleEntries(); transfer(newTable, oldTable); table = oldTable; } } 

WeakHashMap的get操作

WeakHashMap的get操作当中也是按照对key进行hash后定位table桶，然后对table进行一轮value的回收，然后在遍历table桶下面所有的元素进行比较返回查找值。

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; } private Entry<K,V>[] getTable() { expungeStaleEntries(); return 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; } } } } 

WeakHashMap迭代器

WeakHashMap迭代器的实现是非常巧妙的，通过只创建一个KeySet对象来完成迭代器的工作，从这点上我们也可以看出来WeakHashMap是线程不安全的。
类KeySet内部通过创建KeyIterator类对象，KeyIterator继承自类HashIterator，内部的hasNext从table的尾部开始往前进行遍历，每次记录上一次遍历的位置从而继续往前遍历。hasNext判断当前的Entry是否为null，如果为null就继续往前遍历。
KeyIterator的next方法负责返回当前Entry的key值并将Entry往下一个Entry进行推进，所以next的分工是往下一个Entry推进，hasNext是table桶整体往前推进。

public Set<K> keySet() { Set<K> ks = keySet; if (ks == null) { ks = new KeySet(); keySet = ks; } return ks; } private class KeySet extends AbstractSet<K> { public Iterator<K> iterator() { return new KeyIterator(); } } private class KeyIterator extends HashIterator<K> { public K next() { return nextEntry().getKey(); } } private abstract class HashIterator<T> implements Iterator<T> { private int index; private Entry<K,V> entry; private Entry<K,V> lastReturned; private int expectedModCount = modCount; private Object nextKey; private Object currentKey; HashIterator() { index = isEmpty() ? 0 : table.length; } public boolean hasNext() { Entry<K,V>[] t = table; while (nextKey == null) { Entry<K,V> e = entry; int i = index; while (e == null && i > 0) e = t[--i]; entry = e; // index从上一个位置开始找起 index = i; if (e == null) { currentKey = null; return false; } nextKey = e.get(); 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; } } 

参考文章

理解Java中的弱引用
Java 集合系列13之 WeakHashMap详细介绍(源码解析)和使用示例