概述

由于hashMap底层使用数组来实现的，用数据肯定无法避免扩容的问题。
1.7原理：hashMap扩容主要是，2倍扩容 + rehash，每个key-value对，都会基于key的hash值重新寻址找到新数组的新的位置。本来那个数组的长度假设是16，现在的话新数组的长度是32。同时要把所有元素rehash一下。基于key的hash值，重新在新的数组里找到新的位置，很多key在新数组的位置都不一样了，如果是之前冲突的这个key可能就会在新的数组里分布在不同的位置上了。
1.8原理：都是数组大小是2的n次方扩容，用的是与操作符来实现hash寻址的算法，来进行扩容的时候，rehash

JDK1.8的rehash算法

举例：
值1
n - 1 0000 0000 0000 0000 0000 0000 0000 1111
hash1 1111 1111 1111 1111 0000 1111 0000 0101
&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）
值2
n - 1 0000 0000 0000 0000 0000 0000 0000 1111
hash2 1111 1111 1111 1111 0000 1111 0001 0101
&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）

如果数组扩容了，容量变为原来的两倍，这时候就要重新去用那个hash寻址算法（（n-1）&hash）寻址。
值1 重新哈希
n-1 0000 0000 0000 0000 0000 0000 0001 1111
hash1 1111 1111 1111 1111 0000 1111 0000 0101
&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）

值2 重新哈希
n-1 0000 0000 0000 0000 0000 0000 0001 1111
hash2 1111 1111 1111 1111 0000 1111 0001 0101
&结果 0000 0000 0000 0000 0000 0000 0001 0101 = 21（index = 21的位置）

看下源码：size>threashold，意味着数组元素大于这个阈值就要开始扩容，重新哈希了
image.png

  1. public class HashMap<K,V> extends AbstractMap<K,V>
  2.     implements Map<K,V>, Cloneable, Serializable {
  4.     // jdk1.8 HashMap扩容源码
  5.     final Node<K,V>[] resize() {
  7.         Node<K,V>[] oldTab = table;
  9.         // 到@SuppressWarnings都是计算newTab的newCap和threshold容量
  10.         int oldCap = (oldTab == null) ? 0 : oldTab.length;
  11.         int oldThr = threshold;
  12.         int newCap, newThr = 0;
  13.         if (oldCap > 0) {
  14.             if (oldCap >= MAXIMUM_CAPACITY) {
  15.                 threshold = Integer.MAX_VALUE;
  16.                 return oldTab;
  17.             }
  18.             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  19.                      oldCap >= DEFAULT_INITIAL_CAPACITY)
  20.                 newThr = oldThr << 1; // double threshold
  21.         }
  22.         else if (oldThr > 0) // initial capacity was placed in threshold
  23.             newCap = oldThr;
  24.         else {               // zero initial threshold signifies using defaults
  25.             newCap = DEFAULT_INITIAL_CAPACITY;
  26.             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  27.         }
  28.         if (newThr == 0) {
  29.             float ft = (float)newCap * loadFactor;
  30.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  31.                       (int)ft : Integer.MAX_VALUE);
  32.         }
  33.         threshold = newThr;
  34.         @SuppressWarnings({"rawtypes","unchecked"})
  35.             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  37.         // 开始进行数据迁移
  38.         table = newTab;
  39.         if (oldTab != null) {
  40.             // 遍历oldTab中的数据，并迁移到新数组。
  41.             for (int j = 0; j < oldCap; ++j) {
  42.                 Node<K,V> e;
  43.                 // 如果oldTab数组中j位置数据不为null，进行遍历，并赋值给e，避免直接对oldTab进行操作
  44.                 if ((e = oldTab[j]) != null) {
  45.                     oldTab[j] = null;
  46.                     // 如果oldTab的j位置数据没有形成链表，就直接赋值到newTab
  47.                     if (e.next == null)
  48.                         newTab[e.hash & (newCap - 1)] = e;
  49.                     // 链表转换成了红黑树，针对红黑树的迁移方式
  50.                     else if (e instanceof TreeNode)
  51.                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  52.                     // 针对链表的数据迁移方式
  53.                     else { // preserve order
  54.                         // loHead 表示老值,老值的意思是扩容后，该链表中计算出索引位置不变的元素
  55.                         Node<K,V> loHead = null, loTail = null;
  56.                         // hiHead 表示新值，新值的意思是扩容后，计算出索引位置发生变化的元素
  57.                         Node<K,V> hiHead = null, hiTail = null;
  58.                         Node<K,V> next;
  59.                         do {
  60.                             next = e.next;
  61.                             // 表示老值链表，即该链表中计算出索引位置不变的元素
  62.                             if ((e.hash & oldCap) == 0) {
  63.                                 if (loTail == null)
  64.                                     loHead = e;
  65.                                 else
  66.                                     loTail.next = e;
  67.                                 loTail = e;
  68.                             }
  69.                             // 表示新值链表，即计算出索引位置发生变化的元素
  70.                             else {
  71.                                 if (hiTail == null)
  72.                                     hiHead = e;
  73.                                 else
  74.                                     hiTail.next = e;
  75.                                 hiTail = e;
  76.                             }
  77.                         } while ((e = next) != null);
  78.                         // 生成链表后整体赋值
  79.                         // 老链表整体赋值
  80.                         if (loTail != null) {
  81.                             loTail.next = null;
  82.                             newTab[j] = loHead;
  83.                         }
  84.                         // 新链表整体赋值
  85.                         if (hiTail != null) {
  86.                             hiTail.next = null;
  87.                             newTab[j + oldCap] = hiHead;
  88.                         }
  89.                     }
  90.                 }
  91.             }
  92.         }
  93.         return newTab;
  94.     }
  95. }

  1. else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

    1.             oldCap >= DEFAULT_INITIAL_CAPACITY)<br />                newThr = oldThr << 1; // double threshold 把原来数组的长度扩大两倍，同时把转红黑树的阈值也过大两倍。由于无论怎么样设定的容量一定是2的n次方，那这里直接位运算扩大两倍就行

  2. if ((e = oldTab[j]) != null) 拿到数组中的元素

    1. if (e.next == null)；如果这个元素下一个节点没有东西，也就是说这个元素不是个链表，直接哈希一个位置newTab[e.hash & (newCap - 1)] = e;
    2. else if (e instanceof TreeNode)，如果是个红黑树的树节点，就执行split方法遍历红黑树，然后将里面每个节点都进行重新hash寻址，找到新数组的某个位置。
    3. else { // preserve order；进入这个else分支的话，证明是链表，(e.hash & oldCap) == 0这里用的很巧妙用hash和老的与运算一下，意在分开链表中冲突的元素
      1. ① 等于0时，则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置

② 不等于0时,则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置再加上旧数组长度，记为高位区。

链表rehash详解：⭐

loHead：表示老值,老值的意思是扩容后，该链表中计算出索引位置不变的元素。
hiHead：表示新值，新值的意思是扩容后，计算出索引位置发生变化的元素。
举个例子，数组大小是 8 ，在数组索引位置是 1 的地方挂着一个链表，链表有两个值，两个值的 hashcode 分别是是9和33。当数组发生扩容时，新数组的大小是 16，此时 hashcode 是 33 的值计算出来的数组索引位置仍然是 1，我们称为老值hashcode 是 9 的值计算出来的数组索引位置是 9，就发生了变化，我们称为新值。
针对链表做do-while遍历，条件为(e = next) != null。利用(e.hash & oldCap) == 0来判断元素e属于新值链表还是老值链表。参考上面索引位置计算算法 e.hash & (oldCap - 1)，这次直接利用e.hash与oldCap作&运算，因为oldCap为4、8、16…为2的指数，其二进制为100，1000，10000…，所以e.hash与其作&运算，假如oldCap = 4，newCap = 8，那么最终计算得到的值如果等于0，则该元素的位置0-3之间，除此之外在4-7之间。通过这种方式判断元素e属于老值还是新值，这样生成两条新的链表。

1.8之所以解决了1.7循环链表的问题。

  1. 1.8用(e = next) != null来判断，同时使用loHead，hiHead记录新旧值，在赋值的时候loTail.next = null; hiTail.next = null;主动断链，而且赋值的时候用的是尾插法。
  2. 1.7就仅仅是在do-while循环中通过e!=null做约束而没有做别的什么操作。因此，在并发情况下，在do-while循环代码块中单纯使用指针做约束而不使用真实的Node节点中的next信息做约束，同时还是头插法构建链表，肯定是由一些问题的。