脚本宝典收集整理的这篇文章主要介绍了HashMap中扩容问题夺命6连问,问到了硬件层,你能顶住吗?,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
✨ 我是喜欢分享知识、喜欢写博客的YuShiwen,与大家一起学习,共同成长!
📢 闻到有先后,学到了就是自己的,大家加油!
📢 导读:
文章不长,看完后相信你一定会有所收获,本篇文章和一般的面试文章不一样,本篇文章知识点更细、更深,直接到硬件层,更进一步拓宽读者对于计算机的认知,并且还力求知其所以然!
即i=(n-1)&hash;其中i是tab数组的下标,n是Hash表中数组的长度,hash是key通过hashCode方法计算得到的值,源码如下:
这里笔者就拿刚开始的扩容量来说,之前是2的n次幂的时候,初始化长度是16,如果不是2的n次幂,我们就举例为13,那么执行上面这段代码的时候,会出现这样的现象:(备注:int类型有32为,为节约空间,这里我只写出低8位,剩下的24位没写出的全是0)
也就是说初始化长度位13的hash表数组,其中只有下标为0、4、8、12的能存放值,下标为1、2、3、5、6、7、9、10、11是没有用到的,如下图:
这就会导致让节点成为超长链表的概率大大增加,导致之后的查询时间过长。如果是2的n次幂,同样的我们执行上述三个步骤:
图就变成了下图:
这里说一下取模Math.floorMod和取余%的区别,在Java中取模的定义如下:
因为取余运算是操作符%,Java中看不到源码,笔者参考数学中对于取余的定义,大致内容如下:public static int fixMod(int x, int y){
int r = x - fixDiv(x,y)*y;
return r;
}
floorMod调用了floorDiv方法,fixMod调用了fixDiv方法,floorDiv方法和fixDiv都是求商的运算; 其中floorDiv是向负无穷取整,fixDiv是向0取整:
总结就是:
上面是取余与取模运算其中的一个区别,接下我们看另外一个区别,这个也是重点,我们看一个例子:
上例代码如下,大家可以自行复制粘贴运行一下康康:println "5,3取模运算为:"+Math.floorMod(5,3);
println "5,3取余运算为:"+5%3;
println "";
println "-5,-3取模运算为:"+Math.floorMod(-5,-3);
println "-5,-3取余运算为:"+(-5%-3);
println "";
println "5,-3取模运算为:"+Math.floorMod(5,-3);
println "5,-3取余运算为:"+(5%-3);
println "";
println "-5,3取模运算为:"+Math.floorMod(-5,3);
println "-5,3取余运算为:"+(-5%3);
运行结果如下:
有如下情况:通过上面可以可以得知,不论是取模运算还是取余运算,当除数或被除数是负数时,那么计算结果也可能为负数。
普通计算器是通过硬件的逻辑运算实现加减乘除的:
从数学上讲,CPU中的ALU在算术上只干了三件事,加法,移位,取反; 在实际的物理电路中,只有与、或、非、异或这四种门电路; 知道了这两点,我们再来分析加减乘除:
2位加法器门电路大致如下:(这里以两位加法器举例,现实中可以由更多的这些门电路组成更多位的加法器)
乘法器门电路图如下,乘法器由加法器和与门组成(同样这里也只举例2位*2位的乘法,更高位的门电路更复杂,但是实现的基本方式是没有变化的)从硬件实现上讲,可以看出,实现这四种基本运算只需要加法器、移位器和基本逻辑门电路硬件组件就行。早期的cpu里结构简单,只有这些组件,没有专门的乘法器、除法器。后来的cpu会集成专门的并行处理电路在cpu内建的协处理器(比如浮点运算器,很早的cpu是没有专门计算浮点的电路的)中,在硬件上实现,这样计算速度就快了。当然,计算的逻辑还是没变。
上面3.1章节中,我们提到过,取模操作如下(取余操作也是类似的):
r=x-floorDiv(x,y)*y
在这个关系式中,fixMod它是求商操作,求商操作包含了除法操作,得到的商又和y相乘,上面我们讲到了: 乘法可以拆分为:移位,逻辑判断,累加; 除法可以拆分为:移位,逻辑判断,累减。 可以看到乘法和除法的底层实现就是移位操作还有累加操作,再加上一些逻辑判断,这和&(与)操作相比效率低太多了,与操作只需要一个与门逻辑电路就可以计算完成。
测试代码(JDK1.8): 创建一个HashMap,此时为空,首先我们向HashMap中插入key=”name“,value=”YuShiwen“的键值对。
跟进代码中,调用了HashMap中的putVal()方法 跟进putVal方法中:putVal方法返回默认值16后,我们继续看,(此时HashMap表的长度就是16了,即n的值是16;我们都知道HashMap底层的实现是数组+链表,即是如下第一张图的结构;)之后到了一个if语句,该if语句中就是上面提到的计算数组下标的过程,即先把Hash表中数组的长度减1,然后在与key的hash值进行按位与(&)操作。
我是喜欢分享知识、喜欢写博客的YuShiwen,与大家一起学习,共同成长!咋们下篇博文见。
以上是脚本宝典为你收集整理的HashMap中扩容问题夺命6连问,问到了硬件层,你能顶住吗?全部内容,希望文章能够帮你解决HashMap中扩容问题夺命6连问,问到了硬件层,你能顶住吗?所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。