hashmap数组什么时候扩容_hashmap是数组还是链表

hashmap数组什么时候扩容_hashmap是数组还是链表为什么需要扩容?因为HashMap为了节省创建出的对象的内存占用,一开始只默认分配:staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;也就是默认的数组大小是16个,而在HashMap的源码中可以发现HashMap扩容方法如下,就是说当HashMap里存储元素的个数大于threshold(capacity*loadFactor时,会进行扩容,…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

为什么需要扩容?

因为HashMap为了节省创建出的对象的内存占用,一开始只默认分配:

static final int DEFAULT_INITIAL_CAPACITY=1<<4; 也就是默认的数组大小是16个,而在HashMap的源码中可以发现HashMap扩容方法如下,就是说当HashMap里存储元素的个数大于threshold(capacity*loadFactor时,会进行扩容,一般都会扩大成为原大小的一倍(总之是%2=0的一个newCapacity),之所以需要和2的幂相关,是因为散列表的hash算法是根据移位来进行计算的,而我们都知道计算机是二进制的,移位也只能是进行*2或者/2因此,扩容的大小要符合这个标准,否则会造成没必要的浪费甚至错误。

hashmap数组什么时候扩容_hashmap是数组还是链表 判断何时需要扩容

知道什么场景下会造成扩容,下面聊聊扩容是如何实现的:

hashmap数组什么时候扩容_hashmap是数组还是链表 扩容方法

首先判断原本的capacity是否已经是static final intMAXIMUM_CAPACITY=1<<30;,如果不是,会重新创建新的Entry数组,并将数组长度更改为newCapacity,接着调用了transfer方法,并将新的table和threshold赋值给当前hashMap对象,这里最重要的方法就是transfer,因为这个方法会根据newCapacity重新计算在Entry数组中原先存在的entry的新的散列位置。方法如下:

hashmap数组什么时候扩容_hashmap是数组还是链表 rehash重新计算entry的散列位置

计算过程比较简单与重新创建新的hashMap比较类似,就是根据entry的key重新计算出hash值,然后根据新的数组长度计算出应该把老的entry放在新数组的那个位置,如果有冲突就将entry链接其上。(这个方法一个有趣的地方是:是否rehash是可选的,而选择的方法是通过hash因子来决定的,这边暂时不多做讨论)在执行完这些东西之后,hashMap的扩容就结束了。

可以发觉,扩容的成本并不低,因为需要遍历一个时间复杂度为O(n)的数组,并且为其中的每个enrty进行hash计算。加入到新数组中,所以最好的情况是能够合理的使用HashMap的构造方法创建合适大小的HashMap,使得在不浪费内存的情况下,尽量减少扩容,这个就要根据业务来决定了。

另外引申一个问题,为什么hashMap会使用着么复杂的结构,而且在元素并没有将数组填充满的情况下就进行扩容?这个其实是和HashMap散列表的目的有关,因为使用hashCode先进行查找到entry所在的HashMap数组位置,再去遍历这个数组位置上的bucket,会使得查询的时间复杂度为O(1),这样一对比一般意义上的数组,不难发现有质的飞跃。这也是HashMap大费周章搞出这些的原因。而由此引申出来的冲突处理这样的问题后面会谈到。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/192636.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • matlab绘制plot_matlab最基本的绘图函数为

    matlab绘制plot_matlab最基本的绘图函数为1,颜色和线条:bblue蓝.point-solidggreen绿ocircle:dottedrred红xx-mark

  • Win系统 – 单通道 16G 内存 VS 双通道 16G 内存

    Win系统 – 单通道 16G 内存 VS 双通道 16G 内存单通道16GB测试成绩双通道16GB(8+8)测试成绩总结通过以上的一系列测试,不难看出单通道16GB与双通道16GB还是有一些差别的,究竟如何决择,笔者给大家分析一下。通过基础频率测试看出单通道16GB与双通道16GB内存条在性能参数、读取、写入、拷贝、复制、延迟及总体内存性能方面,还是存在着很大差距的;通过应用程序测试看出双通道16GB在解压缩方面比单通道16GB的速度要快接近1M/s,同理可以看出在双通道16GB在处理海量照片,视频软件等专业软件的能力要高出单通..

  • 使用python快速开发桌面小工具

    使用python快速开发桌面小工具参考链接WelcometoPython.orgExtendingandEmbeddingthePythonInterpreter—Python3.7.3documentation起因更重要在日常开发中,总需要一些普通的小工具。小工具嘛,要得急,写得也急,总有很多不完善的问题,频繁修改成了一个较大的问题。比如之前用c#写了一个将excel表自动转成csv文本的工具,…

  • 由于Redis后门漏洞导致服务器被注入挖矿脚本解决过程

    由于Redis后门漏洞导致服务器被注入挖矿脚本解决过程由于Redis后门漏洞导致服务器被注入挖矿脚本解决过程事件描述某一天的早晨,我还是像往常一样搭着公交车开启打工仔的一天,一早8.30就到办公室了,坐着玩手机等上班,就这这时突然我组长飞快的回来办公室,回来就说快看看阿里云后台服务,服务是不是挂掉了,我当时就纳闷了一大早的流量不大怎么就宕机了呢,不一会我组长收到了阿里云短信通知监测到恶意脚本,接下来就是脚本的查找前期处理首先是通过阿里云的控制台发现,查看到恶意的进程PID,通过ps-ef|greap5724的确看到了当前进程,前期处理我只

  • Linux防火墙关闭命令

    1.启动防火墙systemctlstartfirewalld2.禁用防火墙systemctlstopfirewalld3.设置开机启动systemctlenablefirewalld4.停止并禁用开机启动sytemctldisablefirewalld5.重启防火墙firewall-cmd–reload在linus上部署了项目,有时候会发现防火墙会拦截浏览器上发起的请求,这时候只需要执行第2个命令,把防火墙关闭即可…

  • javaweb-springMVC-55

    javaweb-springMVC-55

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号