HashMap之扩容机制

首先要了解HashMap的扩容过程，我们就得了解一些HashMap中的变量：

Node<K,V>：链表节点，包含了key、value、hash、next指针四个元素
table：Node<K,V>类型的数组，里面的元素是链表，用于存放HashMap元素的实体
size：记录了放入HashMap的元素个数
loadFactor：负载因子
threshold：扩容的阈值，决定了HashMap何时扩容，以及扩容后的大小，一般等于，等于 table * loadFactor

何时进行扩容？

HashMap使用的是懒加载，构造完HashMap对象后，只要不进行put方法插入元素之前，HashMap并不会去初始化或者扩容table。

当首次调用put方法时，HashMap会发现table为空然后调用resize方法进行初始化，当添加完元素后，如果HashMap发现size（元素总数）大于threshold（阈值），则会调用resize方法进行扩容

扩容过程：

• 若threshold（阈值）不为空，table的首次初始化大小为阈值，否则初始化为缺省值大小16

• 默认的负载因子大小为0.75，当一个map填满了75%的bucket时候，就会扩容，扩容后的table大小变为原来的两倍
• 扩容因子=0.75。当使用量接近数组容量的75%的时候，数组中还有25%的剩余空间。碰撞的概率越大，put的元素就越多，平均到每个桶中的元素的数量也越多。一旦发生碰撞，需要付出更大的代价。所以，如果扩容因子越大，碰撞的概率也就越大，发生碰撞后的代价也更大，结果导致效率大打折扣。因此扩容因子=0.75也是一个空间换时间的考虑，0.75这个数值应该是经过充分的考虑决定的。
• 假设扩容前的table大小为2的N次方，有上述put方法解析可知，元素的table索引为其hash值的后N位确定
• 扩容后的table大小即为2的N+1次方，则其中元素的table索引为其hash值的后N+1位确定，比原来多了一位
• 重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing

因此，table中的元素只有两种情况：

元素hash值第N+1位为0：不需要进行位置调整

元素hash值第N+1位为1：调整至原索引的两倍位置

扩容或初始化完成后，resize方法返回新的table

以上就是极悦小编介绍的"HashMap之扩容机制"，希望对大家有帮助，想了解更多可查看Java基础教程，如有疑问，请在线咨询，有专业老师随时为您服务。