java HashMap 源码分析（深度讲解）
目录
一、前言
大家好，本篇博文将通过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函数第一行设置断点）
package csdn.knowledge.api_tools.gather.map;
import java.util.HashMap;
import java.util.Map;
/**
* @author : Cyan_RA9
* @version : 21.0
*/
public class HashMap_Demo {
public static void main(String[] args) {
Map map = new HashMap();
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直接把源码给大家放过来，如下 :
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, 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; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(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 key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
不打紧啊，我们一步一步来看——
首先，定义了几个辅助变量，如下 :
tab数组其实就是table数组的一个替代品，用来做个判断、赋个值啥的，最后还是要看真正存储元素的table数组。
p是一个Node类型的临时变量，其作用和tab一样，就是个替代品，将来可以用它临时保存table数组中某个元素的值，然后拿来做个判断 、赋个值啥的。
n和i暂时不用管，用到再说。
接着，有一条独立的if 条件语句，如下 :
它这是问你table数组现在为空吗？那肯定为空啊，啥都没干呢！
因此，要执行这条独立的if 语句中的内容，即将一个不知道什么东西（扩容后的table数组）的长度赋值给了刚刚定义的n变量。"tab = resize()"，显然这是要对table数组进行第一次扩容操作了。
④跳入resize方法。
继续，跳入resize方法，resize方法源码如下 :
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (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>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 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;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<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;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.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;
}
}
}
}
}
return newTab;
}
同样地，不打紧啊，👴都出博文了还不给你讲清楚？我们一步一步来看——
首先，还是那老一套（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函数第一行设置断点）
package csdn.knowledge.api_tools.gather.map;
import java.util.HashMap;
/**
* @author : Cyan_RA9
* @version : 21.0
*/
public class HashMap_Demo2 {
public static void main(String[] args) {
HashMap hashMap = new HashMap();
for (int i = 0; i < 12; ++i) {
hashMap.put(new Fruit(), i);
}
for (Object o : hashMap.entrySet()) {
System.out.println(o);
}
}
}
class Fruit {
@Override
public int hashCode() {
return 400;
}
@Override
public String toString() {
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------------------------------------------------------------);
- 点赞
- 收藏
- 关注作者
评论（0）