Java之HashMap系列--HashMap扩容的原理

秒速五厘米 2023-10-01 17:09 17阅读 0赞

原文网址：[Java之HashMap系列--HashMap扩容的原理\_IT利刃出鞘的博客-CSDN博客][Java_HashMap_--HashMap_IT_-CSDN]

## 简介 ##

**说明**

本文介绍Java的HashMap是如何扩容的。

**重要大小**

<table> 
 <tbody> 
 <tr> 
 <td style="width:104px;"> 类 </td> 
 <td style="width:86px;"> 初始容量 </td> 
 <td style="width:174px;"> 最大容量 </td> 
 <td style="width:100px;"> 扩容时倍数 </td> 
 <td style="width:87px;"> 加载因子 </td> 
 <td style="width:184px;"> 底层实现 </td> 
 </tr> 
 <tr> 
 <td style="width:104px;"> HashMap </td> 
 <td style="width:86px;"> 2^4 </td> 
 <td style="width:174px;"> 2^30 </td> 
 <td style="width:100px;"> n * 2 </td> 
 <td style="width:87px;"> 0.75 </td> 
 <td style="width:184px;"> Map.Entry </td> 
 </tr> 
 <tr> 
 <td style="width:104px;"> HashSet </td> 
 <td style="width:86px;"> 2^4 </td> 
 <td style="width:174px;"> 2^30 </td> 
 <td style="width:100px;"> n * 2 </td> 
 <td style="width:87px;"> 0.75 </td> 
 <td style="width:184px;"> HashMap&lt;E,Object&gt; </td> 
 </tr> 
 <tr> 
 <td style="width:104px;"> HashTable </td> 
 <td style="width:86px;"> 11 </td> 
 <td style="width:174px;"> Integer.MAX_VALUE - 8 </td> 
 <td style="width:100px;"> n*2 + 1 </td> 
 <td style="width:87px;"> 0.75 </td> 
 <td style="width:184px;"> Hashtable.Entry </td> 
 </tr> 
 </tbody> 
</table>

上表中的“容量”其实就是数组长度。

HashMap中，哈希桶数组table的长度length大小必须为2的n次方(非质数)，这是一种非常规的设计，常规的设计是把桶的大小设计为质数。相对来说质数导致冲突的概率要小于非质数，具体证明可以参考[此文][Link 1]，Hashtable初始化桶大小为11，就是桶大小设计为质数的应用（Hashtable扩容后不能保证还是质数）。

HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化。为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。

## **何时扩容** ##

HashMap是懒加载，构造完HashMap对象后，若没用 put 来插入元素，HashMap不会去初始化或者扩容table，此时table是空的。扩容有如下场景：

1.  首次调用put方法时，HashMap会发现table为空然后调用resize方法进行初始化。
2.  非首次调用put方法时，若HashMap发现size（元素个数）大于threshold（阈值）（数组长度乘以加载因子的值），则会调用resize方法进行扩容。
3.  链表长度大于8 且数组长度小于64 会进行扩容。
    
    1.  链表长度大于8 （且数组长度大于等于64），会转化为红黑树。

数组是无法自动扩容的，所以只能是换一个更大的数组去装填以前的元素和将要添加的新元素。

上边是文章的部分内容，为便于维护，全文已迁移到此网址：[Java-HashMap扩容的原理 - 自学精灵][Java-HashMap_ -]

[Java_HashMap_--HashMap_IT_-CSDN]: https://knife.blog.csdn.net/article/details/122781613
[Link 1]: http://blog.csdn.net/liuqiyao_01/article/details/14475159
[Java-HashMap_ -]: https://learn.skyofit.com/archives/394