前言
JDK7 和JDK8 的扩容方法都基于 resize()方法，但底层实现却有所不同
JDK7 HashMap扩容
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); //新的容量为旧数组容量的两倍
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
//扩容方法
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//如果老的数组容量大于最大值，即2的30次方，则将其容量设置为Integer.MAX_VALUE返回
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//根据新的容量创建Entry数组
Entry[] newTable = new Entry[newCapacity];
//将就数组的值rehash到新数组中去
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
//更新阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//for循环遍历数组
for (Entry<K,V> e : table) {
//遍历链表
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//重新计算索引值
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
static int indexFor(int h, int length) {
return h & (length-1);
}
全部 rehash（重新计算索引位置） 消耗大，采用头插法在多线程环境下可能出现死循环，jdk8已经优化
总结
- 新数组容量为旧数组容量的两倍
- 根据新的容量创建数组，然后调用transfer方法遍历Entry数组和遍历Entry数组每个元素的遍历，对链表上的每个元素重新计算索引值，然后放到新数组中去
- rehash完成之后，将原数组引用指向新数组，然后更新阈值
JDK8 HashMap扩容
//扩容方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//旧的数组容量不能为空
if (oldCap > 0) {
//如果老的数组容量大于最大值，即2的30次方，则将其容量设置为Integer.MAX_VALUE返回
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果没那么大，则新容量为原来的两倍，对阈值也进行扩容
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//如果旧数组容量为0，但是阈值大于0时，那么新容量就设置为阈值
else if (oldThr > 0)
newCap = oldThr;
else {
//如果都为0，那么容量设置为默认值16，阈值为容量 * 加载因子 == 16 * 0.75
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//若新的阈值为0，那么用新的容量 * 加载因子重新计算
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;
//如果旧数组不为null
if (oldTab != null) {
//遍历旧的数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//如果当前元素不为null，用中间变量把保存当前元素
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果只有一个元素
if (e.next == null)
//重新做hash散列并赋值
newTab[e.hash & (newCap - 1)] = e;
//如果是红黑树的话，那么就要把新的hash表也变成红黑树结构
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
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;
}
loHead，下标不变情况下的链表头
loTail，下标不变情况下的链表尾
hiHead，下标改变情况下的链表头
hiTail，下标改变情况下的链表尾
if((e.hash & oldCap) == 0)，就是代表散列下标不变的情况，这种情况下代码只使用了loHead和loTail两个参数，由他们组成了一个链表，否则将使用hiHead和hiTail参数。
JDK8 和 JDK7 在rehash上是有所不同的，JDK7是对全部元素 rehash，而JDK8对此进行优化，根据 if((e.hash & oldCap) == 0) 判断是否需要移动元素
举例：
18 % 16=2 18 % 32=18
34 % 16=2 34 % 32=2
50 % 16=2 50 % 32=18
区分哪些元素应该在原来的位置，那些在新的位置。
总结
- 如果旧的数组容量不能为空且老的数组容量大于最大值，即2的30次方，则将其容量设置为Integer.MAX_VALUE返回，否则的话将新容量设为原来的两倍，对阈值也进行扩容
- 如果旧数组容量为0，但是阈值大于0时，那么新容量就设置为阈值
- 如果都为0，那么容量设置为默认值16，阈值为容量 * 加载因子 == 16 * 0.75
- 把就数组元素放到新数组中去
- 如果旧数组不为null，那么遍历旧数组，如果旧数组每个元素即链表头节点不为null，且只有一个元素的话，那么将该元素重新散列到新数组中去
- 如果是红黑树结构的话，那么在新的数组中也要是红黑树结构
- 如果都不是的话，则需要通过if ((e.hash & oldCap) == 0)判断当前节点是否需要改变位置，对于不需要改变的节点初始化loHead为头节点，loTail为尾节点通过next往后移，而需要改变得元素初始化hiHead为头节点，hiTail为尾节点通过next往后移
- 最后，对于loHead在新数组原索引处放置，对于hiHead，则在当前位置 + olgTab(旧数组容量)放置
觉得不错的小伙伴可以一键三连哦！，感谢支持！！！
更多面试题请移步 大厂面试题专栏
