HashMap 初始容量 计算方法
如果在new HashMap的时候，没有指定初始initialCapacity，则初始initialCapacity为16，负载因子为0.75，下次扩容阈值为 16*0.75=12
这个初始容量 不一定等于初始化完成后底层数组实际的容量，因为存在阈值的计算，方法如下；也不是初始容量是多少开始就能存多少个元素，因为存在负载因子，在底层数组还没满的时候就会进行扩容。
阈值计算方法为：
代码语言：javascript复制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;
}该方法计算大于等于输入参数并最接近参数的2的整数次幂的数，如10，返回16
cap -1 ，-1是为了在计算的时候能得到大于等于输入参数的值
在HashMap 进行put方法的时候，如果判断已有的元素大于 阈值就会触发扩容计算，扩容步骤如代码所示：
代码语言：javascript复制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;
}总结：
如下3种情况，例子需要自己调式，主要关注数组长度(OldCap,newCap)新老变化，扩容阈值(oldThr,newThr)新老变化
代码语言：javascript复制//①
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");① 没有设置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
面试回答要素
- 回答什么情况下会第一扩容，举例说明，新数组大小，阈值大小
- 以后什么情况下会再次扩容，这次是怎么计算新数组大小，及阈值大小的
作者热门文章推荐：
Java面试题专栏：
《从Java面试题看源码》-LongAdder、LongAccumulator是个什么东西？
《从Java面试题来看源码》-LinkedBlockingQueue 源码分析
《从Java面试题看源码》-有哪些并发队列?及ConcurrentLinkedQueue 源码分析
《从Java面试题看源码》-看完Kafka性能优化-让你吊打面试官
《从Java面试题看源码》-默认线程池阻塞队列为什么用LinkedBlockingQueue
