扩容(resize)就是重新计算容量,向HashMap对象里不停的添加元素,而HashMap对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素,方法是使用一个新的数组代替已有的容量小的数组。
核心代码如下
void resize(int newCapacity) { //传入新的容量
Entry[] oldTable = table; //引用扩容前的Entry数组
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了
threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
return;
}
Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组
transfer(newTable); //!!将数据转移到新的Entry数组里
table = newTable; //HashMap的table属性引用新的Entry数组
threshold = (int) (newCapacity * loadFactor);//修改阈值
}
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了旧的Entry数组
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
Entry<K, V> e = src[j]; //取得旧Entry数组的每个元素
if (e != null) {
src[j] = null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)
do {
Entry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity); //!!重新计算每个元素在数组中的位置
e.next = newTable[i]; //标记[1]
newTable[i] = e; //将元素放在数组上
e = next; //访问下一个Entry链上的元素
} while (e != null);
}
}
}
static int indexFor(int h, int length) {
return h & (length - 1);
}
代码重点在transfer方法,主要思想是
1.HashMap中创建新数组。
2.遍历旧数组,取出每个数组元素的链表.
3.把链表里的单元不断取出
4.通过indexFor方法计算其对应的index.,我们这里简单化 index=key%hashmap数组长度
5.取出新数组下标index对应的链表,放在当前单元.next中,同时把当前链表单元放到新数组下标为index的地方。
6.把当前链表单元.next作为 新当前链表单元。
7.循环4、5、6操作
我这里弄了一个实例。
当前hashmap数据如下,我们加载因子我们设为1,那么hashmap容量已经达到阈值了,再添加数据则需要扩容。
扩容如下。
那我们就开始重新安置原本hashmap里面数据的位置吧。
我们直接从第3步骤来看,取出下标0的数据即链表,也就是 e
按照第4步骤indexFor方法,计算其index,得出index=3,
按照第5步骤,把新数组下标为3的数据即链表(新数组每个元素初始值都是null)放在e.next中,同时把e放在下标为3新数组中。
那我们可以得出如下。
当前数组下标为0的链表,取尽链表单元后,继续取数组下标为1的链表。
按照上面同样做法,我们可以得出。
继续取数组下标为2的链表.key 有5、8、11,链表key为5、8时,结果如下。
当key为11时,即e5,这个时候对应新数组下标为5,此时该位置已经有数据,这就是遇到HashMap碰撞问题了,
按照第5步骤,新数组下标为5的数据即链表e3,放在e5.next中,同时e5放在新数组下标为5的地方。结果如下图。
扩容基本完成。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。