WeakHashMap
WeakHashMap 能解决什么问题？什么时候使用 WeakHashMap?
1）WeakHashMap 是基于弱引用键实现 Map 接口的哈希表。当内存紧张，并且键只被 WeakHashMap 使用时，垃圾回收器会按需回收键值对。
2）WeakHashMap 支持 null 键和 null 值。
3）WeakHashMap 是线程不同步的，可以通过 {@link Collections#synchronizedMap Collections.synchronizedMap} 方法获取线程同步的 Map。
如何使用 WeakHashMap?
1）可以使用 WeakHashMap 实现热点分代缓存，当内存紧张，并且键只被 WeakHashMap 使用时，垃圾回收器会按需回收键值对。
使用 WeakHashMap 有什么风险？
1）WeakHashMap 读写数据时，都会同步锁住引用队列来删除无效的节点，当 JVM 内存不够而频繁执行垃圾回收时，同步删除操作比较影响性能。
WeakHashMap 核心操作的实现原理？
/**
* 默认初始容量值为 16
*/
private static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
* 最大的容量值，即 bucket 的个数
*/
private static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认的加载因子
*/
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 底层存储键值对的 table
*/
Entry<K,V>[] table;
/**
* 已有键值对总数
*/
private int size;
/**
* 下一次扩容的阈值
*/
private int threshold;
/**
* 加载因子
*/
private final float loadFactor;
/**
* 当弱引用关联的值需要被 GC 垃圾回收时，该弱引用就会被加入到其关联的引用队列中，
* queue 中的对象都是 WeakHashMap 中需要被回收的节点。
*/
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
/**
* 结构化修改的次数，用于实现 Fast-Fail
*/
int modCount;
/**
* WeakHashMap 的键值对继承了 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.
*/
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;
}
}
/**
* 创建一个容量为 16，加载因子为 0.75 的空 WeakHashMap 实例
*/
public WeakHashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 创建一个容量为大于等于 initialCapacity 的最小的 2 的幂，
* 加载因子为 0.75 的空 WeakHashMap 实例
*/
public WeakHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 创建一个容量为大于等于 initialCapacity 的最小的 2 的幂，
* 加载因子为 loadFactor 的空 WeakHashMap 实例
*/
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;
}
// 初始化 table
table = newTable(capacity);
// 写入加载因子
this.loadFactor = loadFactor;
// 写入扩容阈值
threshold = (int)(capacity * loadFactor);
}
/**
* 添加新的键值对
*/
@Override
public V put(K key, V value) {
// mask 键
final Object k = WeakHashMap.maskNull(key);
// 计算哈希值
final int h = hash(k);
// 去除无效的键值对，并返回 table
final Entry<K,V>[] tab = getTable();
// 基于键的哈希值计算目标索引
final int i = WeakHashMap.indexFor(h, tab.length);
// 读取指定的 bucket，并遍历单向链表的所有元素
for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
/**
* 当前节点的哈希值和目标哈希值一致，
* 并且目标键和弱引用键关联的键值相等
*/
if (h == e.hash && WeakHashMap.eq(k, e.get())) {
final V oldValue = e.value;
// 如果新值和旧值不相等，则替换旧值
if (value != oldValue) {
e.value = value;
}
// 返回旧值
return oldValue;
}
}
modCount++;
// 读取 bucket 首节点
final Entry<K,V> e = tab[i];
// 创建新的节点作为 bucket 的首节点，并将原来的单向链表链接在其后
tab[i] = new Entry<>(k, value, queue, h, e);
// 递增元素总个数，如果超出阈值
if (++size >= threshold) {
// 进行双倍扩容
resize(tab.length * 2);
}
// 新增节点返回 null
return null;
}
/**
* 删除 WeakHashMap 中的无效节点，并返回 table
*/
private Entry<K,V>[] getTable() {
expungeStaleEntries();
return table;
}
/**
* 从 table 中删除过时的节点
*/
private void expungeStaleEntries() {
// 同步处理弱引用队列中的所有元素
for (Object x; (x = queue.poll()) != null; ) {
synchronized (queue) {
@SuppressWarnings("unchecked")
final
Entry<K,V> e = (Entry<K,V>) x;
// 计算哈希值
final int i = WeakHashMap.indexFor(e.hash, table.length);
// 读取 bucket 的首节点
Entry<K,V> prev = table[i];
// 暂存前置节点
Entry<K,V> p = prev;
while (p != null) {
// 读取下一个节点
final Entry<K,V> next = p.next;
// 链表中的当前节点就是引用队列中弹出的节点
if (p == e) {
// 当前处理节点是 bucket 首节点
if (prev == e) {
// 更新 bucket 首节点为后置节点
table[i] = next;
} else {
// 前置节点的后置节点更新为处理节点的后置节点
prev.next = next;
}
// 将节点值置空
e.value = null; // Help GC
// 递减元素个数
size--;
break;
}
// 否则处理下一个节点
prev = p;
p = next;
}
}
}
}
void resize(int newCapacity) {
// 读取旧 table
final Entry<K,V>[] oldTable = getTable();
// 读取旧容量
final int oldCapacity = oldTable.length;
// 旧容量达到最大容量
if (oldCapacity == MAXIMUM_CAPACITY) {
// 只更新扩容阈值为 Integer.MAX_VALUE
threshold = Integer.MAX_VALUE;
return;
}
// 创建新 table
final Entry<K,V>[] newTable = newTable(newCapacity);
// 迁移旧 table 中的元素到新 table 中
transfer(oldTable, newTable);
table = newTable;
/*
* 总元素个数 >= 扩容阈值的二分之一
*/
if (size >= threshold / 2) {
// 计算新的阈值
threshold = (int)(newCapacity * loadFactor);
} else {
// 去除无效的节点并将元素迁移回旧 table 中
expungeStaleEntries();
transfer(newTable, oldTable);
table = oldTable;
}
}
/**
* 从 src table 迁移所有的节点到 dest table
*/
private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
// 顺序处理 src table 中的每个 bucket
for (int j = 0; j < src.length; ++j) {
// 读取首节点
Entry<K,V> e = src[j];
// 将其置空
src[j] = null;
// 首节点不为 null，表示当前 bucket 不为空
while (e != null) {
// 读取下一个节点
final Entry<K,V> next = e.next;
// 读取当前节点的键
final Object key = e.get();
// 键为 null，表示已经被回收，则删除该节点
if (key == null) {
e.next = null; // Help GC
e.value = null; // " "
size--;
} else {
// 计算键在新 bucket 中的索引
final int i = WeakHashMap.indexFor(e.hash, dest.length);
// 当前节点的 next 指向新 bucket 的首节点
e.next = dest[i];
/**
* 新 bucket 的首节点更新为当前节点，
* 每次添加节点，新节点都作为 bucket 的首节点加入到单向链表中
*/
dest[i] = e;
}
// 递归处理单向链表的下一个节点
e = next;
}
}
}
/**
* 根据键读取值
*/
@Override
public V get(Object key) {
final Object k = WeakHashMap.maskNull(key);
final int h = hash(k);
final Entry<K,V>[] tab = getTable();
final int index = WeakHashMap.indexFor(h, tab.length);
// 读取 bucket 首节点
Entry<K,V> e = tab[index];
while (e != null) {
// 当前节点键和目标键相等
if (e.hash == h && WeakHashMap.eq(k, e.get())) {
// 读取值
return e.value;
}
e = e.next;
}
// 键不存在返回 null
return null;
}
/**
* 去除无效的节点，并返回粗略的元素总数
*/
@Override
public int size() {
if (size == 0) {
return 0;
}
expungeStaleEntries();
return size;
}
/**
* WeakHashMap 是否为空
*/
@Override
public boolean isEmpty() {
return size() == 0;
}