WeakHashMap 是一种非凡的 HashMap,它的 key 为 WeakReference 弱援用,并且内置了一个 ReferenceQueue 用于存储被回收的弱援用。浏览 WeakHashMap 源码之前,须要先了解 Reference 和 ReferenceQueue 的机制。了解其基本原理之后,能够应用 HashMap 达到跟 WeakHashMap 一样的成果,文末提供了示例。
1. Reference
public abstract class Reference<T>
extends Object
Reference 是援用对象的形象基类。此类定义了罕用于所有援用对象的操作。因为援用对象是通过与垃圾回收器的密切合作来实现的,所以不能间接为此类创立子类。
Reference 继承构造
继承构造如下:
Reference 与 GC 的交互
在 Reference 实例所治理的对象被垃圾回收器检测为不可达时,垃圾回收器会把该 Reference 增加到 pending-Reference 列表中,这是一个十分轻量级的操作。同时,Reference 实例会默认启动一个 ReferenceHandler 守护线程,不停地尝试从 pending-Reference 列表中获得被回收的 Reference 实例。当获取胜利时,ReferenceHandler 线程会把该 Reference 存入 ReferenceQueue 队列。
Reference 的构造函数
Reference 是一个抽象类,须要由子类来调用其构造方法。
入参 referent 是须要被 GC 非凡看待的对象,入参 queue 是 ReferenceQueue 援用队列实例,默认为 ReferenceQueue.NULL。
Reference(T referent) {this(referent, null);
}
Reference(T referent, ReferenceQueue<? super T> queue) {
this.referent = referent;
this.queue = (queue == null) ? ReferenceQueue.NULL : queue;
}
Reference 的属性
private T referent; // Reference 实例治理的对象,会被 GC 非凡看待
volatile ReferenceQueue<? super T> queue; // Reference 实例治理的对象被回收后,Reference 实例会被增加到这个队列中
/* When active: NULL
* pending: this
* Enqueued: 队列中的下一个援用(如果是最初一个,则为 this)* Inactive: this
*/
@SuppressWarnings("rawtypes")
Reference next; // ReferenceQueue 队列的下一个援用
/* When active: 由垃圾回收器治理的已发现的援用列表的下一个元素(如果是最初一个,则为 this)* pending: pending-Reference 列表中的下一个元素(如果是最初一个,则为 null)* otherwise: NULL
*/
transient private Reference<T> discovered; // pending-Reference 列表的指针,由 JVM 应用
/* 用于管制垃圾回收器操作的锁,垃圾回收器开始一轮垃圾回收前要获取此锁。* 所有占用这个锁的代码必须尽快实现,不能生成新对象,也不能调用用户代码。*/
static private class Lock { }
private static Lock lock = new Lock();
/* pending-Reference 列表,存储期待进入 ReferenceQueue 队列的援用。* 垃圾回收器向该列表增加元素,而 Reference-handler 线程向该列表移除元素。* 操作 pending-Reference 列表须要应用 lock 对象。* pending-Reference 列表应用 discovered 指针来拜访元素。*/
private static Reference<Object> pending = null; // pending-Reference 列表的头结点
Reference 的状态
Reference 实例具备四种状态:
- Active:新创建的 Reference 实例为 Active 状态。当垃圾回收器检测到 Reference 中治理的对象为不可达时,如果该 Reference 实例注册了队列,则进入 Pending 状态,否则进入 Inactive 状态。
- Pending:在 pending-Reference 列表中的元素,期待 Reference-handler 线程将其存入 ReferenceQueue 队列。未注册的实例不会达到这个状态。
- Enqueued:在 ReferenceQueue 队列中的元素。当实例从 ReferenceQueue 队列中删除时,进入 Inactive 状态。未注册的实例不会达到这个状态。
- Inactive:一旦实例变为 Inactive (非流动)状态,它的状态将不再更改。
其状态图转换如下:
Reference 类是通过其中的 queue 属性和 next 属性来记录这些状态:
- Active:queue = ReferenceQueue 实例 或 ReferenceQueue.NULL; next = null
- Pending:queue = ReferenceQueue 实例; next = this
- Enqueued:queue = ReferenceQueue.ENQUEUED; next = 队列的下一个节点或 this
- Inactive:queue = ReferenceQueue.NULL; next = this.
ReferenceHandler 线程
Reference 类中定义了动态代码块,用于启动 ReferenceHandler 守护线程,设置优先级最高。
static {ThreadGroup tg = Thread.currentThread().getThreadGroup();
for (ThreadGroup tgn = tg;
tgn != null;
tg = tgn, tgn = tg.getParent());
Thread handler = new ReferenceHandler(tg, "Reference Handler");
/* If there were a special system-only priority greater than
* MAX_PRIORITY, it would be used here
*/
handler.setPriority(Thread.MAX_PRIORITY);
handler.setDaemon(true);
handler.start(); // 启动 ReferenceHandler 守护线程,优先级最高
// provide access in SharedSecrets // 在 SharedSecrets 中提供拜访权限
SharedSecrets.setJavaLangRefAccess(new JavaLangRefAccess() {
@Override
public boolean tryHandlePendingReference() {return tryHandlePending(false);
}
});
}
ReferenceHandler 线程启动之后,在死循环中执行 tryHandlePending 操作。
tryHandlePending 代码流程:
- 从 pending 属性获得 GC 回收时存入 pending-Reference 列表中对象。
- 将 pending 指向 pending-Reference 列表的下一个节点。
- 如果 ReferenceQueue 不为空,则把被回收的对象入队。
java.lang.ref.Reference.ReferenceHandler
private static class ReferenceHandler extends Thread {public void run() {while (true) {tryHandlePending(true);
}
}
}
java.lang.ref.Reference#tryHandlePending
static boolean tryHandlePending(boolean waitForNotify) {
Reference<Object> r;
Cleaner c;
try {synchronized (lock) {if (pending != null) {
r = pending; // GC 回收的时候,会把对象赋值给 pending,这里取的该对象
c = r instanceof Cleaner ? (Cleaner) r : null;
// 从 pending 链中删除 r
pending = r.discovered;
r.discovered = null;
} else {if (waitForNotify) {lock.wait(); // 取不到则休眠
}
// retry if waited
return waitForNotify;
}
}
} catch (OutOfMemoryError x) {Thread.yield(); // 让出线程的 CPU 工夫,这样心愿能删除一些流动援用,应用 GC 回收一些空间
// retry
return true;
} catch (InterruptedException x) {
// retry
return true;
}
// Fast path for cleaners
if (c != null) {c.clean();
return true;
}
ReferenceQueue<? super Object> q = r.queue;
if (q != ReferenceQueue.NULL) q.enqueue(r); // 若援用队列不为空,将对象放入 ReferenceQueue 队列中
return true;
}
2. ReferenceQueue
ReferenceQueue 的属性
static ReferenceQueue<Object> NULL = new Null<>();
static ReferenceQueue<Object> ENQUEUED = new Null<>();
private static class Null<S> extends ReferenceQueue<S> {boolean enqueue(Reference<? extends S> r) {return false;}
}
入队
应用头插法,将援用 r 存入 r.queue 队列中。
java.lang.ref.ReferenceQueue#enqueue
boolean enqueue(Reference<? extends T> r) { /* Called only by Reference class */
synchronized (lock) {
// Check that since getting the lock this reference hasn't already been
// enqueued (and even then removed)
ReferenceQueue<?> queue = r.queue;
if ((queue == NULL) || (queue == ENQUEUED)) { // 校验援用 r 是否曾经存入 ReferenceQueue 之中,或者曾经从 ReferenceQueue 中移除
return false;
}
assert queue == this;
r.queue = ENQUEUED; // 示意援用 r 曾经存入 ReferenceQueue 之中
r.next = (head == null) ? r : head; // 头插法。r.next = 队列的下一个节点
head = r;
queueLength++;
if (r instanceof FinalReference) {sun.misc.VM.addFinalRefCount(1);
}
lock.notifyAll();
return true;
}
}
出队
将头节点出队,设置新的头节点,并将援用 r 的下一个节点指向本身。
java.lang.ref.ReferenceQueue#reallyPoll
@SuppressWarnings("unchecked")
private Reference<? extends T> reallyPoll() { /* Must hold lock */
Reference<? extends T> r = head;
if (r != null) {head = (r.next == r) ?
null :
r.next; // Unchecked due to the next field having a raw type in Reference // 头节点出队
r.queue = NULL; // 示意援用 r 曾经从 ReferenceQueue 中移除
r.next = r; // 自连贯,不便回收
queueLength--;
if (r instanceof FinalReference) {sun.misc.VM.addFinalRefCount(-1);
}
return r;
}
return null;
}
3. WeakReference
在 JDK 1.2 版之前,Java 外面的援用是很传统的定义:如果 reference 类型的数据中存储的数值代表的是另外一块内存的起始地址,就称该 reference 数据是代表某块内存、某个对象的援用。在 JDK 1.2 版之后,Java 对援用的概念进行了裁减,将援用分为强援用(Strongly Reference)、软援用(Soft Reference)、弱援用(Weak Reference)和虚援用(Phantom Reference)4 种,这 4 种援用强度顺次逐步削弱。
- 强援用:无论任何状况下,只有强援用关系还存在,垃圾收集器就永远不会回收掉被援用的对象。
- 软援用:在零碎将要产生内存溢出异样前,会把这些对象列进回收范畴之中进行第二次回收,如果这次回收还没有足够的内存,才会抛出内存溢出异样
- 弱援用:当垃圾收集器开始工作,无论以后内存是否足够,都会回收掉只被弱援用关联的对象
- 虚援用:一个对象是否有虚援用的存在,齐全不会对其生存工夫形成影响,也无奈通过虚援用来获得一个对象实例。为一个对象设置虚援用关联的惟一目标只是为了能在这个对象被收集器回收时收到一个零碎告诉。
WeakReference 的定义
java.lang.ref.WeakReference
public class WeakReference<T> extends Reference<T> {
/**
* Creates a new weak reference that refers to the given object. The new
* reference is not registered with any queue.
*
* @param referent object the new weak reference will refer to
*/
public WeakReference(T referent) {super(referent);
}
/**
* Creates a new weak reference that refers to the given object and is
* registered with the given queue.
*
* @param referent object the new weak reference will refer to
* @param q the queue with which the reference is to be registered,
* or <tt>null</tt> if registration is not required
*/
public WeakReference(T referent, ReferenceQueue<? super T> q) {super(referent, q);
}
}
WeakReference 的应用
/**
* 弱援用:当垃圾收集器开始工作,无论以后内存是否足够,都会回收掉只被弱援用关联的对象
* <p>
* -verbose:gc -Xms20M -Xmx20M -Xmn10M -XX:SurvivorRatio=8
* 堆大小为 20m,其中新生代大小为 10m,依照 1:8 比例调配,Eden 区大小设置为 8m
* 此时存入 8m 大小的变量,间接存入老年代(tenured generation)*/
@Test
public void weakReference() {byte[] allocation01 = new byte[1024 * 1024 * 8];
WeakReference<byte[]> weakReference = new WeakReference<byte[]>(allocation01);
System.out.println("weakReference.get() =" + weakReference.get());// [B@154ebadd
allocation01 = null;// 解除强援用,只留下弱援用
System.out.println("weakReference.get() =" + weakReference.get());// [B@154ebadd
System.gc();
System.out.println("weakReference.get() =" + weakReference.get());// null
}
执行后果:
weakReference.get() = [B@f2a0b8e
[GC (System.gc()) 15209K->9574K(19456K), 0.0209182 secs]
[Full GC (System.gc()) 9574K->1323K(19456K), 0.0239549 secs]
weakReference.get() = null
WeakReference 和 ReferenceQueue 配合应用
@Test
public void referenceQueue() throws InterruptedException {
// 创立一个援用队列
ReferenceQueue referenceQueue = new ReferenceQueue();
/**
* 创立弱援用,此时 Reference 状态为 Active,*/
WeakReference weakReference = new WeakReference(new Object(), referenceQueue);
System.out.println(weakReference);// java.lang.ref.WeakReference@f2a0b8e
System.out.println(weakReference.get());// java.lang.Object@593634ad
/**
* 当 GC 执行后,因为自定了援用队列,Reference 的状态由 Pending 变为 Enqueued
*/
System.gc();
System.out.println(weakReference);// java.lang.ref.WeakReference@f2a0b8e
System.out.println(weakReference.get());// null
/**
* 从队列外面取出该元素,Reference 状态为 Inactive
*/
Reference reference = referenceQueue.remove();
System.out.println(reference);// java.lang.ref.WeakReference@f2a0b8e
System.out.println(reference.get());// null
reference = referenceQueue.poll();
System.out.println(reference);// null
}
for 循环中的援用对象
来看一下非凡的例子。
/**
* -verbose:gc -Xms20M -Xmx20M -Xmn10M -XX:SurvivorRatio=8
*/
@Test
public void weakReferenceInLoop01() throws InterruptedException {ReferenceQueue referenceQueue = new ReferenceQueue();
for (int i = 0; i < 5; i++) {byte[] bytes = new byte[1024 * 1024 * 8]; // 尽管是个强援用,然而下一次循环后就变为不可达!WeakReference<byte[]> weakReference = new WeakReference<byte[]>(bytes, referenceQueue);
}
Reference remove = referenceQueue.remove(1000); // 这里没有失去告诉!System.out.println("remove =" + remove); // null
}
执行后果:
[GC (Allocation Failure) 15241K->9594K(19456K), 0.0025132 secs]
[GC (Allocation Failure) 9594K->9610K(19456K), 0.0010068 secs]
[Full GC (Allocation Failure) 9610K->1328K(19456K), 0.0151334 secs]
[GC (Allocation Failure) 9520K->9520K(19456K), 0.0003440 secs]
[Full GC (Ergonomics) 9520K->1328K(19456K), 0.0055399 secs]
[GC (Allocation Failure) 9520K->9520K(19456K), 0.0002247 secs]
[Full GC (Ergonomics) 9520K->963K(19456K), 0.0068916 secs]
[GC (Allocation Failure) 9156K->9156K(19456K), 0.0003452 secs]
[Full GC (Ergonomics) 9156K->1024K(19456K), 0.0024345 secs]
remove = null
下面的例子有两个留神要点:
- for 循环中的 bytes,尽管是个强援用,然而下一次循环后就变为不可达,因而弱援用会被回收。
- 弱援用被回收,然而 ReferenceQueue 并没有失去告诉。
即便在 java.lang.ref.Reference#tryHandlePending 中打断点,也没有进入。
为什么 ReferenceQueue 没有失去告诉呢,来看下一个例子。
/**
* -verbose:gc -Xms20M -Xmx20M -Xmn10M -XX:SurvivorRatio=8
*/
@Test
public void weakReferenceInLoop02() throws InterruptedException {ReferenceQueue referenceQueue = new ReferenceQueue();
WeakReference[] weakReferences = new WeakReference[10];
for (int i = 0; i < 5; i++) {byte[] bytes = new byte[1024 * 1024 * 8];
WeakReference<byte[]> weakReference = new WeakReference<byte[]>(bytes, referenceQueue);
weakReferences[i] = weakReference;
}
Reference remove = referenceQueue.remove(1000); // 这里失去告诉了!System.out.println("remove =" + remove);
}
执行后果:
[GC (Allocation Failure) 15196K->9597K(19456K), 0.0033007 secs]
[GC (Allocation Failure) 9597K->9629K(19456K), 0.0101304 secs]
[Full GC (Allocation Failure) 9629K->1328K(19456K), 0.0097783 secs]
[GC (Allocation Failure) 9520K->9552K(19456K), 0.0076307 secs]
[Full GC (Ergonomics) 9552K->1536K(19456K), 0.0299183 secs]
[GC (Allocation Failure) 9728K->9760K(19456K), 0.0082721 secs]
[Full GC (Ergonomics) 9760K->1328K(19456K), 0.0051265 secs]
[GC (Allocation Failure) 9520K->9552K(19456K), 0.0004645 secs]
[Full GC (Ergonomics) 9552K->1328K(19456K), 0.0044950 secs]
remove = java.lang.ref.WeakReference@f2a0b8e
这个例子中,for 循环中的 WeakReference 通过赋值给数组,裸露给 for 循环之外了。
如果在 java.lang.ref.Reference#tryHandlePending 中打断点,发现是能够进入断点地位的。
猜想是 JVM 的一种优化伎俩,当 WeakReference 对象自身有关联到强援用时,GC 回收弱援用的时候才会将其存入 pending-Reference 列表,以便后续由 Reference-handler 线程将其存入 ReferenceQueue 队列。
4. WeakHashMap
public class WeakHashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>
WeakHashMap 是以弱键实现的基于哈希表的 Map。在 WeakHashMap 中,当某个 key 不再失常应用时,将主动移除该 Entry。
反对 null 值和 null 键。该类具备与 HashMap 类类似的性能特色,并具备雷同的初始容量(16)和加载因子(0.75)。
像大多数 collection 类一样,该类是不同步的。能够应用 Collections.synchronizedMap 办法来结构同步的 WeakHashMap。
WeakHashMap 的数据结构
WeakHashMap 的存储构造只有(数组 + 链表)。
WeakHashMap 因为应用了弱援用,在 GC 时会回收没有强援用的 key,因而不会存储过多的元素,无需转换成树结构。
数组构造定义如下:
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
Entry<K,V>[] table;
WeakHashMap 中的外部类 Entry 继承了 WeakReference,将 key 交给 WeakReference 治理。
java.util.WeakHashMap.Entry
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;
}
}
定义了属性 ReferenceQueue
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
往 WeakHashMap 中增加元素时,应用 new Entry<>(k, value, queue, h, e)
创立 Entry 条目,传入 ReferenceQueue,具体见 WeakHashMap#put 办法。
put
java.util.WeakHashMap#put
public V put(K key, V value) {Object k = maskNull(key);
int h = hash(k);
Entry<K,V>[] tab = getTable(); // 获取以后 table 数组(获取之前会革除废除的元素)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;
}
流程跟 HashMap#put 相比简化了不少,关注不同的中央:
- WeakHashMap 的构造函数中就创立了数组,而 HashMap 第一次 put 操作才初始化数组。
- getTable() 获取以后数组 table 时,会先革除 Key 已被回收的 Entry,再返回 table。
- 因为桶中没有树结构,定位到桶之后只须要遍历链表即可。
- 链表应用头插法退出新元素。
expungeStaleEntries
expungeStaleEntries()
办法用于革除废除元素,getTable()
、size()
和 resize()
办法都会调用该办法。
基本上 WeakHashMap 的每个办法都会调用 getTable()
,可知 expungeStaleEntries()
是 WeakHashMap 中外围的逻辑。
java.util.WeakHashMap#expungeStaleEntries
private void expungeStaleEntries() {for (Object x; (x = queue.poll()) != null; ) { // 被回收的对象,会由 GC 存入援用队列中
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) { // 遍历链表,删除节点 e
Entry<K,V> next = p.next;
if (p == e) {if (prev == e)
table[i] = next;
else
prev.next = next; // 节点 e 的前一个节点,指向节点 e 的下一个节点,即在链表上解开节点 e
// 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;
}
}
}
}
代码流程:
- 从 ReferenceQueue 中拉取已被 GC 回收的弱援用节点
- 定位该节点在数组中所在桶的地位
- 遍历桶上的链表,删除该节点
resize
当满足 size >= threshold
时,调用扩容办法。
须要留神的是,执行扩容之前,会革除 WeakHashMap 中废除的 Entry,导致 size 变小而达不到扩容阈值。
此时 WeakHashMap 采取先扩容,再将新的 size 与旧的 threshold 进行比照。
若满足 size >= threshold / 2
阐明扩容胜利,更新阈值;否则放弃扩容,把元素迁徙回旧数组。
先扩容又放弃扩容,重复迁徙数组是一个比拟低效的操作。
void resize(int newCapacity) {Entry<K,V>[] oldTable = getTable(); // 扩容之前获取旧数组,该操作会触发革除废除元素,导致 size 变小而达不到扩容阈值
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.
*/
if (size >= threshold / 2) { // 这里放宽了扩容阈值,为原来的一半,目标是防止重复迁徙数组
threshold = (int)(newCapacity * loadFactor); // 扩容实现,更新阈值
} else { // 放弃扩容
expungeStaleEntries(); // 革除废除的元素
transfer(newTable, oldTable); // 迁徙元素至旧数组
table = oldTable;
}
}
WeakHashMap 应用案例
往 WeakHashMap 中存入 10000 个 key 为 1M 大小的元素,循环完结之后查得 WeakHashMap 大小远不到 10000。
@Test
public void weakHashMap() throws InterruptedException {WeakHashMap<Object, Object> map = new WeakHashMap<>();
Object value = new Object();
for (int i = 0; i < 10000; i++) {byte[] bytes = new byte[1024 * 1024]; // 1M
map.put(bytes, value);
}
System.out.println("map.size->" + map.size()); // 609
}
总结一下,WeakHashMap 应用了弱援用作为 key,当 GC 回收时,革除弱援用并将 Entry 存入 WeakHashMap 中内置的 ReferenceQueue 中。
后续 WeakHashMap 的每一步操作都会从 ReferenceQueue 中拉获得到 Entry,并从 WeakHashMap 中删除该 Entry。
依据这一个性,WeakHashMap 很适宜作为缓存应用。
了解了 WeakHashMap 的原理,应用 HashMap 同样能够做到相似的成果。
@Test
public void hashMap() throws InterruptedException {ReferenceQueue referenceQueue = new ReferenceQueue(); // 定义援用队列
Object value = new Object();
HashMap<Object, Object> map = new HashMap<>();
for (int i = 0; i < 10000; i++) {byte[] bytes = new byte[1024 * 1024]; // 1M
WeakReference<byte[]> weakReference = new WeakReference<byte[]>(bytes, referenceQueue);
map.put(weakReference, value); // 应用 WeakReference 作为 Key
}
System.out.println("map.size->" + map.size()); // 10000
Thread thread = new Thread(() -> {
try {
int cnt = 0;
WeakReference<byte[]> k;
while ((k = (WeakReference) referenceQueue.remove(1000)) != null) {map.remove(k); // 从 HashMap 中移除 Entry,达到与 WeakHashMap 一样的成果
}
} catch (InterruptedException e) {// nothing}
});
thread.setDaemon(true);
thread.start();
thread.join();// 主线程须要期待,直到以后线程 thread 沦亡
System.out.println("map.size->" + map.size()); // 远有余 10000
}
5. 参考
- 《深刻了解 Java 虚拟机:JVM 高级个性与最佳实际(第 3 版)》
- Java Development Kit 8 Documentation
- 深刻理解 JDK 中的 Reference
- 死磕 java 汇合之 WeakHashMap 源码剖析
作者:Sumkor
链接:https://segmentfault.com/a/11…