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大小变为原来的两倍
• 假设扩容前的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

参考:
Java HashMap的扩容

技术讨论 & 疑问建议 & 个人博客

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 3.0 许可协议，转载请注明出处！