大家好，我是小彭。

在之前的文章里，我们聊到了Java标准库中HashMap与LinkedHashMap的实现原理。HashMap是一个标准的散列表数据结构，而LinkedHashMap是在HashMap的基础上实现的哈希链表。

今天，我们来讨论WeakHashMap，其中的“Weak”是指什么，与前两者的使用场景有何不同？我们就围绕这些问题展开。

(相关资料图)

提示：本文源码基于JDK1.2WeakHashMap。

思维导图：

1.回顾HashMap和LinkedHashMap

其实，WeakHashMap与HashMap和LinkedHashMap的数据结构大同小异，所以我们先回顾后者的实现原理。

1.1说一下HashMap的实现结构

HashMap是基于分离链表法解决散列冲突的动态散列表。

1、HashMap在Java7中使用的是“数组+链表”，发生散列冲突的键值对会用头插法添加到单链表中；

2、HashMap在Java8中使用的是“数组+链表+红黑树”，发生散列冲突的键值对会用尾插法添加到单链表中。如果链表的长度大于8时且散列表容量大于64，会将链表树化为红黑树。

HashMap实现示意图

1.2说一下LinkedHashMap的实现结构

LinkedHashMap是继承于HashMap实现的哈希链表。

1、LinkedHashMap同时具备双向链表和散列表的特点。当LinkedHashMap作为散列表时，主要体现出O(1)时间复杂度的查询效率。当LinkedHashMap作为双向链表时，主要体现出有序的特性；

2、LinkedHashMap支持FIFO和LRU两种排序模式，默认是FIFO排序模式，即按照插入顺序排序。Android中的LruCache内存缓存和DiskLruCache磁盘缓存也是直接复用LinkedHashMap提供的缓存管理能力。

LinkedHashMap示意图

2.认识WeakHashMap

2.1WeakReference弱引用的特点

WeakHashMap中的“Weak”指键Key是弱引用，也叫弱键。弱引用是Java四大引用类型之一，一共有四种引用类型，分别是强引用、软引用、弱引用和虚引用。我将它们的区别概括为3个维度：

维度1-对象可达性状态的区别：强引用指向的对象是强可达的，只有强可达的对象才会认为是存活的对象，才能保证在垃圾收集的过程中不会被回收；

维度2-垃圾回收策略的区别：不同的引用类型的回收激进程度不同，

强引用指向的对象不会被回收；

软引用指向的对象在内存充足时不会被回收，在内存不足时会被回收；

弱引用和虚引用指向的对象无论在内存是否充足的时候都会被回收；

维度3-感知垃圾回收时机：当引用对象关联的实际对象被垃圾回收时，引用对象会进入关联的引用队列，程序可以通过观察引用队列的方式，感知对象被垃圾回收的时机。

感知垃圾回收示意图

提示：关于“Java四种引用类型”的区别，在小彭的Java专栏中深入讨论过《说一下Java的四种引用类型》，去看看。

2.2WeakHashMap的特点

WeakHashMap是使用弱键的动态散列表，用于实现“自动清理”的内存缓存。

1、WeakHashMap使用与Java7HashMap相同的“数组+链表”解决散列冲突，发生散列冲突的键值对会用头插法添加到单链表中；

2、WeakHashMap依赖于Java垃圾收集器自动清理不可达对象的特性。当Key对象不再被持有强引用时，垃圾收集器会按照弱引用策略自动回收Key对象，并在下次访问WeakHashMap时清理全部无效的键值对。因此，WeakHashMap特别适合实现“自动清理”的内存活动缓存，当键值对有效时保留，在键值对无效时自动被垃圾收集器清理；

3、需要注意，因为WeakHashMap会持有Value对象的强引用，所以在Value对象中一定不能持有key的强引用。否则，会阻止垃圾收集器回收“本该不可达”的Key对象，使得WeakHashMap失去作用。

4、与HashMap相同，LinkedHashMap也不考虑线程同步，也会存在线程安全问题。可以使用Collections.synchronizedMap包装类，其原理也是在所有方法上增加synchronized关键字。

WeakHashMap示意图

自动清理数据

2.3说一下WeakHashMap与HashMap和LinkedHashMap的区别？

WeakHashMap与HashMap都是基于分离链表法解决散列冲突的动态散列表，两者的主要区别在键Key的引用类型上：

HashMap会持有键Key的强引用，除非手动移除，否则键值对会长期存在于散列表中；

WeakHashMap只持有键Key的弱引用，当Key对象不再被外部持有强引用时，键值对会被自动被清理。

WeakHashMap与LinkedHashMap都有自动清理的能力，两者的主要区别在于淘汰数据的策略上：

LinkedHashMap会按照FIFO或LRU的策略“尝试”淘汰数据，需要开发者重写removeEldestEntry方法实现是否删除最早节点的判断逻辑；

WeakHashMap会按照Key对象的可达性淘汰数据，当Key对象不再被持有强引用时，会自动清理无效数据。

2.4重建Key对象不等价的问题

WeakHashMap的Key使用弱引用，也就是以Key作为清理数据的判断锚点，当Key变得不可达时会自动清理数据。此时，如果使用多个equals相等的Key对象访问键值对，就会出现第1个Key对象不可达导致键值对被回收，而第2个Key查询键值对为null的问题。这说明equals相等的Key对象在HashMap等散列表中是等价的，但是在WeakHashMap散列表中是不等价的。

因此，如果Key类型没有重写equals方法，那么WeakHashMap就表现良好，否则会存在歧义。例如下面这个Demo中，首先创建了指向image_url1的图片Key1，再重建了同样指向image_url1的图片Key2。在HashMap中，Key1和Key2等价，但在WeakHashMap中，Key1和Key2不等价。

Demo

classImageKey{

privateStringurl;

ImageKey(Stringurl){

this.url=url;

}

publicbooleanequals(Objectobj){

return(objinstanceOfImageKey)&&Objects.equals(((ImageKey)obj).url,this.url);

}

}

WeakHashMapmap=newWeakHashMap<>;

ImageKeykey1=newImageKey("image_url1");

ImageKeykey2=newImageKey("image_url2");

//key1equalsTokey3

ImageKeykey3=newImageKey("image_url1");

map.put(key1,bitmap1);

map.put(key2,bitmap2);

System.out.println(map.get(key1));//输出bitmap1

System.out.println(map.get(key2));//输出bitmap2

System.out.println(map.get(key3));//输出bitmap1

//使key1不可达，key3保持

key1=null;

//说明重建Key与原始Key不等价

System.out.println(map.get(key1));//输出null

System.out.println(map.get(key2));//输出bitmap2

System.out.println(map.get(key3));//输出null

默认的Object#equals是判断两个变量是否指向同一个对象：

Object.java

publicbooleanequals(Objectobj){

return(this==obj);

}

2.5Key弱引用和Value弱引用的区别

不管是Key还是Value使用弱引用都可以实现自动清理，至于使用哪一种方法各有优缺点，适用场景也不同。

Key弱引用：以Key作为清理数据的判断锚点，当Key不可达时清理数据。优点是容器外不需要持有Value的强引用，缺点是重建的Key与原始Key不等价，重建Key无法阻止数据被清理；

Value弱引用：以Value作为清理数据的判断锚点，当Value不可达时清理数据。优点是重建Key与与原始Key等价，缺点是容器外需要持有Value的强引用。

类型优点缺点场景Key弱引用外部不需要持有Value的强引用，使用更简单重建Key不等价未重写equalsValue弱引用重建Key等价外部需要持有Value的强引用重写equals

举例1：在AndroidGlide图片框架的多级缓存中，因为图片的EngineKey是可重建的，存在多个EngineKey对象指向同一个图片Bitmap，所以Glide最顶层的活动缓存采用的是Value弱引用。

EngineKey.java

classEngineKeyimplementsKey{

//重写equals

@Override

publicbooleanequals(Objecto){

if(oinstanceofEngineKey){

EngineKeyother=(EngineKey)o;

returnmodel.equals(other.model)

&&signature.equals(other.signature)

&&height==other.height

&&width==other.width

&&transformations.equals(other.transformations)

&&resourceClass.equals(other.resourceClass)

&&transcodeClass.equals(other.transcodeClass)

&&options.equals(other.options);

}

returnfalse;

}

}

举例2：在ThreadLocal的ThreadLocalMap线程本地存储中，因为ThreadLocal没有重写equals，不存在多个ThreadLocal对象指向同一个键值对的情况，所以ThreadLocal采用的是Key弱引用。

ThreadLocal.java

staticclassEntryextendsWeakReference>{

/**ThevalueassociatedwiththisThreadLocal.*/

Objectvalue;

Entry(ThreadLocal>k,Objectv){

super(k);

value=v;

}

//未重写equals

}

3.WeakHashMap源码分析

这一节，我们来分析WeakHashMap中主要流程的源码。

事实上，WeakHashMap就是照着Java7版本的HashMap依葫芦画瓢的，没有树化的逻辑。考虑到我们已经对HashMap做过详细分析，所以我们没有必要重复分析WeakHashMap的每个细节，而是把重心放在WeakHashMap与HashMap不同的地方。

3.1WeakHashMap的属性

先用一个表格整理WeakHashMap的属性：

版本数据结构节点实现类属性Java7HashMap数组+链表Entry（单链表）1、table（数组）2、size（尺寸）3、threshold（扩容阈值）4、loadFactor（装载因子上限）5、modCount（修改计数）6、默认数组容量167、最大数组容量2^308、默认负载因子0.75WeakHashMap数组+链表Entry（单链表，弱引用的子类型）9、queue（引用队列）

WeakHashMap.java

publicclassWeakHashMapextendsAbstractMapimplementsMap{

//默认数组容量

privatestaticfinalintDEFAULT_INITIAL_CAPACITY=16;

//数组最大容量：2^30（高位0100，低位都是0）

privatestaticfinalintMAXIMUM_CAPACITY=1<<30;

//默认装载因子上限：0.75

privatestaticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;

//底层数组

Entry[]table;

//键值对数量

privateintsize;

//扩容阈值（容量*装载因子）

privateintthreshold;

//装载因子上限

privatefinalfloatloadFactor;

//引用队列

privatefinalReferenceQueue

//修改计数

intmodCount;

//链表节点（一个Entry等于一个键值对）

privatestaticclassEntryextendsWeakReference

//Key：与HashMap和LinkedHashMap相比，少了key的强引用

//finalKkey;

//Value（强引用）

Vvalue;

//哈希值

finalinthash;

Entrynext;

Entry(Objectkey,Vvalue,ReferenceQueue

super(key/*注意：只有Key是弱引用*/,queue);

this.value=value;

this.hash=hash;

this.next=next;

}

}

}

WeakHashMap与HashMap的属性几乎相同，主要区别有2个：

1、ReferenceQueue：WeakHashMap的属性里多了一个queue引用队列；

2、Entry：WeakHashMap#Entry节点继承于WeakReference，表面看是WeakHashMap持有了Entry的强引用，其实不是。注意看Entry的构造方法，WeakReference关联的实际对象是Key。所以，WeakHashMap依然持有Entry和Value的强引用，仅持有Key的弱引用。

引用关系示意图

不出意外的话又有小朋友出来举手提问了????????‍♀：

????????‍♀疑问1：说一下ReferenceQueuequeue的作用?

ReferenceQueue与Reference配合能够实现感知对象被垃圾回收的能力。在创建引用对象时可以关联一个实际对象和一个引用队列，当实现对象被垃圾回收后，引用对象会被添加到这个引用队列中。在WeakHashMap中，就是根据这个引用队列来自动清理无效键值对。

????????‍♀疑问2：为什么Key是弱引用，而不是Entry或Value是弱引用？

首先，Entry一定要持有强引用，而不能持有弱引用。这是因为Entry是WeakHashMap内部维护数据结构的实现细节，并不会暴露到WeakHashMap外部，即除了WeakHashMap本身之外没有其它地方持有Entry的强引用。所以，如果持有Entry的弱引用，即使WeakHashMap外部依然在使用Key对象，WeakHashMap内部依然会回收键值对，这与预期不符。

其次，不管是Key还是Value使用弱引用都可以实现自动清理。至于使用哪一种方法各有优缺点，适用场景也不同，这个在前文分析过了。

3.2WeakHashMap如何清理无效数据？

在通过put/get/size等方法访问WeakHashMap时，其内部会调用expungeStaleEntries方法清理Key对象已经被回收的无效键值对。其中会遍历ReferenceQueue中持有的弱引用对象（即Entry节点），并将该结点从散列表中移除。

privatefinalReferenceQueue

//添加键值对

publicVput(Kkey,Vvalue){

...

//间接expungeStaleEntries

Entry[]tab=getTable;

...

}

//扩容

voidresize(intnewCapacity){

//间接expungeStaleEntries

Entry[]oldTable=getTable;

...

}

//获取键值对

publicVget(Objectkey){

...

//间接expungeStaleEntries

Entry[]tab=getTable;

...

}

privateEntry[]getTable{

//清理无效键值对

expungeStaleEntries;

returntable;

}

//->清理无效键值对

privatevoidexpungeStaleEntries{

//遍历引用队列

for(Objectx;(x=queue.poll)!=null;){

//疑问3：既然WeakHashMap不考虑线程同步，为什么这里要做加锁，岂不是突兀？

synchronized(queue){

Entrye=(Entry)x;

//根据散列值定位数组下标

inti=indexFor(e.hash/*散列值*/,table.length);

//遍历桶寻找节点e的前驱结点

Entryprev=table[i];

Entryp=prev;

while(p!=null){

Entrynext=p.next;

if(p==e){

//删除节点e

if(prev==e)