一.HashMap相关信息
1.相关名称含义
Node:哈希表结构中数组的名字(table)
DEFAULT_INITIAL_CAPACITY：数组默认长度16
DEFAULT_LOAD_FACTOR：默认加载因子0.75(用于计算数组扩容的阈值)
2.链表键值对象信息
当数组上的数据仍然是以链表形式存在时适用
int hash;：键的哈希值
final K key;：键
V value;：值
Node：下一个节点的地址值
3.红黑树键值对象信息
当数组上的数据已经从链表转换成红黑树时适用
int hash;：键的哈希值
final K key;：键
V value;：值
TreeNode：父节点的地址值
TreeNode：左子节点的地址值
TreeNode：右子节点的地址值
boolean red;：节点的颜色，true是红色，false是黑色
二.创建HashMap对象
1.实际书写代码：
HashMap hm = new HashMap<>();
2.对应源码：
(1)相关参数
DEFAULT_LOAD_FACTOR：默认加载因子(0.75)
(2)由源码得出结论
这一步没有创建哈希数组，也没有执行什么操作，就是只是指定了加载因子而已。
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
二.添加元素
实际书写代码:
hm.put("aaa" , 111);
第一步：put调putVal
实际书写的put去调用putVal()进行下一步处理
putVal中hash()方法
这是putVal形参hash(key)方法
**作用：**利用键计算出对应的哈希值，再把哈希值进行一些额外的处理
**返回值：**返回值就是键的哈希值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
第二步：进入putVal
这是put里面调用的putVal方法
putVal的形参
- 参数一：键的哈希值
- 参数二：键
- 参数三：值
- 参数四：如果键重复了是否保留
- true，表示老元素的值保留，不会覆盖
- false，表示老元素的值不保留，会进行覆盖
(1) 创建变量
①创建记录哈希表数组(就是挂链表/树那个大数组)地址值的tabNode
**目的：**提高效率，避免重复调用堆内的table(也是记录哈希数组地址值的变量)
②创建临时变量，记录键值对对象的地址值Node
③创建表示数组长度的n以及表示索引的i
Node[] tab;
//临时的第三方变量，用来记录键值对对象的地址值
Node p;
//表示当前数组的长度
int n;
//表示索引
int i;
//把哈希表中数组的地址值，赋值给局部变量tab
tab = table;
(2) 使用if判断并调用resize方法
**作用：**就是用来创建和扩容数组的
① if判断
判断当前数组是否为空(tab复制了哈希表地址值，见上)
- 为空，直接调用resize方法(一般只会出现在第一次添加元素时)
- 不为
null(没数组)，将n赋值成当前数组长度n = tab.length，使n有值了，并判断其长度是否为0
if (tab == null || (n = tab.length) == 0){}
② 调用resize方法(无论是否是空都会调)
**主要作用：**①创建数组，并将地址值赋值给table，将计算出来的扩容时机赋值给threshold
②判断是否需要扩容
resize方法的处理：
1.如果当前是第一次添加数据，底层会创建一个默认长度为16，加载因子为0.75的数组 2.如果不是第一次添加数据，会看数组中的元素是否达到了扩容的条件
- 如果没有达到扩容条件，底层不会做任何操作
- 如果达到了扩容条件，底层会把数组扩容为原先的两倍，并把数据(链表、树)全部转移到新的哈希表中
- 将
resize()的返回值赋值给tab变量(resize创建数组) - 将
resize()中创建的哈希数组长度赋值给n
if (tab == null || (n = tab.length) == 0){
tab = resize();
//第一次调用：表示把当前数组的长度赋值给n -> 16
n = tab.length;
}
三.进行数据添加
1.计算存入位置
通过哈希值与数组长度进行计算，求出当前键值对对象应在数组中存入的位置
i = (n - 1) & hash;//i可以理解为index
2.从计算位置处读取数据
获取数组中对应元素的数据(Tab已经记录Node的地址值了，Tab[i]相当于调用计算位置的数据）
p = tab[i];
3.判断计算位置有无数据
添加元素情况出现分离的地方⭐
if (p == null){
}else{}
(1)为空(null)
这可情况会出现在计算位置恰好没有数据的时候。
① 底层创建对象放入数组
此时底层会直接创建一个键值对对象，然后放入数组中
if (p == null){
//底层会创建一个键值对对象，直接放到数组当中
tab[i] = newNode(hash, key, value, null);
}else {.....}
② 判断是否需要扩容
**注：**threshold：表示数组长度 * 0.75.就是扩容的阈值
**例如：**第一次调用resize(),创建的数组长度是16，则threshold = 16 * 0.75 =12
先++size，将当前添加元素造成的长度变化更新，在与threshold进行比较，当数组长度大于threshold时，就执行扩容(调用resize())
if (++size > threshold){
resize();
}
③ 直接走到最后null
因为这是第一次添加元素，当前没有覆盖任何元素，直接返回null
(2)非空，键不重复
① 不符合if进入else
Ⅰ.相关参数说明：
-
p.hash:这里面的p就是前面（三.2）读取数据中记录获取数据地址值的那个p,所以p.hash就是位置处那个元素的哈希值 -
hash:这个单纯的哈希变量，出现在下面的比较中，这个就是当前添加键值对的哈希值啦
Ⅱ.过程：
①先if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){}
拆分(只分析涉及此次前提元素的东西)
Ⅰ.p.hash == hash，就是比较当前要添加的键位对哈希值是否等于计算出键位对的哈希值(判断是否为一个元素)
- 如果键不一样，此时返回false(此刻我们是这里，因为我们键位不重复)
- 如果键一样，返回true
Ⅱ.由上，p.hash == hash结果为false,因为是&&符号，所以if判断句整体为false,进入else
②进入else判断
Ⅰ.else if (p instanceof TreeNode){}判断数组中获取出来的键值对是不是红黑树中的节点.
- 如果是，则调用方法putTreeVal，把当前的节点按照红黑树的规则添加到树当中。
- 不是，进入下一个else(这里的情况)
Ⅱ.根据上面的结果，进入最后一个else,这个是判断是不是链表的（这里我们是）
进入这个判断
i.定义binCount变量，赋值为0，先自增
ii.比较当前位置的是否存在下一个元素,并在此时完成对e的赋值(是否为null)
-
null:直接创建结点并挂到它下面 -
!null:进行判断，判断当前是否满足条件转为红黑树(这里不满足，直接跳出了for循环以及else，进入下一个if)
iii.判断下一个元素的哈希值是否等于被添加元素
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
break;
}
- 满足则跳出循环，进入到else外面
if (e != null) {}进行替换判断 - 不满足不进入if执行下一个
p = e;，然后再循环一次(就是这个操作使得结点可以一个个向下找空位置) -
else {
//如果从数组中获取出来的键值对不是红黑树中的节点
//表示此时下面挂的是链表
for (int binCount = 0; ; ++binCount) {
//获取下一个结点，并判断其是否为null
if ((e = p.next) == null) {
//为null表示其没有下一个结点，此时就会创建一个新的节点，直接挂在下面形成链表
p.next = newNode(hash, key, value, null);
//判断当前链表长度是否超过8，如果超过8，就会调用方法treeifyBin
//treeifyBin方法的底层还会继续判断
//判断数组的长度是否大于等于64
//如果同时满足这两个条件，就会把这个链表转成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//e： 0x0044 ddd 444
//要添加的元素： 0x0055 ddd 555
//如果哈希值一样，就会调用equals方法比较内部的属性值是否相同
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
break;
}
p = e;
}
}
② 判断e进入覆盖循环
- 如果e为null，表示当前不需要覆盖任何元素
- 如果e不为null，表示当前的键是一样的，值会被覆盖
i.这里是Null直接跳过
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null){
//等号的右边：当前要添加的值
//等号的左边：0x0044的值
e.value = value;
}
afterNodeAccess(e);
return oldValue;//返回被替换的元素
}
③ 判断是否需要扩容
**注意：**threshold：表示数组长度 * 0.75.就是扩容的阈值
**例如：**第一次调用resize(),创建的数组长度是16，则threshold = 16 * 0.75 =12
先++size，将当前添加元素造成的长度变化更新，在与threshold进行比较，当数组长度大于threshold时，就执行扩容(调用resize())
if (++size > threshold){
resize();
}
④ 直接走到最后null
因为这是第一次添加元素，当前没有覆盖任何元素，返回null
return null;
(3)数组位置不为null，键重复，元素覆盖
① 不符合if进入else
①先if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){}
拆分(只分析涉及此次前提元素的东西)
Ⅰ.p.hash == hash，就是比较当前要添加的键位对哈希值是否等于计算出键位对的哈希值(判断是否为一个元素)
- 如果键不一样，此时返回false(此刻我们是这里，因为我们键位不重复)
- 如果键一样，返回true
Ⅱ.由上，p.hash == hash结果为false,因为是&&符号，所以if判断句整体为false,进入else
②进入else判断
Ⅰ.else if (p instanceof TreeNode){}判断数组中获取出来的键值对是不是红黑树中的节点.
- 如果是，则调用方法putTreeVal，把当前的节点按照红黑树的规则添加到树当中。
- 不是，进入下一个else(这里的情况)
Ⅱ.根据上面的结果，进入最后一个else,这个是判断是不是链表的（这里我们是）
进入这个判断。
i.定义binCount变量，赋值为0，先自增
ii.比较当前位置的是否存在下一个元素,并在此时完成对e的赋值(是否为null),是执行这里的操作【我们是这里】
- 直接创建结点并挂到它下面
- 进行判断，判断当前是否满足条件转为红黑树(这里不满足，直接跳出了for循环以及else，进入下一步)
ii.比较当前位置的是否存在下一个元素,并在此时完成对e的赋值(是否为null)
-
null:直接创建结点并挂到它下面 -
!null:进行判断，判断当前是否满足条件转为红黑树(这里不满足，直接跳出了for循环以及else，进入下一个if)
iii.判断下一个元素的哈希值是否等于被添加元素
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
break;
}
- 满足则跳出循环，进入到else外面
if (e != null) {}进行替换判断 - 不满足不进入if执行下一个
p = e;，然后再循环一次(就是这个操作使得结点可以一个个向下找空位置) -
else {
//如果从数组中获取出来的键值对不是红黑树中的节点
//表示此时下面挂的是链表
for (int binCount = 0; ; ++binCount) {
//获取下一个结点，并判断其是否为null
if ((e = p.next) == null) {
//为null表示其没有下一个结点，此时就会创建一个新的节点，直接挂在下面形成链表
p.next = newNode(hash, key, value, null);
//判断当前链表长度是否超过8，如果超过8，就会调用方法treeifyBin
//treeifyBin方法的底层还会继续判断
//判断数组的长度是否大于等于64
//如果同时满足这两个条件，就会把这个链表转成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//e： 0x0044 ddd 444
//要添加的元素： 0x0055 ddd 555
//如果哈希值一样，就会调用equals方法比较内部的属性值是否相同
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
break;
}
p = e;
}
}
② 判断e,进入覆盖循环
- 如果e为null，表示当前不需要覆盖任何元素
- 如果e不为null，表示当前的键是一样的，值会被覆盖
因为是在那个判断
e.hash == hash跳出else循环进入这里的，所以e不为0，进入循环进行替换
就是判断e的值是不是为null(如果是从上面跳出的，那绝对不为null),再进一步判断!onlyIfAbsent,因为!onlyIfAbsent在上面设置成了false,则这里取反就是true,进入，执行替换
由源码可以得知，其替换并非全部替换，老的键值对依旧在那，替换的仅仅只有值而已。
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null){
//等号的右边：当前要添加的值
//等号的左边：0x0044的值
e.value = value;
}
afterNodeAccess(e);
return oldValue;//返回被替换的元素
}
③ 判断是否需要扩容
**注意：**threshold：表示数组长度 * 0.75.就是扩容的阈值
**例如：**第一次调用resize(),创建的数组长度是16，则threshold = 16 * 0.75 =12
先++size，将当前添加元素造成的长度变化更新，在与threshold进行比较，当数组长度大于threshold时，就执行扩容(调用resize())
if (++size > threshold){
resize();
}
④ 直接走到最后null
因为这是第一次添加元素，当前没有覆盖任何元素，返回null
return null;
四.完整源码
1.看源码之前需要了解的一些内容
Node[] table 哈希表结构中数组的名字
DEFAULT_INITIAL_CAPACITY： 数组默认长度16
DEFAULT_LOAD_FACTOR： 默认加载因子0.75
HashMap里面每一个对象包含以下内容：
1.1 链表中的键值对对象
包含：
int hash; //键的哈希值
final K key; //键
V value; //值
Node next; //下一个节点的地址值
1.2 红黑树中的键值对对象
包含：
int hash; //键的哈希值
final K key; //键
V value; //值
TreeNode parent; //父节点的地址值
TreeNode left; //左子节点的地址值
TreeNode right; //右子节点的地址值
boolean red; //节点的颜色，true是红色，false是黑色
2.添加元素
HashMap hm = new HashMap<>(); //此时什么都没干，只是指定了加载因子而已，甚至数组都不存在
hm.put("aaa" , 111);
hm.put("bbb" , 222);
hm.put("ccc" , 333);
hm.put("ddd" , 444);
hm.put("eee" , 555);
添加元素的时候至少考虑三种情况：
2.1数组位置为null
2.2数组位置不为null，键不重复，挂在下面形成链表或者红黑树
2.3数组位置不为null，键重复，元素覆盖
//参数一：键
//参数二：值
//返回值：被覆盖元素的值，如果没有覆盖，返回null
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//利用键计算出对应的哈希值，再把哈希值进行一些额外的处理
//简单理解：返回值就是返回键的哈希值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//参数一：键的哈希值
//参数二：键
//参数三：值
//参数四：如果键重复了是否保留
// true，表示老元素的值保留，不会覆盖
// false，表示老元素的值不保留，会进行覆盖
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
//定义一个局部变量，用来记录哈希表中数组的地址值。
//定义的原因：此方法需要反复用到Node的地址值，直接定义在方法(栈)，可避免重复调用堆内存里的table(同样记录Node地址值，不过在父级)，提高了效率
Node[] tab;
//临时的第三方变量，用来记录键值对对象的地址值
Node p;
//表示当前数组的长度
int n;
//表示索引
int i;
//把哈希表中数组的地址值，赋值给局部变量tab
tab = table;
if (tab == null || (n = tab.length) == 0){
//resize方法的处理：(table的值是在这个里面被赋予的，数组也是在这里创建的)
//1.如果当前是第一次添加数据，底层会创建一个默认长度为16，加载因子为0.75的数组
//2.如果不是第一次添加数据，会看数组中的元素是否达到了扩容的条件
//如果没有达到扩容条件，底层不会做任何操作
//如果达到了扩容条件，底层会把数组扩容为原先的两倍，并把数据(链表、树)全部转移到新的哈希表中
tab = resize();
//表示把当前数组的长度赋值给n -> 16
n = tab.length;
}
//拿着数组的长度跟键的哈希值进行计算，计算出当前键值对对象，在数组中应存入的位置
i = (n - 1) & hash;//i可以理解为index
//获取数组中对应元素的数据(Tab已经记录Node的地址值了)
p = tab[i];
if (p == null){
//底层会创建一个键值对对象，直接放到数组当中
tab[i] = newNode(hash, key, value, null);
}else {
Node e;
K k;
//-----------------------------
//判断当前添加元素的哈希值等不等于上一个结点(同位置)的哈希值[判断键是否相同]
//等号的左边：数组中键值对的哈希值
//等号的右边：当前要添加键值对的哈希值
//1.如果键不一样，此时返回false
//2.如果键一样，返回true
//p.hash表示是当前位置的元素的哈希，这个p是前面计算处理的位置，用这个调用就是其父结点的哈希啦
boolean b1 = p.hash == hash;//只会走一次
//-------------------------------------
if (b1 && ((k = p.key) == key || (key != null && key.equals(k)))){
e = p;
} else if (p instanceof TreeNode){
//判断数组中获取出来的键值对是不是红黑树中的节点
//如果是，则调用方法putTreeVal，把当前的节点按照红黑树的规则添加到树当中。
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
} else {
//如果从数组中获取出来的键值对不是红黑树中的节点
//表示此时下面挂的是链表
for (int binCount = 0; ; ++binCount) {
//获取下一个结点，并判断其是否为null
if ((e = p.next) == null) {
//为null表示其没有下一个结点，此时就会创建一个新的节点，直接挂在下面形成链表
p.next = newNode(hash, key, value, null);
//判断当前链表长度是否超过8，如果超过8，就会调用方法treeifyBin
//treeifyBin方法的底层还会继续判断
//判断数组的长度是否大于等于64
//如果同时满足这两个条件，就会把这个链表转成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//e： 0x0044 ddd 444
//要添加的元素： 0x0055 ddd 555
//如果哈希值一样，就会调用equals方法比较内部的属性值是否相同
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
break;
}
p = e;
}
}
//如果e为null，表示当前不需要覆盖任何元素
//如果e不为null，表示当前的键是一样的，值会被覆盖
//e:0x0044 ddd 555
//要添加的元素： 0x0055 ddd 555
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null){
//等号的右边：当前要添加的值
//等号的左边：0x0044的值
e.value = value;
}
afterNodeAccess(e);
return oldValue;
}
}
//threshold：记录的就是数组的长度 * 0.75，哈希表的扩容时机 16 * 0.75 = 12
if (++size > threshold){
resize();
}
//表示当前没有覆盖任何元素，返回null
return null;
}