文章插图
而 hash 值的高位是否为 1 ， 只需要和扩容后的长度做与操作就可以了 ， 因为扩容后的长度为 2 的次幂 ， 所以高位必为 1 ， 低位必为 0 ， 如 10000 这种形式 ， 源码中有 e.hash--tt-darkmode-color: #50616D;">这个设计确实非常的巧妙 ， 既省去了重新计算 hash 值的时间 ， 而且同时 ， 由于新增的 1bit 是 0 还是 1 可以认为是随机的 ， 因此 resize 的过程 ， 均匀的把之前的冲突的节点分散到新的 bucket 了 。 这一块就是 JDK1.8 新增的优化点 。 有一点注意区别 ， JDK1.7 中 rehash 的时候 ， 旧链表迁移新链表的时候 ， 如果在新表的数组索引位置相同 ， 则链表元素会倒置 ， 但是从上图可以看出 ， JDK1.8 不会倒置 。 下面是 JDK1.8 的 resize 源码 ， 写的很赞 ， 如下:
final Node[] resize() {Node[] 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// double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else { // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 计算新的resize上限if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node[] newTab = (Node[])new Node[newCap];table = newTab;if (oldTab != null) {// 把每个bucket都移动到新的buckets中for (int j = 0; j < oldCap; ++j) {Node e;//如果位置上没有元素 ， 直接为nullif ((e = oldTab[j]) != null) {oldTab[j] = null;//如果只有一个元素 ， 新的hash计算后放入新的数组中if (e.next == null)newTab[e.hash//如果是树状结构 ， 使用红黑树保存else if (e instanceof TreeNode)((TreeNode)e).split(this, newTab, j, oldCap);//如果是链表形式else { // preserve orderNode loHead = null, loTail = null;Node hiHead = null, hiTail = null;Node next;do {next = e.next;//hash碰撞后高位为0 ， 放入低Hash值的链表中if ((e.hashelseloTail.next = e;loTail = e;}//hash碰撞后高位为1 ， 放入高Hash值的链表中else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 低hash值的链表放入数组的原始位置if (loTail != null) {loTail.next = null;newTab[j] = loHead;}// 高hash值的链表放入数组的原始位置 + 原始容量if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}作者：feigeswjtu
链接：
【图文并茂：HashMap经典详解】-------- END ---------
