文章目录
- 4、HashMap
- 4.1 先看看属性
- 4.2 构造方法
- 4.3 从put分析扩容机制(重点)
- putVal方法
- resize方法(扩容和树化)
- 扩容
- 树化
- 扩容机制总结
- 4.4 get方法
- 4.5 remove方法
- 4.6 replace
往期:
- Collection集合工具类源码解读(一) — ArrayList 和 Vector
- Collection集合工具类源码解读(二) — LinkedList
4、HashMap
重头戏来咯,老惯例,先写个demo,debug
public class HashMapDemo {
public static void main(String[] args) {
HashMap<Object, Integer> map = new HashMap<>();
//HashMap<Object, Integer> map = new HashMap<>(2, 2);
map.put("AAA",1);
map.put("BBB",2);
map.put("CCC",3);
map.put("CCC",4);
for (int i = 5; i <= 12; i++) {
map.put(new Person(),i);
}
map.put(new Person(),13);
map.put(new Person(),14);
map.put(new Person(),15);
}
static class Person{
String name;
@Override
public int hashCode() {
return 100;
}
}
}
4.1 先看看属性
DEFAULT_INITIAL_CAPACITY
:默认初始容量为16- 注意:刚new出来是0,往里添加数据后第一次
resize()
才到16,等下分析
- 注意:刚new出来是0,往里添加数据后第一次
MAXIMUM_CAPACITY
:最大的容量:2的30次方DEFAULT_LOAD_FACTOR
:默认加载因子loadfactor:0.75- 用来计算扩容门槛,比如现在容量为16,16*0.75=12,即table满了12个容量就扩容,一次扩两倍
TREEIFY_THRESHOLD
:默认树化门槛:8UNTREEIFY_THRESHOLD
:默认从树转换回链表的门槛:6MIN_TREEIFY_CAPACITY
:最小树化容量:64- 注意:①jdk1.8之后hashmap才是数组+链表+红黑树,jdk1.7和之前都是数组+链表,没有红黑树
- ②必须满足table容量到64,并且其中table数组中的一个格子链接了长度为8的链表,这时候该链表才会树化,转换为红黑树
4.2 构造方法
一共四个:
- public HashMap():默认无参,loadfactor = 0.75
- public HashMap(int initialCapacity) :设置初始容量,loadfactor = 0.75
- public HashMap(int initialCapacity, float loadFactor):设置初始容量和loadfactor
- 注意:loadfactor需要在
0~1
范围内,否则永远不会扩容 (后续分析)
- 注意:loadfactor需要在
- public HashMap(Map<? extends K, ? extends V> m):往hashmap中插入另一个map
4.3 从put分析扩容机制(重点)
- put进去后先算key的hash值,如果key为空,hash为0,否则就用key的hashcode异或key右移16位
- 然后是进入putVal方法: 这个方法很重要,需要细说一下
putVal方法
- tab在判断时赋值,把原先的table赋给了tab,第一次进入putVal时,table为空,走进第一个if( 第一次put必然 )
- 进行 第一次resize
- 其他情况就是table不为空
- 如果该hash对应的table[i]位置为空:就直接放进去
- 如果该位置已经有元素了:
- 判断第一个元素的hash以及key和想要put进来的元素的hash以及key 是否相等,相等就让
e = 这个相等的元素
- 判断这个位置连接的是否是红黑树:是就走红黑树的方法
putTreeVal
- 否则就循环遍历这条链表,找是否有hash以及key 相等的元素,
- 有相等的就让
e = 这个相等的元素
- 没有相等的就找到这条链表的尾部,追加到尾部
- 有相等的就让
- 判断第一个元素的hash以及key和想要put进来的元素的hash以及key 是否相等,相等就让
- 最后如果
e!=null
即找到了一个key和hash都相等的元素,那么就替换调原来的值,修改为最新的值(所以hashmap往里put两个相同的key,值最后为最新的那个)
resize方法(扩容和树化)
扩容
- 进来之后先拿到原来的大小
oldCap
,原来的扩容门槛oldThr
, - 大括号是第一个if语段
- 原来的容量不为空:在oldCap不超过最大容量
MAXIMUM_CAPACITY
的情况下,将容量和门槛左移一位:意思是扩容直接翻2倍 - 原来的容量为空,但是门槛不为空:新的容量就是原来门槛的大小
- 原来容量为空,门槛也为空:(第一次resize):设置容量为16,门槛为16*0.75=12
- 原来的容量不为空:在oldCap不超过最大容量
- 第二个if语段,判断newThr是否还是等于0
- 在上一个if语段里,如果进入了
oldCap>0
,且oldThr=0的情况下,newThr翻2倍任然是0,所以在这里需要再次判断 - 将newThr设置为
newCap*loadFactor
- 在上一个if语段里,如果进入了
- 然后把
threshold = newThr
写回属性里,new一个新大小的Node数组,将table指向新的数组 - 然后再判断oldTab还有不有值,有就复制过来
- 最后返回新的table表
树化
再来讲一下扩容什么时候变成树的
如图是一个demo,默认构造方法hashmap的扩容门槛threhold是12
,Person类的hashcode都是一致的,所以能插在同一索引位置上
所以:执行完断点前面的程序后,size已经满足了12,且Person那条链表长度以及到达了8,如图
-
在put第13个值时,打断点进去,发现其执行了
treeifyBin(tab,hash)
,是因为他的链表长度超过了树化的长度TREEIFY_THRESHOLD = 8
最终执行完之后可以看到,容量扩到了32,门槛到了24
-
同样的,put14的时候,容量会扩到64,门槛到48,过程不截图了
-
在put 15 的时候,注意,在此之前已经满足①链表长度>=8 ②table表容量64 :意思是要开始树化了
同样的,进入
treeifyBin(tab,hash)
,但是这次走else if,进行红黑树化,如图:treeify()
就是对原来的树进行红黑树的格式化了,就不走进去了
最后发现,原来的Node已经被重构成了TreeNode
扩容机制总结
4.4 get方法
- get:
- 调用getNode,如果查到有值就返回该值,查不到就返回
null
- 调用getNode,如果查到有值就返回该值,查不到就返回
- getOrDefault:
- 调用getNode,如果查到有值就返回该值,查不到就返回
设置的默认值
- 调用getNode,如果查到有值就返回该值,查不到就返回
4.5 remove方法
- remove(Object key):删除一个KV。调用removeNode方法,分析写在图上了,显而易见
4.6 replace
- replace(key,oldValue,newValue):找到key,oldvalue对应的结点替换这个值
- replace(key,value):找到key对应的结点替换这个值
最后
以上就是专注发夹最近收集整理的关于Collection集合工具类源码解读(三) --- HashMap4、HashMap的全部内容,更多相关Collection集合工具类源码解读(三)内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复