HashMap 源码分析（jdk1.8）

数据迁移

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 里边的代码笔者只用语言很难描述清楚，详细请见上面的数据迁移图

第三次迁移