大家好，本篇博文将通过Debug流程分析，带你全面解读HashMap类的底层源码。之前up出过HashSet的源码分析，而HashSet的底层其实就是HashMap，只不过HashSet相当于只使用了HashMap的K（键），而没有使用V（值）罢了。所以，强烈建议各位大佬们在看这篇博文前，先去看一下up之前出的HashSet的源码分析。对于HashMap和HashSet源码分析中相同的部分，up就不会讲那么细了，我们重点要说二者不同的地方。 注意 : ①解读源码需要扎实的基础，比较适合希望深究的同学； ②不要眼高手低，看会了不代表你会了，自己能全程Debug下来才算有收获； ③点击文章的侧边栏目录或者前面的目录可以进行跳转。良工不示人以朴，up所有文章都会适时进行补充完善。大家有问题都可以在评论区讨论交流，或者私信up。 感谢阅读！

二、HashMap简介

HashMap是Map集合体系中使用频率最高的一个实现类。HashMap的方法没有使用synchronized关键字修饰，因此HashMap是线程不同步的。

HashMap属于java.base模块，java.util包下。如下 :

我们再来回顾一下HashMap的类图，如下 :

三、HashMap的底层实现

1° HashMap底层维护了Node类型的数组table，默认为null。HashMap的底层是"数组 + 链表 + 红黑树"的结构。简单来说，即table数组的元素是一个链表，并且在某些条件下会将链表树化为红黑树。如下图所示 :

2° 当创建HashMap对象时，会将加载因子（loadFactor）初始化为0.75。

3° 当我们向table数组中添加一个key-value键值对时，会先根据当前键值对的key得到一个该键值对的hash值(哈希值)，然后在底层将它转化为一个索引值。这个索引值决定该元素在table数组中应该存放的位置。

4°当（table数组中）索引值对应的位置没有元素存在时，直接将当前元素（键值对）加入table数组。

反之，则进行判断，如果当前要添加的键值对的key与该位置处的键值对的key判断为相等，放弃添加该元素，并用新的value值替换掉key对应的旧的value值，返回旧值；如果当前元素的key与已存在元素的key不相等，则继续判断table数组该索引处的元素后面跟着的是一个链表还是一棵红黑树。

5°若判断table数组该索引处的元素是一个链表，则继续判断该链表中的元素有无与当前元素相同的key，若有——放弃添加该key-value键值对，用新的value值替换掉对应的旧的value值，并返回旧值；若无——直接将当前键值对挂载到当前链表的最后面（实现了数组 + 链表的结构）。

若判断table数组该索引处的元素是一棵红黑树，则用红黑树的方法去添加元素。

6°第一次向HashMap集合中添加元素时，底层的table数组会扩容到16，临界值(threshold) = 16 * 0.75 = 12；之后每当table数组中的元素超过临界值时，就要对table数组进行扩容，容量和临界值都扩大2倍，以此类推。
7° 在JDK17.0版本中，如果table数组中某一条链表的元素个数达到或超过了TREEIFY_THRESHOLD（默认是8），并且table数组的长度达到或超过了MIN_TREEIFY_CAPACITY（默认是64），底层就会对该链表进行树化，将其转化为一棵红黑树；否则仍采用数组扩容机制。（JDK8.0同）

四、HashMap的源码解读（断点调试）

0.准备工作 :

up以HashMap_Demo类作为演示类，代码如下 : （main函数第一行设置断点）

packagecsdn.knowledge.api_tools.gather.map;
importjava.util.HashMap;
importjava.util.Map;
/*** @author : Cyan_RA9* @version : 21.0*/publicclassHashMap_Demo {
publicstaticvoidmain(String[] args) {
Mapmap=newHashMap();
map.put("CSDN", "NB");
map.put("Cyan", "Rain");
map.put("CSDN", "YYDS");
System.out.println(map);
    }
}

运行结果 :

1.向集合中添加第一个元素 :

①跳入无参构造。

OK，我们开始Debug！

先跳入HashMap的无参构造，如下图所示 :

可以看到，无参构造的作用是将loadFactor（加载因子）初始为了0.75。

好的，我们跳出构造器。在测试类中我们已经可以看到table数组的请况了，如下 :

可以看到，此时HashMap$Node[] table = null;。

②跳入put方法。

继续，跳入put方法，如下 :

可以看到，IDEA给出了提示信息——key = "CSDN"；并且value值不再是我们在HashSet源码分析中见到的那个PRESENT了，而是"NB"。

put方法的内部又调用了putVal方法，并且传入了5个实参——①hash方法的返回值；②键值对中的key；③键值对中的value；④false（传递给onlyIfAbsent）；⑤true（传递给evict）。

先来看看第一个实参，我们追到hash方法中看看，如下 :

可以看到，hash方法的本质就是根据一个算法来返回键值对中key对应的哈希值。此处key显然不为null，因此会返回三目运算符的"(h = key.hashCode()) ^ (h >>> 16)"部分，这便是计算哈希值的一个算法，就是将int类型变量h 无符号右移16位后又和key的哈希码值进行了异或操作，这里大家不需要深究，了解一下该算法即可。

第二个实参和第三个实参就不用说了吧。至于后两个布尔类型的实参，我们暂时不管他，等用到了再说，只需要知道一个是false一个是true就行。

③跳入putVal方法。

继续，我们跳入putVal方法。同样地，由于putVal方法本身代码很多，up直接把源码给大家放过来，如下 :

finalVputVal(inthash, Kkey, Vvalue, booleanonlyIfAbsent,
booleanevict) {
Node<K,V>[] tab; Node<K,V>p; intn, i;
if ((tab=table) ==null|| (n=tab.length) ==0)
n= (tab=resize()).length;
if ((p=tab[i= (n-1) &hash]) ==null)
tab[i] =newNode(hash, key, value, null);
else {
Node<K,V>e; Kk;
if (p.hash==hash&&                ((k=p.key) ==key|| (key!=null&&key.equals(k))))
e=p;
elseif (pinstanceofTreeNode)
e= ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (intbinCount=0; ; ++binCount) {
if ((e=p.next) ==null) {
p.next=newNode(hash, key, value, null);
if (binCount>=TREEIFY_THRESHOLD-1) // -1 for 1sttreeifyBin(tab, hash);
break;
                    }
if (e.hash==hash&&                        ((k=e.key) ==key|| (key!=null&&key.equals(k))))
break;
p=e;
                }
            }
if (e!=null) { // existing mapping for keyVoldValue=e.value;
if (!onlyIfAbsent||oldValue==null)
e.value=value;
afterNodeAccess(e);
returnoldValue;
            }
        }
++modCount;
if (++size>threshold)
resize();
afterNodeInsertion(evict);
returnnull;
    }

不打紧啊，我们一步一步来看——

首先，定义了几个辅助变量，如下 :

tab数组其实就是table数组的一个替代品，用来做个判断、赋个值啥的，最后还是要看真正存储元素的table数组。

p是一个Node类型的临时变量，其作用和tab一样，就是个替代品，将来可以用它临时保存table数组中某个元素的值，然后拿来做个判断、赋个值啥的。

n和i暂时不用管，用到再说。

接着，有一条独立的if 条件语句，如下 :

它这是问你table数组现在为空吗？那肯定为空啊，啥都没干呢！

因此，要执行这条独立的if 语句中的内容，即将一个不知道什么东西（扩容后的table数组）的长度赋值给了刚刚定义的n变量。"tab = resize()"，显然这是要对table数组进行第一次扩容操作了。

④跳入resize方法。

继续，跳入resize方法，resize方法源码如下 :

finalNode<K,V>[] resize() {
Node<K,V>[] oldTab=table;
intoldCap= (oldTab==null) ?0 : oldTab.length;
intoldThr=threshold;
intnewCap, newThr=0;
if (oldCap>0) {
if (oldCap>=MAXIMUM_CAPACITY) {
threshold=Integer.MAX_VALUE;
returnoldTab;
            }
elseif ((newCap=oldCap<<1) <MAXIMUM_CAPACITY&&oldCap>=DEFAULT_INITIAL_CAPACITY)
newThr=oldThr<<1; // double threshold        }
elseif (oldThr>0) // initial capacity was placed in thresholdnewCap=oldThr;
else {               // zero initial threshold signifies using defaultsnewCap=DEFAULT_INITIAL_CAPACITY;
newThr= (int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);
        }
if (newThr==0) {
floatft= (float)newCap*loadFactor;
newThr= (newCap<MAXIMUM_CAPACITY&&ft< (float)MAXIMUM_CAPACITY?                      (int)ft : Integer.MAX_VALUE);
        }
threshold=newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab= (Node<K,V>[])newNode[newCap];
table=newTab;
if (oldTab!=null) {
for (intj=0; j<oldCap; ++j) {
Node<K,V>e;
if ((e=oldTab[j]) !=null) {
oldTab[j] =null;
if (e.next==null)
newTab[e.hash& (newCap-1)] =e;
elseif (einstanceofTreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve orderNode<K,V>loHead=null, loTail=null;
Node<K,V>hiHead=null, hiTail=null;
Node<K,V>next;
do {
next=e.next;
if ((e.hash&oldCap) ==0) {
if (loTail==null)
loHead=e;
elseloTail.next=e;
loTail=e;
                            }
else {
if (hiTail==null)
hiHead=e;
elsehiTail.next=e;
hiTail=e;
                            }
                        } while ((e=next) !=null);
if (loTail!=null) {
loTail.next=null;
newTab[j] =loHead;
                        }
if (hiTail!=null) {
hiTail.next=null;
newTab[j+oldCap] =hiHead;
                        }
                    }
                }
            }
        }
returnnewTab;
    }

同样地，不打紧啊，👴都出博文了还不给你讲清楚？我们一步一步来看——

首先，还是那老一套（up在HashSet的源码分析中已经讲过），如下 :

将table（ = null ）赋值给了oldTab引用，oldTab，见名知意，oldTable；然后定义了oldCap变量，赋值为0，oldCap见名知意，oldCapacity；接着又定义了oldThr变量，并为其赋值为threshold，threshold此时是为0的，如下图所示 :

oldThr，见名知意，oldThreshold的意思。至于threshold变量（临界值），up在HashSet的源码分析一文中已经讲得很详细了，这里不再赘述。

继续，newCap变量和newThr变量与oldCap，oldThr变量相对，不解释过多。

接着，if条件语句我们不进去，如下 :

else if 语句我们也不进去，如下 :

进入else语句，else 语句中为newCap变量初始化为了16，并且将newThr变量初始化为了16 * 0.75 = 12。如下图所示 :

将newThe变量返回给threshold后，终于要new出新的Node类型的数组，如下 :

执行完这几步后，我们已经可以看到table数组被初始化成功了，如下 :

然后，返回新数组，结束resize方法，如下 :

⑤回到putVal方法。

如下 :

if条件语句中，利用获取到的key的哈希值，根据特定算法可以得到一个索引值i，该索引之当前键值对在table数组中应该存放的位置。显然，此处p不为空，所以会直接将当前键值对包装成Node类型，然后加入到table数组该索引处。后面几个与HashSet源码分析中重复的步骤up就不再啰嗦了。

⑥回到演示类。

回到演示类，此时我们已经可以看到第一个键值对"CSDN"-"NB"已成功加入到了table数组中，如下 :

2.演示put方法对value的替换功能 :

①第二个元素直接加进去。

第二个键值对的key = "Cyan"，它的哈希值肯定与第一个键值对的key（"CSDN"）不同。因此，第二个元素的添加过程与第一个元素一样，这里就不演示了，我们直接把它加进去，如下图所示 :

②跳入putVal方法。

先跳入put方法，如下 :

可以看到，此时我们的key = "CSDN"，value = "YYDS"。key相同，hash方法返回的哈希值就一定相同。

继续，跳入putVal方法，如下 :

可以看到，此时的哈希值2077925与table数组中已经存在的键值对"CSDN=NB"的哈希值一样，那么最后转换成的索引值也会相同。

对于putVal方法中的第二个if语句，因为我们已经在table数组的该索引处添加过"CSDN=NB"的键值对，因此第二个if语句的判断显然不成立，要进入else语句中。

同样地，就和我们在HashSet源码分析中说的一样（具体详解请查看HashSet源码分析一文），最外层的else语句内部，又分为了三种情况——

第一种情况，如果table数组该索引处元素的key与当前元素的key相同，就放弃添加当前键值对。

第二种情况，如果该索引处元素的key与当前元素的key不相同，并且该索引处元素后面跟着的是一棵红黑树，就采用红黑树的方法进行元素的添加。

第三种情况，在不满足前面两种情况的基础上，如果该索引处元素的后面跟着的是一个链表，就要对链表中的元素挨个进行判断，只要链表中的元素出现了与当前元素key相同的情况，就立刻break出去，放弃添加当前元素。

显然，现在符合第一种情况，于是我们来到了三种情况后面的if条件语句，如下 :

e != null显然成立（注意，上面第一种情况中，我们已经将p赋给了e，即e代表table数组中当前存在的元素），注意看内层if 条件语句中的内容，onlyIfAbsent其实就是我们一开始调用putVal方法时传入的第四个实参false，此处加上！就是true。

内层if 中，进行了值的替换，将table数组该索引出的键值对的旧值替换为了当前键值对的新值，最后又返回了旧的值。

③value替换完成。

执行完这个if语句后，我们已经可以看到value的替换，如下图所示 :

可以看到，此时"NB"已经被替换为了"YYDS"。

3.HashMap树化机制的触发 :

〇准备工作。

先简单回顾一下HashMap底层链表转换为红黑树的条件——①table数组的某索引处的链表中，元素的个数达到或超过8个；②table数组本身的长度达到或超过64个。

对于第②个条件其实比较简单，table数组在初始化后，长度 = 16，我们只需要让它再扩容2次，16 ——> 32 ——> 64，就可以了。关键是，对于第一个条件，我们如何才能顺利地把八个元素挂载在table数组的同一索引处？欸，看过up之前HashSet源码分析的带佬们此时就会发出轻蔑的一笑，哼，重写hashCode方法。

没错！还记不记得我们用put方法添加键值对时，底层如何判断它放在table数组的哪儿?答案是先根据键值对的key得到它的哈希值，再根据这个哈希值得到对应的索引值。那这个哈希值是怎么得来的，得到哈希值的算法如下 :

注意看，起决定性作用的是key的哈希码值，因此，只要我们能让key的哈希码值相同，就能轻松将多个元素挂载到同一链表下（当然前提得value不一样）。

所以，我们可以定义一个类，并重写该类的hashCode方法，使其始终返回相同的值。

up以HashMap_Demo2类为演示类，并在其源文件下定义Fruit类。

代码如下 : （main函数第一行设置断点）

packagecsdn.knowledge.api_tools.gather.map;
importjava.util.HashMap;
/*** @author : Cyan_RA9* @version : 21.0*/publicclassHashMap_Demo2 {
publicstaticvoidmain(String[] args) {
HashMaphashMap=newHashMap();
for (inti=0; i<12; ++i) {
hashMap.put(newFruit(), i);
        }
for (Objecto : hashMap.entrySet()) {
System.out.println(o);
        }
    }
}
classFruit {
@OverridepublicinthashCode() {
return400;
    }
@OverridepublicStringtoString() {
return"Fruit{}";
    }
}

运行结果 :

①向table数组中添加8个元素。

进入Debug，利用for循环，先向table数组中添加元素到8个，如下图所示 :

并且，我们可以看到这8个键值对都挂载到了table数组的同一链表下，如下GIF图所示 :

OK，链表树化的第一个条件我们算是轻松满足了。接下来我们只需要让table数组扩容2次，到64的长度，再向集合中添加元素就会树化了。

②将table数组扩容至64。

问题是：怎么让table数组乖乖扩容至64呢？

诶，哪儿来那么多事？人家源码都写得清清楚楚了，如下 :

当我们在某条链表下挂载的元素达到8后，会进入treeifyBin方法进行二次判断，如果table数组当前的长度不够64，就继续调用resize方法进行扩容；直到table数组的长度达到64后才开始树化。（PS : 这些up在HashSet的源码分析中都已经详细讲过，这里给大家再过一下就好）。

所以，我们只要再向table数组中加入两个元素，就可以让table数组扩容到64了，如下GIF图演示 :

③链表树化为红黑树。

目前集合中共有8 + 2 = 10个元素，如下 :

并且我们可以看到，此时table数组中元素的类型是HashMap$Node类型，如下图所示 :

好的，注意看，当我们向集合中添加第11个元素时，就会对元素个数达到或超过8的链表进行树化，如下GIF图所示 :

可以看到，第11个元素添加后，瞬间结点中新增了一些属性，并且table表中元素的类型由HashMap$Node类型转换为了HashMap$TreeNode类型，如下图所示 :

这表示我们这条链表已成功转换成了一棵红黑树。

五、完结撒❀

🆗，以上就是我们HashMap源码分析的全部内容了。这篇文章配合着之前HashSet源码分析的博文一起食用，up保证你轻松拿捏HashMap的底层源码。源码分析中涉及到了红黑树的知识，属于数据结构与算法的内容，up之后会专门出java语言描述的数据结构与算法的系列专栏，到时候我们再深度研讨。感谢阅读！

System.out.println("END------------------------------------------------------------);

java HashMap 源码分析（深度讲解）

一、前言