java8 HashMap扩容算法到底是怎样？
在看java8 HashMap的扩容方法源码之前，我一直以为扩容后都是重新进行hash计算，再放到对应节点上！ 实际上其实不是，我们先直接上源码
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
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) {
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
}
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) {
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;
}
}
直接看源码可得hashmap扩容，新的table数组直接得到原来的一倍大小容量newThr = oldThr << 1;，将原有数据搬运到新的table数组中，并且，原来数组里的数据，重新计算安排位置。
注意，计算新位置，是拿原有的hash值进行移位计算，而不是重新计算hash值。
根据源码，if ((e.hash & oldCap) == 0) 则原数据保持原位，但如果不等于0时，则新的下标就是旧下标 j+map的长度（这里的map长度就是对应扩容前table数组的长度）。
这是怎么来的，我们可以自己算一下
我们直接假设我们现在初始容器的大小是16，现在put了一个新的数据进来，key对应的hash，我们二进制码表示为00000000 00000000 00001010 10011111
根据源码
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//这里就是put进去的时候计算对应数组下标的逻辑
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value,
else {
//多余代码省略
...
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
}
我们可以
00000000 00000000 00001010 10011111& 00000000 00000000 00000000 00001111得00000000 00000000 00000000 00001111 ，即15 为最终值。
当我们进行扩容时，一次只能翻倍增长，16->32,重新分配位置，执行if ((e.hash & oldCap) == 0)，
也 00000000 00000000 00001010 10011111& 00000000 00000000 00000000 00010000得00000000 00000000 00000000 00010000
结果不为0，则原下标+16位=31，最终新位置在31。
如果该值是扩容后put进来的，新位置也是31吗？我们试一下
00000000 00000000 00001010 10011111& 00000000 00000000 00000000 00011111得00000000 00000000 00000000 00011111 ，即31 为最终值。
这是为什么？为什么？为什么？ 因为1&1才能为1，0&任何值都为0。
也就是32位的数，我们高16位可以不用看了，因为结果一定是0。
我们直接截断容量为16的低8位来看00010000,只有hash值(比如：00000000 00000000 00001010 10001111)的低第五位不为1时，才算出0的结果，保持原下标不变。当我们用容量为32来计算时，我们用hash值与上00011111结果位置跟原来的一致。
我们可以得出，如果你原容量是16，你hash值低五位结果小于等于15(00001111)时，保持原有位置不变。大于等于16（00010000）时，因为低第五位为1，我们需要进行移位16位的操作。因为用新的容量进行运算的时候，新的容量对应的二进制码00011111，原本低第五位不参与运算（这里的不参与运算是基于0&任何值都为0，我们当它不参与运算），只有低四位参与（原本16的容量是与上00001111），现在多了一位，也就是多了一倍，所以要+16位。
手动跟着算一遍就能意会到其中的奥妙。
这样的操作为了重新放置到新的table数组中更加均匀分布，一半一半地重新分布。并且比重新一个个rehash更快。
转载自:https://juejin.cn/post/7226376235558060087