本篇内容介绍了“HashMap的介绍以及扩容为什么是2的n次幂”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
HashMap是Java中的集合类,是存放键值对形式的数据(Key和Value),例如QQ账号和QQ密码,QQ账号就是Key而密码则是Value。如下图所示(假如QQ账号为123456,密码为abcdef)
运行结果如下所示
如果存放相同的Key,那么Value将会被覆盖,类似于QQ更改密码,账号不会变,只有密码会进行更改。
运行结果如下所示
首先先看一下HashMap中的putVal方法(存值的)和resize方法(扩容的),之所以HashMap扩容是2的n次幂和这两个方法有千丝万缕的联系。
通过putVal方法可以看出来HashMap在存值时会先把key的hash值和扩容后的长度进行一次按位与运算,其中hash是在hash方法中把key进行计算后的出来的结果,n是扩容的长度(也就是数组的长度,默认为16),然后判断是否hash碰撞在进行不同的存储。如下图源码所示。
通过resize方法可以看出来扩容时会新建一个tab,然后遍历旧的tab,将旧的元素进行e.hash & (newCap - 1)的计算添加进新的tab中,也就是(n - 1) & hash的计算方法,其中n是集合的容量,hash是添加的元素经过hash函数计算出来的hash值。如下图源码所示。
之所以这样2n扩容和上面的两个方法有极大的关系,首先他们都使用了按位与运算,按位与运算就是把值先变成二进制然后进行运算,如果有0则为0,都为1时则输出为1,HashMap默认容量为16那么在存放到数组时就是n-1也就是15,而15二进制则是1111扩容后为32-1及11111111
,如果都为1的情况下是可以极大的减少hash碰撞,增加效率的。
通过下面例子来看一下当容量为11111111时按位与运算的结果,通过下面的结果可以看出来结果很分散,大大减少了hash碰撞的发生。
再看一下当容量不为11111111而是为其他值的时候,通过下面的结果可以看出,1、2、4跟不同的值进行hash运算但是结果却是相同的,也就是发生了hash碰撞。
通过上面的对比可以看出来11111111和其他值
比较大大的减少了hash碰撞的发生,这样就是为什
么HashMap为什么扩容采用2的n次幂的原因。
“HashMap的介绍以及扩容为什么是2的n次幂”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。