hashmap扩容面试题：面试必问之HashMap扩容
hashmap扩容面试题：面试必问之HashMap扩容//判断容量是否大于0int newCap newThr = 0//获取当前tab的容量int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;
前面我们已经看过HashMap中put方法的内部实现流程啦，那么今天我们就来一起看看resize()方法到底做了些什么吧！我们继续来看下JDK 1.8中HashMap resize()方法的源码：
final Node<K V>[] resize() {
Node<K V>[] oldTab = table;
//获取当前tab的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap newThr = 0
//判断容量是否大于0
if (oldCap > 0) {
//判断容量是否超过最大容量，如超过最大容量，则将阈值设置为最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//判断将当前tab容易扩大一倍后是否小于最大容量并大于等于初始容量
//如果满足，则将阈值扩大一倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//如果当前tab容量为0并且阈值大于0，则将新容量设置为阈值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//设置默认容量，设置阈值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//此处针对有传入初始容量的实例，计算新的阈值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//设置新的阈值
threshold = newThr;
@SuppressWarnings({"rawtypes" "unchecked"})
Node<K V>[] newTab = (Node<K V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//遍历节点数组，将节点移入新的节点数组table
for (int j = 0; j < oldCap; j) {
Node<K V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果该位置只有一个节点则计算index索引并移入
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;
//重新计算索引位置
//e.hash & oldCap == 0 存入lo链 否则存入hi链
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);
//将lo链存入当前位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//将hi链存入oldCap j位置
if (hiTail != null) {
hiTail.next = null;
newTab[j oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
相信很多小伙伴看到e.hash & oldCap这句话很费解，但相信看了下面的例子后，小伙伴们就能明白了。
首先，我们假设oldCap为16，当前j=3 此时这个位置的链表上有A、B两个节点，这两个节点的(n-1)&hash=3 那么我们是不是可能理解为下面的情况：
hash(A): 0000 ... 0000 0011
hash(B): 0000 ... 0001 0011
&
n-1(15): 0000 ... 0000 1111
结果：
A: 0000 ... 0000 0011
B: 0000 ... 0000 0011
那么 oldCap&hash 也就是 n&hash，是不是可以如下理解呢
hash(A): 0000 ... 0000 0011
hash(B): 0000 ... 0001 0011
&
n(oldCap): 0000 ... 0001 0000 结果: A:0 B：16
newCap-1: 0000 ... 0001 1111 结果: A:3 B:19 (oldCap j)
通过这样一对比，大家发现没有，容量扩大一倍后计算位置与旧tab的索引index存在一定联系。
当 oldCap & hash = 0 时，新表位置与旧表保持一致
当 oldCap & hash != 0 时，新表位置为oldCap j
在扩容的时候通过这种方式，将一个链表合理的拆分成为了两部分，还省去了重新计算hash值的时间。这个设计是不是很精妙呢，反正我已经给作者献上了膝盖了。
