数据迁移
loHead = e;
9
loTail
(e = p.next) == null
if
hiTail =null
loHead
final int hash；
最大容量 即 2的30 次幂
loadFactor <= 0 || Float.isNaN(loadFactor)
1、申明临时变量 h。2、判断 key 是否为 null，如果键为空，那么它的 hash 值为 0。3、如果 key 不为空，那么用临时变量· h 保存 key的 hashCode，然后跟 h 无符号右移 16位做异或运算，得到一个 hash 值并返回。PS: 一些初学者认为， HashMap 中计算的 hash 值就是键 key 的 hashCode 的返回值，这个说法是有误的， HashMap 实际上做了一个 二次扰动，目的就是为了让数据变得更加散列，减少 Hash 碰撞
true
hash : 4
A
初始化数组，默认长度为 1左移4位，即 16
如果寻找到的桶中已经存在 Node ，则开始树化
!onlyIfAbsent || oldValue == null
else if
D
初始化数组或数组扩容
hiHead
判断 key 的 hash 值是否相等以及 key的equals是否相等
再次判断，是 hash 冲突还是真的需要覆盖旧值
hiTail
寻址，e.hash & (newCap - 1)
e instanceof TreeNode
map的 size是否大于扩容阈值
判断是否红黑数
低位链表头
判断初始值是否大于了 HashMap 的最大容量
进入 else ，表示与桶头的Hash值产生冲突，需要覆盖或者以链表形式挂载到链表尾部
将低位链表的 next 节点设置为 null
hash扰动函数，计算 hash 值，得到的hash 值会在构造 Node（Entry） 对象的时候，作为构造参数传入
如果旧值容量大于数组允许最大值 2 的 30次方，就设置为最大值，这里一般为false
resize（）
5
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
桶里已经存在了数据
false
newTab[j + oldCap] = hiHead;
是否为红黑树
原始数组长度：如果原始数组为空，则数组容量（旧值）设置为 0，否则为原始数组长度
float ft = (float)newCap * loadFactor;
initialCapacity < 0
13
当链表长度大于 8，转红黑树（这只是树化的其中一个条件，还需满足 数组长度大于 64）
afterNodeInsertion(evict);
判断新的扩容阈值是否等于 0
newTab[j] = loHead;
e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))
e != null
(newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
Author：helloworld
else
E
this.threshold = tableSizeFor(initialCapacity);
判断高位、低位链表。用当前原元素的 hash 值与 旧数组长度做 & 运算，如果为0，元素位置在扩容后数组中的位置没有发生改变（低位），如果不为0，元素位置在扩容后数组中的位置发生了改变，新的下标位置是（原下标位置+原数组长）
第一次迁移
作者 QQ，微信点击头像
(n - 1) & hash为什么 HashMap 这里使用 & 运算，并非使用 hash 值对桶的长度减 1 取模？因为 & 运算操作的是二进制，效率会比取模运算快很多
0
判断 e 的 next 节点是否为 null，为 null 表示桶里只有一个数据
oldTab != null
hash : 12
return oldTab
B
threshold = newThr;
判断数组是否为空 || 数组长度是否为 0
hiTail != null
如果 key 已经存在且不是 Hash 冲突所导致位置相同
7
tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY
原始数组：用 oldTab 保存原始的数组 table
threshold = Integer.MAX_VALUE
this.loadFactor = DEFAULT_LOAD_FACTOR;
hiHead = null
e.next == null
这里读者或许会有疑问，原来的位置 +旧数组长度，会不会超出了新数组长度，造成数组越界？回顾一下：1、能够进入这个方法，表明数组已经是被创建了，旧数组长度不会是 0 。resize 做的是扩容操作而非初始化数组。2、HashMap 的数组每次执行扩容，都是扩容 2 倍，所以， 原来位置 + 旧数组长度 <= 旧数组长度*2 - 1所以不会造成数组越界
在 jdk1.8 的hashMap 中，调用构造方法，hashMap 只是对负载因子、初始容量等属性做初始化工作，并未在底层构建数组
hiHead = e
int threshold;
put 方法结束，如果没有产生覆盖，返回 null 值
将负载因子设置为传入的值
newTab[e.hash & (newCap - 1)] = e;
这里笔者先简单画两个草图对 put 方法以及 HashMap 的数据迁移 做一个简单介绍，之后再从源码级别来解释说明
低位链表尾
设置数组长度新值为默认长度 16
1、扩容就是将旧数组的数据迁移到新数组2、迁移过去的值需要重新计算桶位置，判断依据： e.hash & oldCap（currentNode.hash & 旧数组长度）是否为 0 3、关于位置可以这样理解：假设扩容前的数组为旧数组，长度8、新数组长度16。 旧数组位置4有6个数据，假如前三个 Node 的hash值是一样的，后面的三个 Node 的hash值是一样的迁移的时候；就需要计算这6个 Node 的存储位置4、如何计算位置？采用低位链表和高位链表； 如果位置4下面的数据 e.hash & oldCap ==0 那么它对应的就是 低位链表 ，也就是数据位置不变，扩容前放那个桶，扩容后还是放那个桶 e.hash & oldCap != 0 就要重写计算他的位置也就是 j + oldCap（4+8）；这个12，就是 高位链表 位置（新数组12位置的桶）
put 方法结束，返回被覆盖的旧值
数组扩容，不会树化
寻址： i = (n - 1) & hash，n 是数组长度，这里求的是要存放的桶的位置，及数组下标
进入 else ，表示当前循环到的桶里存放的是链表，后边代码都是对链表做数据迁移
HashMap 中 K-V 的实时数量，中间状态数据
resize()
14
当链表长度小于 6 ，红黑树转回链表
C
如果 e 为空，说明只是 hash 值冲突，并非 key 相同，需要走下面的流程，主要是再次判断链表是否需要树化，数组是否需要扩容
高位链表头
只有第一次调用 put 方法才能进入 else
将新的数组长度设置为旧的扩容阈值
p = e;
HashMap() # 无参构造方法
hiTail.next = null;
(tab = table) == null || (n = tab.length) == 0
next = e.next;
接下来，笔者会从宏观和微观上分析 HashMap 底层原理，解决上述问题，源码尽可能地精确到每一行。
initialCapacity > MAXIMUM_CAPACITY
2
进入 else 表示，桶里边已经存在了数据，接下来就要判断是否覆盖
申明临时变量 e，在循环中保存数组中的每一个桶
return oldValue
数组长度大于 64，且链表长度大于 8 ，链表转红黑树
static final int MIN_TREEIFY_CAPACITY = 64;
p instanceof TreeNode
onlyIfAbsent 是 putVal 方法参数，默认为 false（源码已经写死），所以不论 oldValue 是否为 null，这个判断一定会进入
TREEIFY_THRESHOLD 链表树化阈值 ，判断是否将链表树化，链表长度如果>8转红黑树（or 扩容）减 1是因为binCount 是从 0 开始计算
break 直接跳出循环
initialCapacity = MAXIMUM_CAPACITY;
创建 or 追加链表
根据寻址公式，判断寻找到的桶是否为空
return oldValue;
旧的数组长度扩容两倍得到新的数组长度，判断新的数组长度是否小于最大值 且 旧的数组长度大于等于默认的数组长度 16
table = newTab;
hiTail == null
(e = tab[index = (n - 1) & hash]) != null
binCount >= TREEIFY_THRESHOLD - 1
这里证明了，第一次调用 put 方法，HashMap 才会开辟一块内存空间存放 Node 节点，并不是 new HashMa 就会创建
transient int size;
第一次调用 resize 方法，是创建数组，所以第一次put ，oldTab 等于null，在此之后调用 resize()，是对旧数组扩容，此时 oldTab 才不为空。这个判断里执行的代码，就是处理数组扩容后数据迁移的问题，也是 HashMap 中重要的知识点
此时 oldCap 旧数组长度不大于 0 ，判断旧的扩容阈值是否大于 0，第一次调用 put 方法，threshold =0，所以 oldThr 也等于0，无法进入判断
HashMap 中的重要成员
oldCap >= MAXIMUM_CAPACITY
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
第二次迁移
这里可以看出，无参构造就只是将负载因子设置为默认值
F
把旧数组下标为 j 的桶赋值给 e，判断是否为 null，不为 null 表示循环到的桶里有数据
8
创建一个 Node ，即 Map.Entry，在 jdk1.8 后，使用 Node 代替了 Entry
return null
相信各位熟读 HashMap 的大佬，看到这几个问题几乎是脱口而出，不过，还是请各位先背一遍 《HashMap 面试圣经span style=\"font-size: inherit;\
++size > threshold
调用重载构造
设置扩容临界点
hashMap 中数组，中间状态数据，不参与序列化（重点）
假设一个数组长度 8 ，扩容临界点 8*0.75 = 6，扩容后新数组长度为 16，第4个桶存放了6个数据，它们的 hash 值如图
for (int j = 0; j oldCap; ++j)
用来记录HashMap的修改次数 线程不安全
(n - 1) & hash，这个是hashmap 的寻址方法，根据数组长度和 hash 值算出桶的位置，这里就是判断桶里是否已经存在数据
判断是否是红黑树结构
6
默认数组容量 16， 1 左移4位，即 2的4 次幂
e.value = value;
构造阶段
迁移前
tab[i] == null
如果以上的 if 判断都没有进入，将头节点赋值为临时变量 e，此时 e 的值是 p.next，
loTail.next = e;
高位链表尾
(e = oldTab[j]) != null
创建 HashMap 调用 HashMap 构造器，在 jdk 1.8中，仅仅对负载因子进行赋值，默认 0.75，此时并未创建数组。当第一次调用 put方法的时候，1、首先计算 key 的hash值hash 值的计算方法： hash 扰动，如果 key 为 null，则存储位置下标为 0，如果不为 null，用 key 的 hashCode 与 （key 的hashCode右移 16 位后）的值做 ^ 异或运算，得到具体的下标位置，这个位置就是数组下标，即桶的位置。2、判断数组是否为空 或 数组长度是否为 0由于是第一次 put ，数组肯定为空，调用扩数组扩容方法数组扩容1、设置新数组长度和新的扩容阈值if 判断原数组长度是否大于 0第一次调用 put 方法，数组还未创建，所以 oldCap = 0。只有第二次调用扩容方法 resize()，才能进入这个判断，这个判断就时再判断数组长度是否合法，如果合法就将数组长度扩容两倍得到新数组长度，同时将旧扩容阈值扩容两倍，得到新的扩容阈值else if 判断旧的扩容阈值是否大于0如果大于 0 ，则将新数组长度设置为就的扩容阈值else 即数组长度不大于 0，且旧的扩容阈值也不大于0设置数组容量为默认值 16，扩容阈值为 16*负载因子 0.75，即 122、将新的扩容阈值赋值给全局变量 threshold3、根据第一步得到的新数组长度创建一个新的数组，并将新数组长度赋值给成员变量 table4、判断旧数组是否不为 null这个判断只有第一次 put 之后进入，因为第一次旧数组肯定为 null不为 null 循环数组中每一个桶， 如果循环到的桶里只有一个数据，通过寻址公式 e.hash & (newCap - 1)，e表示当前桶里的那个数据，newCap是新数组长度， 如果不止一个数据，判断是否是红黑树结构 如果以上都不是，就表明桶里存在一个链表，就要对链表做数据迁移。 链表数据迁移： 低位链表保持位置不变 高位链表迁移到 新的桶里 （当前桶下标 +新数组长度） 什么是低位链表 高位链表？ 低位链表 e.hash & oldCap ==0 高位链表 e.hash & oldCap != 05、返回新数组2、 if 判断当前位置是否存在数据首先计通过hash 值计算位置，(n - 1) & hash ，n是数组长度，这个得到的是桶的位置，如果不存在数据，直接将数据放入桶中 else 桶里已经存在数据 if 判断当前 put 的 key是否与桶里第一个数据桶头（因为桶里可能存在多个数据组成的链表，这里比较的是链表头，简称桶头）是否相等，如果相等，则表示 key 值是一样的，会覆盖旧值，但是并不会直接覆盖，而是用临时变量 e 暂时保存将桶头 比较规则是 1、桶头的hash值与当前插入数据的key的hash值是否相等，这个条件必须满足，是短路与 2、桶头的 key 与当前插入的数据的 key 是同一内存地址 3、当前插入的数据的 key 不为 null，且这个 key.equals(k) 为 true 2和 3 人已满足其一即可 else if 判断是否是红黑树 else 到达 else ，说明当前插入的数据的 key，与桶头的数据的 key 值出现 hash 冲突，循环链表 1、判断当前链表节点的 next 节点是否为null 如果为null，表名此时已处于链表尾部，说明当前插入的数据没有与链表中的数据产生冲突，也就是要做插入链表操作 创建一个 Node 节点，通过 bitCount 变量的值判断链表是否需要树化，如果达到链表树化阈值 ，再判断数组长度是否达到链表树化阈值（64），如果没有达到，则对数组扩容，调用 resize方法 如果达到了，树化 2、判断当前循环到的链表节点与插入的数据 key 是否冲突，比较规则见上。如果冲突，则表示要覆盖当前循环到的链表节点3、如果需要覆盖，则覆盖旧值，并将旧值返回 如果没有覆盖，而是要做添加操作，添加后判断当前size是否已经达到数组扩容阈值，如果是，则扩容数组，最后再返回 null 值
判断原始数组长度是否大于 0，第一次调用 put 方法，数组还未创建，所以 oldCap = 0。只有第一次以后调用put，才能进入这个判断
用 next 来保存 e 节点的下一个节点，做 while 循环的判断
oldThr > 0
n：用于保存当前数组长度e：寻找到的桶中存放的元素（可能为空）
有参构造
++modCount;
扩容临界点： capacity * loadFactory（容量 *负载因子）
高位链表放到了新数组下标为 j +oldCap 的桶里，也就是放到 原来位置 + 旧数组长度 的桶
负载因子 当达到 75% 时 扩容
11
循环旧数组的每一个桶
如果覆盖旧值，那么 put 方法返回 旧值
将原始数组中下标为 j 的桶设为 null，做 GC 处理
判断桶的位置是否有数据
前段时间微信有个同学说自己对 HashMap 的理解始终就像是背八股文一样 ，被问到总觉得没底气，希望深入每行源码了解 HashMap，于是乎，笔者就简单的画一个，此图基于 JDK1.8。如有错误，请多指教
map 的值
static final int MAXIMUM_CAPACITY = 1 << 30;
loHead ，loTail 低位链表（原位置i）hiHead ，hiTail 高位链表（i+n位置）next：当前链表元素的下一个节点
table就是 HashMap 的底层数组，检测数组，数组是否null或者数组长度等于0，第1次调用put table数组为空，只有第一次调用 put 方法才能进入这个判断
for(int binCount = 0; ; ++binCount)
首先校验构造方法中的两个参数 initialCapacity 初始容量，loadFactor 负载因子是否合法
第五次迁移
static final int UNTREEIFY_THRESHOLD = 6;
空方法，交由 HashMap 的子类 LinkedHashMap 实现， HashMap 本身对这个方法没有做任何操作
扰动后的 hash 值
添加 PUT
oldCap > 0
如果不是覆盖旧值而是添加，需要再判断是否扩容
new HashMap<>(20)
判断当前 hashmap 中存放的数据数量是否已经超过了扩容阈值
int oldThr = threshold;
font color=\"#f44336\
throw new IllegalArgumentException
将刚创建的数组赋给成员 table 数组，能够执行到这行代码，只有第一次调用 put 方法，以及数组需要扩容的情况下，所以需要构建一个新的数组
V oldValue = e.value;
将扩容阈值设置为最大值
binCount 是在统计链表个数，达到树化阈值，将链表转为红黑树
HashMap(int initialCapacity)
如果新阈值为0，根据负载因子设置新的扩容阈值
newCap = DEFAULT_INITIAL_CAPACITY;
newCap = oldThr;
写在前面
判断传入的参数即初始容量值是否小于 0
this.loadFactor = loadFactor;
桶的位置为空，直接插入
1
hiTail = e
newThr = oldThr << 1
如果为 true，则表示 key 值是一样的，会覆盖旧值，但是并不会直接覆盖，而是用临时变量 e 暂时保存将桶头
hiHead
桶里第一个元素 (链表的头)：接下来都简称桶头 桶头 的 hash 值与当前 put 进的 key的hash 相同，且 （当前的 key 与 桶头 的 key 内存地址相同 或者 当前 key 在不为 null 的前提下，key 调用自身 equals 方法与桶头相等）这里就是大家背的滚瓜烂熟的 hash 冲突判断：先比较 hashCode 是否相同（hash 值就是根据 hashCode 计算得出，上面已经提到了），再判断 equlas 方法是否返回 true；
3
static final float DEFAULT_LOAD_FACTOR = 0.75f;
(p = tab[i = (n - 1) & hash]) == null
低位链表放到了新数组下标为 j 的桶里，也就是放到原来的桶，位置保持不变
用一个临时变量保存旧值
第四次迁移
链表
e = p
10
判断当前数组是否为 null 或者数组长度小于树化阈值，这里就可以得出，链表转红黑树需要两个条件：1、链表长度大于等树化阈值 8。2、数组长度大于树化阈值 64
这里只是表明，与桶中第一个元素的hash值冲突，接下来会有两种情况1、如果当前桶里只有一个元素，即只有桶头，那么会生成链表，将当前的新值赋给桶头的 next，形成链表2、如果链表已经存在，就循环将当前的 key 依次与链表中的数据做比较
对每一个链表节点进行覆盖判断，这里的判断与之前桶头的判断一样
int oldCap = (oldTab == null) ? 0 : oldTab.length;
n = (tab = resize()).length
putTreeVal
扩容临界点 （旧值）
桶的位置是空的，构造一个 Node 对象直接插入当前数组位置
do-while ((e = next) != null);
hash 扰动，使 hash 更加散列
将高位链表的 next 节点设置为 null
只有 key 已经在 map 中存在，才能进入这个判断，说明key 相等（而不是Hash冲突所导致桶的位置一样），需要对旧值进行覆盖，而这个 e 如果不为空，那么此时已经是需要被覆盖的 Node 对象
(e.hash & oldCap) == 0
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
扩容2倍:将阈值threshold*2得到新的阈值
loTail != null
如果没有覆盖旧值，那么 put 方法返回 null
final K key;
loTail == null
p.next为空表明处于链表的尾部， 1、生成链表 2、已经是链表都是同样的操作
在阅读之前，请读者先思考一下这几个问题：1、HashMap的底层数据结构是什么 ？2、HashMap 的数组是什么时候创建的？1.7和1.8有何不同 ？3、HashMap中 put 底层原理是什么 ？4、HashMap是如何实现扩容的 ，扩容后数据迁移过程是怎样的 ？5、HashMap是如何解决hash冲突的 ？6、HashMap 链表树化条件 ？7、HashMap 是如何计算Hash 值的 ？8、HashMap 是如何计算桶的位置的 ？........
设置新的扩容阈值为 0.75*16
声明一些临时变量，读者一定一定一定要记住这几个变量方便之后的阅读，之后会频繁使用tab ：保存 table 即 HasMap 底层的 Node（Entry） 数组n: 保存数组长度i: 表示当前 put 的数据要放入的桶的位置，即数组下标p:根据当前 hash 值计算出的桶的位置上存放的数据（可能为空）
第一次调用 put 方法
do while 循环链表·
hash(Object key)
oldTab[j] = null;
用新的value值去覆盖老的value值
PUT 源码分析
hiTail.next = e;
loTail = e;
map 的 key
最后将新的扩容赋值给成员属性
new HashMap<>()
PUT核心流程分析
无参构造
数组扩容
resize()
链表数据迁移源码
迁移后
到这一步，说明 hash 值冲突，需要添加到链表或者覆盖链表中的某一个节点
15
loTail.next = null;
链表下一个节点
static final int TREEIFY_THRESHOLD = 8;
V value;
hiTail
第六次迁移
newThr == 0
申明临时变量，这两个变量也一定要记住！，不然之后会很难阅读e： 用来保存当前桶里的数据，桶里如果是链表，会循环链表中的每一个节点并赋值给这个变量 e，用于判断是否需要覆盖旧值k： 保存桶里已存在的第一个数据的 key值
如果大于，就设置初始容量为1最大容量
第一次调用 put 方法，数组必然为空
负载因子是否小于零 || 是否 Not a Number
返回旧的数组
声明变量，保存数组容量（新值）、扩容临界点（新值）
afterNodeAccess(e);
else 里边的代码笔者只用语言很难描述清楚，详细请见上面的数据迁移图
第三次迁移
