关于hashmap的容量问题

最近在研究hashmap的源码,jdk版本1.8
hashmap的第一层是一个数组Node[] table
table数组中存放的是一个结构体为node的单向链表

下面是和我的问题相关的几个属性:
size hashmap中node的个数
capacity hashmap中table数组的长度
loadfactor 负载系数,默认0.75
threshold hashmap中的阈值(threshold是等于capacity乘以loadfactor)

当++size>threshold时hashmap会扩容,并且进行rehash操作
比如就拿初始值来说,capacity=16,threshold=12,当put第13个键值对时就会触发rehash,扩容之后,capaccity会翻倍变成32,同样threshold也会重新计算变成24

那问题来了,在hashmap中,size的大小不能大于阈值,更能大于capacity?
这岂不是意味着,node元素的个数还不如数组的长度大?
还是我理解有误,请高手指教

2个回答

本来就应该是这样,需要在空间占用和性能上做出平衡,太小了,性能低,太大了,那就没必要hash了,成了直接寻址了。

wyl550182402
wyl550182402 我想明白了,我原本的疑问就在于,size小于capacity感觉很不合理,可以根据自己的需求设置loadfactor,大于1就可以让size大于capacity了
3 年多之前 回复

这里主要是要理解hash表的工作原理,loadfactor是一个比较重要的参数,所谓的负载因子就是在空间和查找效率上所做的一个平衡

当你哈希表中桶太小的时候,就会很容易导致冲突,从而需要对冲突的元素进行拉链法/开放寻址法等方式来解决冲突,这样就会导致查找效率的降低

而当你桶太大时,如果实际存放数据比较少。就会浪费太多空间。

所以才会有负载因子的出现,它0.75都是经过了很多工程化的实践后得到的一个优化值

wyl550182402
wyl550182402 想明白了,非常感谢!这个loadfactor可以根据实际情况进行调整,比如 for(int i=0;i<10000000;i++) { hashMap.put(i, 1); }这种场景,调整大一些才更合理
3 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐