WeakHashMap

1、简介

1.1 介绍

WeakHashMap 继承于AbstractMap，实现了Map接口。 和HashMap一样，WeakHashMap 也是一个散列表，它存储的内容也是键值对(key-value)映射，而且键和值都可以是null。

不过WeakHashMap的键是“弱键”。在 WeakHashMap 中，当某个键不再正常使用时，会被从WeakHashMap中被自动移除。更精确地说，对于一个给定的键，其映射的存在并不阻止垃圾回收器对该键的丢弃，这就使该键成为可终止的，被终止，然后被回收。某个键被终止时，它对应的键值对也就从映射中有效地移除了。 这个“弱键”的原理呢？大致上就是，通过WeakReference和ReferenceQueue实现的。 WeakHashMap的key是“弱键”，即是WeakReference类型的；ReferenceQueue是一个队列，它会保存被GC回收的“弱键”。实现步骤是： (01) 新建WeakHashMap，将“键值对”添加到WeakHashMap中。 实际上，WeakHashMap是通过数组table保存Entry(键值对)；每一个Entry实际上是一个单向链表，即Entry是键值对链表。 (02) 当某“弱键”不再被其它对象引用，并被GC回收时。在GC回收该“弱键”时，这个“弱键”也同时会被添加到ReferenceQueue(queue)队列中。 (03) 当下一次我们需要操作WeakHashMap时，会先同步table和queue。table中保存了全部的键值对，而queue中保存被GC回收的键值对；同步它们，就是删除table中被GC回收的键值对。 这就是“弱键”如何被自动从WeakHashMap中删除的步骤了。

和HashMap一样，WeakHashMap是不同步的。可以使用 Collections.synchronizedMap 方法来构造同步的 WeakHashMap。

1.2 构造

//构造一个新的，空的 WeakHashMap ，默认的初始容量（16）和负载因子（0.75）。 WeakHashMap() //构造一个新的，空的 WeakHashMap ，具有给定的初始容量和默认负载因子（0.75）。 WeakHashMap(int initialCapacity) //构造一个新的，空的 WeakHashMap与给定的初始容量和给定的负载因子。 WeakHashMap(int initialCapacity, float loadFactor) //构造一个新的 WeakHashMap与指定的地图相同的映射。 WeakHashMap(Map<? extends K,? extends V> m)

1.3 常用方法

void clear() 从这张地图中删除所有的映射。 boolean containsKey(Object key) 如果此映射包含指定键的映射，则返回 true 。 boolean containsValue(Object value) 如果此地图将一个或多个键映射到指定的值，则返回 true 。 Set<Map.Entry<K,V>> entrySet() 返回此地图中包含的映射的Set视图。 void forEach(BiConsumer<? super K,? super V> action) 对此映射中的每个条目执行给定的操作，直到所有条目都被处理或操作引发异常。 V get(Object key) 返回到指定键所映射的值，或 null如果此映射包含该键的映射。 boolean isEmpty() 如果此地图不包含键值映射，则返回 true 。 Set<K> keySet() 返回此地图中包含的键的Set视图。 V put(K key, V value) 将指定的值与此映射中的指定键相关联。 void putAll(Map<? extends K,? extends V> m) 将指定地图的所有映射复制到此地图。 V remove(Object key) 如果存在，则从此弱散列映射中删除密钥的映射。 void replaceAll(BiFunction<? super K,? super V,? extends V> function) 将每个条目的值替换为对该条目调用给定函数的结果，直到所有条目都被处理或该函数抛出异常。 int size() 返回此地图中键值映射的数量。 Collection<V> values() 返回此地图中包含的值的Collection视图。

1.4 继承关系

java.lang.Object ↳ java.util.AbstractMap<K, V> ↳ java.util.WeakHashMap<K, V> public class WeakHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V> {}

1.5 类图

2、源代码

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; //实际存放数据的数组 Entry<K,V>[] table; //增长临界值 private int threshold; //清除元素的引用队列 private final ReferenceQueue<Object> queue = new ReferenceQueue<>(); //新建节点数组 private Entry<K,V>[] newTable(int n) { return (Entry<K,V>[]) new Entry<?,?>[n]; } //带初始长度和加载因子的构造 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; //大于initialCapacity的2的幂的数 while (capacity < initialCapacity) capacity <<= 1; 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); } 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); } //key为null，value会被直接回收，所以使用Object代替null private static final Object NULL_KEY = new Object(); //扰动函数，使key分布更均匀 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); } //根据key计算桶位置 private static int indexFor(int h, int length) { return h & (length-1); } //从table中删除被垃圾回收的节点 //Entry的key关联ReferenceQueue，key被回收后将放入queue 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; } } } } //返回table private Entry<K,V>[] getTable() { //删除被回收的元素 expungeStaleEntries(); return table; } //根据key获取value public V get(Object key) { //构建key Object k = maskNull(key); //计算key的hash值 int h = hash(k); //获取最新的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; } //是否包含key public boolean containsKey(Object key) { return getEntry(key) != null; } //根据key获取节点 Entry<K,V> getEntry(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 && !(e.hash == h && eq(k, e.get()))) e = e.next; return e; } //添加新的元素 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) { //如果key相同 替换value 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); //如果元素个数大于临界值 扩展为原容量*2 if (++size >= threshold) resize(tab.length * 2); return null; } //扩展 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. */ //如果垃圾回收导致元素个数不及threshold/2，则将元素还原为就table，防止占用过多的内存 if (size >= threshold / 2) { threshold = (int)(newCapacity * loadFactor); } else { 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) { 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; } } } //移除元素 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; //如果key相同 则删除 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; } //移除一个元素 boolean removeMapping(Object o) { if (!(o instanceof Map.Entry)) return false; Entry<K,V>[] tab = getTable(); Map.Entry<?,?> entry = (Map.Entry<?,?>)o; Object k = maskNull(entry.getKey()); int h = hash(k); 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 && e.equals(entry)) { modCount++; size--; if (prev == e) tab[i] = next; else prev.next = next; return true; } prev = e; e = next; } return false; } //清除所有元素 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++; //填充为null 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. //将table填充为null后，会有一波回收 while (queue.poll() != null) ; } //是否包含value 将进行全表查找 很耗时 public boolean containsValue(Object value) { if (value==null) return containsNullValue(); Entry<K,V>[] tab = getTable(); for (int i = tab.length; i-- > 0;) for (Entry<K,V> e = tab[i]; e != null; e = e.next) if (value.equals(e.value)) return true; return false; } //节点类 继承自WeakReference 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. */ //构造将传进一个ReferenceQueue对象 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(); } } //迭代器 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; /** * Strong reference needed to avoid disappearance of key * between hasNext and next */ private Object nextKey; /** * Strong reference needed to avoid disappearance of key * between nextEntry() and any use of the entry */ 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 = 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; } /** The common parts of next() across different types of iterators */ 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; } } //key集 public Set<K> keySet() { Set<K> ks = keySet; if (ks == null) { ks = new KeySet(); keySet = ks; } return ks; } //value集 public Collection<V> values() { Collection<V> vs = values; if (vs == null) { vs = new Values(); values = vs; } return vs; } //Entry集 public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es = entrySet; return es != null ? es : (entrySet = new EntrySet()); } }

2.2 遍历

public static void main(String[] args) { WeakHashMap map = new WeakHashMap(); Object key, value; //元素集 推荐 Iterator iter = map.entrySet().iterator(); while(iter.hasNext()) { Map.Entry entry = (Map.Entry)iter.next(); key = (String)entry.getKey(); value = (Integer)entry.getValue(); } //key集 Iterator iterKey = map.keySet().iterator(); while (iterKey.hasNext()) { key = (String)iterKey.next(); // 根据key，获取value value = (Integer)map.get(key); } //value集 Collection c = map.values(); Iterator iterVal= c.iterator(); while (iter.hasNext()) { value = iter.next(); } }

2.3 总结

WeakHashMap与jdk1.7的hashmap类似，长度都为2的次方数组加链表形式

WeakHashMap的Entry继承自WeakReference且key是弱引用，并关联一个ReferenceQueue。因为key是弱引用，jvm进行一次gc时，会回收key，并将Entry放入ReferenceQueue。queue.poll()弹出Entry，WeakHashMap从table中找到弹出的Entry并删除。此时这个Entry将被彻底回收。(Entry继承自WeakReference条件很重要，删除主要在expungeStaleEntries())

WeakHashMap的key可以为null

参考： http://www.cnblogs.com/skywang12345/p/3311092.html http://blog.csdn.net/kjfcpua/article/details/8495199 http://blog.csdn.net/u012332679/article/details/57489179