失眠网 > 【HashMap扩容机制】

【HashMap扩容机制】

时间：2022-06-26 09:37:32

相关推荐

【HashMap扩容机制】

我是🌟廖志伟🌟，一名🌕Java开发工程师🌕、📝Java领域优质创作者📝、🎉CSDN博客专家🎉、🌹幕后大佬社区创始人🌹。拥有多年一线研发经验，研究过各种常见框架及中间件的底层源码，对于大型分布式、微服务、三高架构（高性能、高并发、高可用）有过实践架构经验。

🍊博主：java_wxid

🍊博主：Java廖志伟

🍊社区：幕后大佬

文章目录

HashMap扩容机制

本文的大概内容：

HashMap扩容机制

将(k1,v1)直接放入Node类型的数组中，这个数组初始化容量是16，默认的加载因子是0.75。

HashMap有两个参数影响其性能：初始容量和加载因子。

容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。

加载因子其实是用来判断当前HashMap<K,V>中存放的数据量。

当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行扩容、rehash操作（即重建内部数据结构），扩容后的哈希表将具有两倍的原容量。hashmap初始化容量时候，对容量大小做的处理，保证初始化容量为最近的2的幂次方。

HashMap初始化容量非得是2的幂次方，2的倍数不行么，奇数不行么？

2的幂次方：hashmap在确定元素落在数组的位置的时候，计算方法是(n - 1) & hash，n为数组长度也就是初始容量。hashmap结构是数组，每个数组里面的结构是node（链表或红黑树），正常情况下，如果你想放数据到不同的位置，肯定会想到取余数确定放在那个数组里，计算公式：hash % n，这个是十进制计算。在计算机中， (n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n，计算更加高效。奇数不行：在计算hash的时候，确定落在数组的位置的时候，计算方法是(n - 1) & hash，奇数n-1为偶数，偶数2进制的结尾都是0，经过hash值&运算后末尾都是0，那么0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这样就会造成空间的浪费而且会增加hash冲突。

HashMap加载因子为什么是0.75？

如果加载因子比较大，扩容发生的频率比较低，浪费的空间比较小，发生hash冲突的几率比较大。比如，加载因子是1的时候，hashmap长度为128，实际存储元素的数量在64至128之间时间段比较多，这个时间段发生hash冲突比较多，造成数组中其中一条链表比较长，会影响性能。

如果加载因子比较小，扩容发生的频率比较高，浪费的空间比较多，发生hash冲突的几率比较小。比如，加载因子是0.5的时候，hashmap长度为128，当数量达到65的时候会触发扩容，扩容后为原理的256，256里面只存储了65个浪费了。

综合了一下，取了一个平均数0.75作为加载因子。当负载因子为0.75,时代入到泊松分布公式，计算出来长度为8时，概率=0.00000006，概率很小了，链表长度为8时转红黑树。

可能引发的问题：HashMap实际使用过程中会出现一些性能问题以及线程安全问题。

在JDK1.7中有二块值得注意的地方。

扩容的时候需要rehash操作，需要将所有的数据重新计算HashCode，然后赋给新的HashMap<K,V>，rehash的过程是非常耗费时间和空间的。当并发执行扩容操作时会造成环形链和数据丢失的情况，开多个线程不断进行put操作，所以当旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置(就是因为头插)，所以最后的结果打乱了插入的顺序，就可能发生环形链和数据丢失的问题，引起死循环，导致CPU利用率接近100%。

在JDK1.8中，对HashMap进行了优化。

经过rehash之后元素的位置，要么是在原位置，要么是在原位置再移动2次幂的位置。HashMap的数组长度恒定为2的n次方，也就是说只会为16，32，64，128这种数。即便你给的初始值是13，最后数组长度也会变成16，它会取与你传入的数最近的一个2的n次方的数。

扩容之后元素的位置是否改变，完全取决于紫色框框中的运算是为0还是1，为0则新位置与原位置相同，不需要换位置，不为零则需要换位置。

在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成原位置+原数组长度。

为什么新的位置是原位置+原数组长度?

HashMap中运算数组的位置使用的是leng-1，对于初始长度为16的数组，扩容之后为32，对应的leng-1就是15，31。

举例一：假设某个元素的hashcode为52，这个52与15运算做按位与运算的的结果是4，这个52与31做按位与运算的的结果是20，20不就是等于4+16吗，刚好是原数组的下标+原数组的长度。

举例二：假设某个元素的hashcode为100，100&15=4，100&31=4，对于HashCode为100的元素来说，扩容后与扩容前其所在数组中的下标均为4。

以上两个例子证明了，经过rehash之后，元素的位置要么是在原位置，要么是在原位置加原数组长度的位置。

因为每次扩容会把原数组的长度*2，那么再二进制上的表现就是多出来一个1

比如原数组16-1二进制为0000 1111
那么扩容后的32-1的二进制就变成了0001 1111
再次扩容64-1就是0011 1111

扩容之后元素的位置是否改变则取决于与这个多出来的1的运算结果，运算结果为0则不需要换位置，运算结果为1则换新位置，新位置为老位置的高位进1。

既省去了重新计算hash值的时间，而且由于新增的1bit是0还是1，可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。

发生hash碰撞，不再采用头插法方式，而是直接插入链表尾部，因此不会出现环形链表的情况，但是在多线程环境下，会发生数据覆盖的情况，如果没有hash碰撞的时候，它会直接插入元素。如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，线程A会把线程B插入的数据给覆盖，导致数据发生覆盖的情况，发生线程不安全。可参考【HashMap并发修改异常】

总结

以上就是今天要讲的内容，还希望各位读者大大能够在评论区积极参与讨论，给文章提出一些宝贵的意见或者建议📝，合理的内容，我会采纳更新博文，重新分享给大家。

🙏四连关注🔎点赞👍收藏⭐️留言📝

感谢大家的支持，用心写博文分享给大家，你的支持（🔎点赞👍收藏⭐️留言📝）是对我创作的最大帮助。
🍊微信公众号：南北踏尘
🍊主页地址：java_wxid
🍊社区地址：幕后大佬

给读者大大的话

我本身是一个很普通的程序员，放在人堆里，除了与生俱来的🌹盛世美颜🌹、所剩不多的发量，就剩下180的大高个了。就是我这样的一个人，默默坚持写博文也有好多年了，有句老话说的好，🌕牛逼之前都是傻逼式的坚持🌕。希望自己可以通过大量的作品，时间的积累，个人魅力、运气和时机，可以打造属于自己的🌟技术影响力🌟。同时也希望自己可以成为一个🎄懂技术🎄，🎄懂业务🎄，🎄懂管理🎄的综合型人才，作为项目架构路线的总设计师，掌控全局的🌕团队大脑🌕，技术团队中的🍊绝对核心🍊是我未来几年不断前进的目标。