关注
提问:hashmap什么时候会触发扩容? 回答:两种情况(基于JDK1.8) 1. 当HashMap中元素总个数达到阈值时就会扩容。注意是元素总个数,而不是数组占用个数。 // 数组扩容阈值,即:HashMap数组总容量 * 负载因子
int threshold
// 如果元素个数大于阈值,扩充数组。
if (++size > threshold)
resize(); 2. 比较复杂,当向HashMap中添加元素时,即调用 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) 方法时,如果通过hash值计算数组的索引,获取该索引位的首节点,且该首节点不为null时(即发生了Hash碰撞),会有对应三种处理情况: ① 新添加元素的key与首节点元素的key相同,即 // 如果首节点的key和要存入的key相同,那么直接覆盖value的值。
// p:hash值对应索引位置的首节点
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p; ② 如果首节点是红黑树节点(TreeNode),将键值对添加到红黑树。 // 如果首节点是红黑树的,将键值对插添加到红黑树
else if (p instanceof HashMap.TreeNode)
e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); ③ 如果首节点是链表,将键值对添加到链表。添加之后会判断链表长度是否到达TREEIFY_THRESHOLD - 1这个阈值,“尝试”将链表转换成红黑树。 // p.next == null,到达链表末尾,添加新节点,如果长度足够,转换成树结构。
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
} 而关键在于这个treeifyBin()方法中,如果 // 把链表转换为红黑色
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e; // 如果当前数组容量太小(小于64),放弃转换,扩充数组。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
resize();
} else if ((e = tab[index = (n - 1) & hash]) != null) {
// 将链表转成红黑树...
}
} HashMap在jdk1.8之后引入了红黑树的概念,表示若桶中链表元素超过8时,会自动转化成红黑树;若桶中元素小于等于6时,树结构还原成链表形式。而如果当前数组的容量太小(小于64),则放弃转换,扩充数组。扩充数组!扩充数组!扩充数组! 这样就有可能有一种情况出现,就是说我整个HashMap并没有达到负载因子那么多的元素个数,但是,我进行了一次扩容。所以单纯的以负载因子来看是否会发生扩容,是不全面的。 那我们来分析为什么要进行这一次扩容。 首先我们要理解HashMap为什么要进行扩容,扩容这个操作真正的意义在哪里?为什么要定义一个负载因子?设计他的初衷究竟是为了解决什么问题? 为什么要扩容呢,之所以要扩容,我理解是基于两个逻辑, 1. HashMap中元素个数实在太多了,已经很频繁的发生hash冲突,我不得不进行扩容来减少这个冲突,来增强效率。 2. HashMap中元素并不多,但元素都集中到那么一两个“坑位”上,数组占用的位置很少,但是在那一两个位置上的元素已经很多了,拖掉了执行的效率。即核心是一个分布不均匀的问题,在这样的情况下,扩容的目的,就是通过重新计算hash“坑位”让原来聚集在一起的节点分散开来,是为了让分布更加均匀。 而treeifyBin()方法中,之所以判断当前数组容量是否太小,也是基于第二个逻辑上的考量,因为数组容量很小,但是已经存在过长的链表需要转换成树结构,不如直接进行一次扩容,毕竟树的查询效率O(logn)也比不上一个正常HashMap的O(1)的效率。
查看原帖
8 2
相关推荐
04-21 10:52
浙江大学 计算机类 点赞 评论 收藏
转发
投递高德地图等公司7个岗位 >
点赞 评论 收藏
转发
不愿透露姓名的神秘牛友
05-08 20:46
点赞 评论 收藏
转发
牛客热帖
正在热议
# 和牛牛一起刷题打卡 #
13954次浏览 1286人参与
# 通信硬件薪资爆料 #
256193次浏览 2411人参与
# 不去互联网可以去金融科技 #
4271次浏览 59人参与
# 牛客帮帮团来啦!有问必答 #
1093856次浏览 16329人参与
# 面试被问第一学历差时该怎么回答 #
18280次浏览 199人参与
# 简历中的项目经历要怎么写? #
14317次浏览 191人参与
# 工作两年想退休了 #
19301次浏览 241人参与
# 简历中的项目经历要怎么写 #
482137次浏览 8763人参与
# 实习生应该准时下班吗 #
93303次浏览 705人参与
# 你收到了团子的OC了吗 #
530861次浏览 6297人参与
# 简历无回复,你会继续海投还是优化再投? #
23477次浏览 329人参与
# 你已经投递多少份简历了 #
338619次浏览 4905人参与
# 你怎么评价今年的春招? #
12464次浏览 193人参与
# 晒一晒我的offer #
3771771次浏览 58075人参与
# 我的上岸简历长这样 #
202532次浏览 4099人参与
# 担心入职之后被发现很菜怎么办 #
39618次浏览 328人参与
# 本周投递记录 #
221033次浏览 5380人参与
# 我想象的工作vs实际工作 #
105777次浏览 1700人参与
# 硬件人的简历怎么写 #
81838次浏览 849人参与
# 产品人求职现状 #
56853次浏览 823人参与
# 工作压力大怎么缓解 #
12608次浏览 176人参与