【从Java面试题看源码】-HashMap 初始容量 计算方法

HashMap 初始容量 计算方法

如果在new HashMap的时候，没有指定初始initialCapacity，则初始initialCapacity为16，负载因子为0.75，下次扩容阈值为 16*0.75=12

这个初始容量 不一定等于初始化完成后底层数组实际的容量，因为存在阈值的计算，方法如下；也不是初始容量是多少开始就能存多少个元素，因为存在负载因子，在底层数组还没满的时候就会进行扩容。

阈值计算方法为：

static final int tableSizeFor(int cap) {
   int n = cap - 1;
   n |= n >>> 1;
   n |= n >>> 2;
   n |= n >>> 4;
   n |= n >>> 8;
   n |= n >>> 16;
   return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
1
2
3
4
5
6
7
8
9

该方法计算大于等于输入参数并最接近参数的2的整数次幂的数，如10，返回16

cap -1 ，-1是为了在计算的时候能得到大于等于输入参数的值

在HashMap 进行put方法的时候，如果判断已有的元素大于 阈值就会触发扩容计算，扩容步骤如代码所示：

final Node<K,V>[] resize() {
//原table数组赋值
   Node<K,V>[] oldTab = table;
//如果原数组为null，那么原数组长度为0
   int oldCap = (oldTab == null) ? 0 : oldTab.length;
//赋值阈值
   int oldThr = threshold;
//newCap 新数组长度
//newThr 下次扩容的阈值
   int newCap, newThr = 0;
// 1. 如果原数组长度大于0
   if (oldCap > 0) {
       //如果大于最大长度1 << 30 = 1073741824，那么阈值赋值为Integer.MAX_VALUE后直接返回
       if (oldCap >= MAXIMUM_CAPACITY) {
           threshold = Integer.MAX_VALUE;
           return oldTab;
       }
       // 2. 如果原数组长度的2倍小于最大长度，并且原数组长度大于默认长度16，那么新阈值为原阈值的2倍
       else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
           newThr = oldThr << 1; // double threshold
   }
// 3. 如果原数组长度等于0，但原阈值大于0，那么新的数组长度赋值为原阈值大小
   else if (oldThr > 0) // initial capacity was placed in threshold
       newCap = oldThr;
   else {               // zero initial threshold signifies using defaults
       // 4. 如果原数组长度为0，阈值为0，那么新数组长度，新阈值都初始化为默认值
       newCap = DEFAULT_INITIAL_CAPACITY;
       newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
   }
// 5.如果新的阈值等于0
   if (newThr == 0) {
       //计算临时阈值
       float ft = (float)newCap * loadFactor;
       //新数组长度小于最大长度，临时阈值也小于最大长度，新阈值为临时阈值，否则是Integer.MAX_VALUE
       newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                 (int)ft : Integer.MAX_VALUE);
   }
//计算出来的新阈值赋值给对象的阈值
   threshold = newThr;
   @SuppressWarnings({"rawtypes","unchecked"})
//用新计算的数组长度新建一个Node数组，并赋值给对象的table
       Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
   table = newTab;
//后面是copy数组和链表数据逻辑
   if (oldTab != null) {
       for (int j = 0; j < oldCap; ++j) {
           Node<K,V> e;
           if ((e = oldTab[j]) != null) {
               oldTab[j] = null;
               if (e.next == null)
                   newTab[e.hash & (newCap - 1)] = e;
               else if (e instanceof TreeNode)
                   ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
               else { // preserve order
                   Node<K,V> loHead = null, loTail = null;
                   Node<K,V> hiHead = null, hiTail = null;
                   Node<K,V> next;
                   do {
                       next = e.next;
                       if ((e.hash & oldCap) == 0) {
                           if (loTail == null)
                               loHead = e;
                           else
                               loTail.next = e;
                           loTail = e;
                       }
                       else {
                           if (hiTail == null)
                               hiHead = e;
                           else
                               hiTail.next = e;
                           hiTail = e;
                       }
                   } while ((e = next) != null);
                   if (loTail != null) {
                       loTail.next = null;
                       newTab[j] = loHead;
                   }
                   if (hiTail != null) {
                       hiTail.next = null;
                       newTab[j + oldCap] = hiHead;
                   }
               }
           }
       }
   }
   return newTab;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

总结：

如下3种情况，例子需要自己调式，主要关注数组长度(OldCap,newCap)新老变化，扩容阈值(oldThr,newThr)新老变化

//①
Map<String, String> map = new HashMap<>();
map.put("1", "1");
//②
Map<String, String> map1 = new HashMap<>(2);
map1.put("2", "2");
//③
Map<String, String> map2 = new HashMap<>(2, 0.5f);
map2.put("3", "3");
1
2
3
4
5
6
7
8
9

① 没有设置initialCapacity，也没有设置负载因子，第一次put的时候会触发扩容
第一次的时候，数组长度为默认值16，阈值为160.75=12，走的代码4逻辑，等到数组长度超过阈值12后，触发第二次扩容，此时table数组，和threshold都不为0，即oldTab、oldCap、oldThr都不为0，先走代码1，如果oldCap长度的2倍没有超过最大容量，并且oldCap 长度大于等于 默认容量16，那么下次扩容的阈值 变为oldThr大小的两倍即 12 2 = 24，newThr = 24，newCap=32

② 设置了initialCapacity，没有设置负载因子，此时hashMap使用默认负载因子0.75，本实例设置的初始容量为2，通过计算阈值为2，第一次put的时候由于还没初始化table数组，因此触发第一次扩容。此时oldCap为0，oldThr为2，走代码3，确定这次扩容的新数组大小为2，此时还没有确定newThr 下次扩容的大小，于是进入代码5 确定newThr为 2 0.75 = 1.5 取整 1 ，及下次扩容阈值为1。当数组已有元素大于阈值及1时，触发第二次扩容，此时oldCap为1，oldThr为1，走代码1newCap = oldCap << 1 结果为 4 小于最大容量， 但oldCap 小于hashMap默认大小16，结果为false，跳出判断，此时由于newThr等于0，进入代码5，确定newThr为 4 0.75 = 3，下次扩容阈值为3

③ 设置了initialCapacity=2，负载因子为0.5，通过tableSizeFor计算阈值为2，第一次put的时候，进行扩容，此时oldCap为2，oldThr为2，进入代码1，同实例②，newCap = oldCap << 1 结果为 4 小于最大容量， 但oldCap 小于hashMap默认大小16，结果为false，跳出判断，进入代码5，确定newThr为 4 * 0.5 = 2,下次扩容阈值为2

面试回答要素

1. 回答什么情况下会第一扩容，举例说明，新数组大小，阈值大小
2. 以后什么情况下会再次扩容，这次是怎么计算新数组大小，及阈值大小的

---

作者热门文章推荐：

Java面试题专栏：

《从Java面试题看源码》-LongAdder、LongAccumulator是个什么东西？
《从Java面试题来看源码》-LinkedBlockingQueue 源码分析
《从Java面试题看源码》-有哪些并发队列?及ConcurrentLinkedQueue 源码分析
《从Java面试题看源码》-看完Kafka性能优化-让你吊打面试官
《从Java面试题看源码》-默认线程池阻塞队列为什么用LinkedBlockingQueue