前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >hashMap初始长度是多少

hashMap初始长度是多少

作者头像
用户5224393
发布2019-06-05 14:52:16
4.5K0
发布2019-06-05 14:52:16
举报
文章被收录于专栏:Java研发军团

创建函数时,传入初始长度0,1,2,3,4……15,16,数组table长度为多少

记住一点,当table进行初始化的时候,table.length 就是 比传入的值大的或者等于的最小的 2的n次方table.length 的长度一直是 2的n次方

也就是说,我new HashMap(0),table初始化后 table.length ==1(当然,源码中所有的变量都采用延迟初始化,只有等到用的时候,即put元素的时候才初始化。如果没有放入元素,那么 table一直为 null,我上面的只是另外一个变量 threshold得出来的,因为这两个有关系。我使用断点调试一下就知道了)

我们注意到,当构建函数时,threshold的初始值和 tableSizeFor()这个函数有关

我们再进入tableSizeFor

这个是返回一个比输入值大的或者等于的最小的 2的n次方(如果你不明白可以看下我后面的测试值和这篇文章

https://www.cnblogs.com/loading4/p/6239441.html

所以他返回的值为 1(比0大的或者等于的最小的2的n次方 就是1);

然后这个时候假如我们第一次 put一个元素,这个时候table数组就要开始初始化了,他就会执行这个resize函数,在源码中是这样

resize的解读如下

代码语言:javascript
复制
  1/**
  2     * 扩容函数
  3     *   使用情景: 1.初始化数组table,
  4     *           2.++size>threshold. 
  5     * @return 新的数组table
  6     *         或者是当扩容一倍长度超过最大值,返回原来的table数组
  7 */
  8    final  Entry[] resize() {
  9        // 定义旧的数组为 Entry 类型的数组,oldTab
 10        Entry[] oldTab = table;
 11        // 如果oldTab==null  则返回 0,否则返回数组大小
 12        int oldCap = (oldTab==null) ? 0 : oldTab.length;
 13
 14        int oldThreshold = threshold;
 15
 16        int newCap,newThreshold=0;
 17
 18        // 说明已经不是第一次 扩容,那么已经初始化过,容量一定是 2的n次方,所以可以直接位运算
 19        if(oldCap>0){
 20            // 如果 原来的数组大小已经大于等于了最大值,那么阈值设置为 Integer的最大值,即不会再进行扩容
 21            if(oldCap >= MAX_CAPACITY){
 22                threshold = Integer.MAX_VALUE;
 23                return oldTab;
 24            }
 25
 26            // 因此已经不是第一次扩容,一定是2的n次方
 27            else if ((newCap = oldCap << 1) < MAX_CAPACITY &&
 28                      oldCap >= INIT_CAPACITY)
 29
 30                newThreshold = oldThreshold << 1;
 31
 32        }
 33        // 如果oldThreshold > 0,并且oldCap == 0,说明是还没有进行调用resize方法。
 34        // 说明输入了初始值,且oldThreshold为 比输入值大的最小的2的n次方
 35        // 那么就把 oldThreshold 的值赋给 newCap ,因为这个值现在为 比输入值大的最小的2的n次方
 36        else if(oldThreshold>0)
 37            newCap = oldThreshold;
 38
 39        // 这个是只有使用无参构造器的时候才能满足的条件。,全部是否默认的值
 40        else{
 41            newCap = INIT_CAPACITY;
 42            newThreshold = (int) (INIT_CAPACITY * DEFAULT_LOADFACTOR);
 43        }
 44
 45        //
 46        if(newThreshold == 0){
 47
 48            float ft = (float) (newCap * loadFactor);
 49            newThreshold =(newCap < MAX_CAPACITY && ft < (float) MAX_CAPACITY ?
 50                    (int )ft : Integer.MAX_VALUE);
 51        }
 52
 53        threshold = newThreshold;
 54
 55        Entry newTable[] = new Entry[newCap];
 56        table=newTable;
 57
 58        // 将原来数组中的所有元素都 copy进新的数组
 59        if(oldTab != null){
 60            for (int j = 0; j < oldCap; j++) {
 61                Entry e;
 62
 63                if((e = oldTab[j]) != null){
 64                    oldTab[j] = null;
 65
 66                    // 说明还没有成链,数组上只有一个
 67                    if(e.next == null){
 68                        // 重新计算 数组索引 值
 69                        newTable[e.h & (newCap-1)] = e;
 70
 71                    }
 72                    // 判断是否为树结构
 73                    //else if (e instanceof TreeNode)
 74
 75
 76                    // 如果不是树,只是链表,即长度还没有大于 8 进化成树
 77                    else{
 78                        // 扩容后,如果元素的 index 还是原来的。就使用这个lo前缀的
 79                        Entry loHead=null, loTail =null;
 80
 81                        // 扩容后  元素index改变,那么就使用 hi前缀开头的
 82                        Entry hiHead = null, hiTail = null;
 83                        Entry next;
 84                        do {
 85                            next = e.next;
 86                            //这个非常重要,也比较难懂,
 87                            // 将它和原来的长度进行相与,就是判断他的原来的hash的上一个    bit 位是否为 1。
 88                            //以此来判断他是在相同的索引还是table长度加上原来的索引
 89                            if((e.h & oldCap) == 0){
 90                                // 如果 loTail == null ,说明这个 位置上是第一次添加,没有哈希冲突
 91                                if(loTail == null)
 92                                    loHead = e;
 93                                else
 94                                    loTail.next = e;
 95                                loTail = e;
 96                            }
 97                            else{
 98                                if(hiTail == null)
 99                                    loHead = e;
100                                else
101                                    hiTail.next = e;
102                                hiTail = e ;
103                            }
104
105                        }while ((e = next) != null);
106
107
108                        if(loTail != null){
109                            loTail.next = null;
110                            newTable[j] = loHead;
111                        }
112
113                        // 新的index 等于原来的 index+oldCap
114                        else {
115
116                            hiTail.next = null;
117                            newTable[j+oldCap] = hiHead;
118                        }
119
120                    }
121                }
122
123            }
124        }
125
126        return newTable;
127    }

我们注意这里,满足这个的条件为 oldCap==0 && oldThreshold>0

代码语言:javascript
复制
1    else if(oldThreshold>0)
2        newCap = oldThreshold;

oldThreshold等于之前使用 tableSizeFor 的返回值,也就是 1;所以table一经初始化长度就为1(但是还要说明一点,执行完 resize函数之后 table.length等于1,threshold等于0。看我上面的分析,newThreshold=(int)0.75就等于0

但是我们执行的是存入元素的操作,所以存完之后,就要++size(因为之前里面没有元素),这个时候 size就等于1,他就大于 threshold。所以他又要执行resize函数进行扩容操作。执行完之后,table.length 就等于2了,threshold就等于 1了。

table的扩容全部都是乘以 2(左移一位),而且table.length也一直等于2的n次方,即(table.length &(table.length-1)) == 0

之后同理可以推,一开始创建对象时,传入 1的话,table 初始化长度为1;传入 2,长度为2;传入3长度为4;传入[5,8],长度为8;传入[9,16],长度为16

END

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-04-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Java研发军团 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 创建函数时,传入初始长度0,1,2,3,4……15,16,数组table长度为多少
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档