前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Java之HashMap扩容

Java之HashMap扩容

原创
作者头像
笔头
修改2022-01-18 10:25:24
9320
修改2022-01-18 10:25:24
举报
文章被收录于专栏:Android记忆

扩容(resize)就是重新计算容量,向HashMap对象里不停的添加元素,而HashMap对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素,方法是使用一个新的数组代替已有的容量小的数组。

核心代码如下

代码语言:javascript
复制
    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 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档