看下面这张图。
n 为 table 的长度,默认值为 16。
n-1 也就是二进制的 0000 1111(1X 2 0 2^0 2
0
+1X 2 1 2^1 2
1
+1X 2 2 2^2 2
2
+1X 2 3 2^3 2
3
=1+2+4+8=15);
key1 哈希值的最后 8 位为 0000 0101
key2 哈希值的最后 8 位为 0001 0101(和 key1 不同)
做与运算后发生了哈希冲突,索引都在(0000 0101)上。
扩容后为 32。
n-1 也就是二进制的 0001 1111(1X 2 0 2^0 2
0
+1X 2 1 2^1 2
1
+1X 2 2 2^2 2
2
+1X 2 3 2^3 2
3
+1X 2 4 2^4 2
4
=1+2+4+8+16=31),扩容前是 0000 1111。
key1 哈希值的低位为 0000 0101
key2 哈希值的低位为 0001 0101(和 key1 不同)
key1 做与运算后,索引为 0000 0101。
key2 做与运算后,索引为 0001 0101。
新的索引就会发生这样的变化:
原来的索引是 5(0 0101)
原来的容量是 16
扩容后的容量是 32
扩容后的索引是 21(1 0101),也就是 5+16,也就是原来的索引+原来的容量
也就是说,JDK 8 不需要像 JDK 7 那样重新计算 hash,只需要看原来的hash值新增的那个bit是1还是0就好了,是0的话就表示索引没变,是1的话,索引就变成了“原索引+原来的容量”。
JDK 8 的这个设计非常巧妙,既省去了重新计算hash的时间,同时,由于新增的1 bit是0还是1是随机的,因此扩容的过程,可以均匀地把之前的节点分散到新的位置上。
woc,只能说 HashMap 的作者 Doug Lea、Josh Bloch、Arthur van Hoff、Neal Gafter 真的强——的一笔。
JDK 8 扩容的源代码:
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; } // 没超过最大值,就扩充为原来的2倍 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); } // 计算新的resize上限 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 // 链表优化重 hash 的代码块 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; }