系列文章：
前言
WeakHashMap类似HashMap是一个基于哈希实现的无序散列表，存储内容是键值对(key-value)，是非线程安全的，但是WeakHashMap的键是弱键。
在WeakHashMap中，当某个键不再正常使用时，将会被自动移除。更精确地说，对于一个给定的键，其映射的存在并不阻止垃圾回收器对该键的回收，这就使该键成为可终止的，然后被回收。回收某个键时，对应的键值对会从映射中有效地移除。因此，该类的行为与其他的 Map 实现有所不同。其定义如下：
public class WeakHashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>
可以看到HashMap继承AbstractMap，实现了Map接口。
那么WeakHashMap是怎么实现这个弱键的呢？WeakHashMap是通过WeakReference和ReferenceQueue实现的，WeakHashMap的key是WeakReference类型的，将WeakReference和ReferenceQueue关联，ReferenceQueue便会保存被GC回收的“弱键”，如下（具体关于Java的四种引用类型见前文Java数据类型）：
-
与
HashMap类似，WeakHashMap是通过数组table保存Entry(键值对)，而每一个Entry是单向链表，Entry类继承WeakReference，新建Entry时，便会把Entry的key和ReferceQueue关联 -
当“弱键”不再被其它对象引用，便会被GC回收时。GC回收该“弱键”时，这个“弱键”也同时会被添加到
ReferenceQueue(queue)队列中 -
当再次操作
WeakHashMap时，如获取size大小，扩容等，会先同步table和queue，table中保存了全部的键值对，而queue中保存被GC回收的键值对，删除table中被GC回收的键值对。
和HashMap一样，WeakHashMap是不同步的。可以使用 Collections.synchronizedMap 方法来构造同步的 WeakHashMap。
本文源码分析基于jdk 1.8.0_121
继承关系
WeakHashMap继承关系
java.lang.Object
|___ java.util.AbstractMap<K,V>
|___ java.util.WeakHashMap<K,V>
所有已实现的接口：
Map<K,V>
关系图
WeakHashMap关系图
-
table是Entry[]型的数组，而Entry其实是个单向链表，所以WeakHashMap的底层实现是由数组和链表实现的，此处的Entry和HashMap中的Node类似，但是Entry继承自WeakReference<Object> -
size是WeakHashMap的实际大小 -
threshold为是否需要调整WeakHashMap的容量的阈值，等于加载因子乘以容量，当size达到threshold时，便对WeakHashMap扩容 -
loadFactor是加载因子 -
modCount是修改WeakHashMap结构的计数值，用来实现fail-fast机制 -
queue用来保存被GC清除的弱引用的键
构造函数
// 带初始容量和加载因子的构造函数
public WeakHashMap(int initialCapacity, float loadFactor)
// 带初始容量的构造函数
public WeakHashMap(int initialCapacity)
// 默认构造函数
public WeakHashMap()
// 包含子Map的构造函数
public WeakHashMap(Map<? extends K, ? extends V> m)
API
void clear()
Object clone()
boolean containsKey(Object key)
boolean containsValue(Object value)
Set<Entry<K, V>> entrySet()
V get(Object key)
boolean isEmpty()
Set<K> keySet()
V put(K key, V value)
void putAll(Map<? extends K, ? extends V> m)
V remove(Object key)
int size()
Collection<V> values()
源码分析
成员变量
// 默认的初始容量是16，必须是2的幂。
private static final int DEFAULT_INITIAL_CAPACITY = 16;
// 最大容量，必须小于2的30次方，初始容量过大将被这个值代替
private static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认加载因子
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 存储数据的Entry[]数组，长度必须是2的幂
// WeakHashMap是采用拉链法实现的，每一个Entry本质上是一个单向链表
Entry<K,V>[] table;
// WeakHashMap的大小，它是WeakHashMap保存的键值对的数量
private int size;
// 阈值用于判断是否需要调整WeakHashMap的容量（threshold=容量*加载因子）
private int threshold;
// 加载因子实际大小
private final float loadFactor;
// HashMap被改变的次数
private transient volatile int modCount;
// 弱引用和ReferenceQueue 联合使用：如果弱引用所引用的对象被垃圾回收，Java虚拟机就会把这个弱引用加入到与之关联的引用队列中
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
构造函数
// 指定“初始容量”和“加载因子”的构造函数
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);
// 找出大于initialCapacity的最小的2的幂
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
// 创建Entry数组
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);
}
定位桶位置
// 与操作 hash值和length-1与操作得到索引值
private static int indexFor(int h, int length) {
return h & (length-1);
}
增加元素
// key-value键值放入WeakHashMap中
public V put(K key, V value) {
// 如果key是null则用NULL_KEY代替
// private static final Object NULL_KEY = new Object();
Object k = maskNull(key);
int h = hash(k);
// 移除内部不用的条目并返回table
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取代旧的value
if (h == e.hash && eq(k, e.get())) {
V oldValue = e.value;
if (value != oldValue)
e.value = value;
return oldValue;
}
}
// 如果key不在WeakHashMap中，则将key-value添加到HashMap中
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;
}
// 将m的元素全部放入WeakHashMap中
public void putAll(Map<? extends K, ? extends V> m) {
int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0)
return;
// 如果当前容量小于目标容量，则进行扩容
if (numKeysToBeAdded > threshold) {
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;
int newCapacity = table.length;
while (newCapacity < targetCapacity)
newCapacity <<= 1;
if (newCapacity > table.length)
resize(newCapacity);
}
// 逐个添加元素到WeakHashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
获取元素
// 获取key对应的value
public V get(Object key) {
Object k = maskNull(key);
// 获取key的哈希值
int h = hash(k);
Entry<K,V>[] tab = getTable();
int index = indexFor(h, tab.length);
Entry<K,V> e = tab[index];
// 在该哈希值索引对应链表上寻找键值等于key的节点的值
while (e != null) {
if (e.hash == h && eq(k, e.get()))
return e.value;
e = e.next;
}
return 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;
}
删除元素
// 删除key对应的键值对
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;
}
resize
// 重新调整WeakHashMap的大小
void resize(int newCapacity) {
Entry<K,V>[] oldTable = getTable();
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 新建一个newTable，旧表的全部元素都添加到其中
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中的全部元素都添加到newTable中
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();
// key为null，则置
if (key == null) {
e.next = null; // Help GC
e.value = null; // " "
size--;
} else {
// 找到e的hash在新数组下对应的索引值
int i = indexFor(e.hash, dest.length);
e.next = dest[i];
dest[i] = e;
}
e = next;
}
}
}
清空无用键值对
// 清空WeakHashMap中无用的键值对
// 因为当WeakHashMap中某个键值对没有引用时，会被GC自动回收，被回收的弱引用key也会被添加到queue中
// 遍历queue中所有key，在table中对应删除该key对应的键值对
private void expungeStaleEntries() {
// 遍历queue中所有key
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;
e.value = null; // Help GC
size--;
break;
}
prev = p;
p = next;
}
}
}
}
Entry数据结构
// 单向链表，继承自WeakReference<Object>
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
V value;
final int hash;
Entry<K,V> next; // 下一个节点
// 构造函数，每构造一个Entry都与queue绑定
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;
}
// 判断两个Entry是否相等
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();
}
}
遍历
假设key和value都是String型
- 根据
entrySet()通过Iterator遍历
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()){
Map.Entry entry = (Map.Entry)iter.next();
key = (String)entry.getKey();
value = (String)entry.getValue();
}
- 根据
keySet()通过Iterator遍历
Iterator iter = map.keySet().iterator();
while(iter.hasNext()){
key = (String)iter.next();
value = (String)map.get(key);
}
- 根据
value()通过Iterator遍历
Iterator iter = map.values().iterator();
while(iter.hasNext()){
value = (String)iter.next;
}
可以发现，遍历WeakHashMap的方法和遍历HashMap的方法完全一致。
网友评论