记住一点,当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
的解读如下
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
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