HashMap 是一个非常重要的集合，其本质上是一个散列表，那么就离不开散列表的三大问题：散列函数、哈希冲突、扩容方案；同时作为一个数据结构，必须考虑多线程并发访问的问题，也就是线程安全。这四个点是学习 HashMap 的重点，也是 HashMap 设计的重点。

HashMap 并不是全能的，对于一些特殊场景下的需求官方拓展了一些其他的类来满足，比如线程安全的 ConcurrentHashMap、记录插入顺序的 LinkHashMap、给 key 排序的 TreeMap 等。

LinkedHashMap 通常提供的是遍历顺序符合插入顺序，它的实现是通过为键值对维护一个双向链表。这种行为适用于一些特定应用场景，例如，我们构建一个空间占用敏感的资源池，希望可以自动将最不常被访问的对象释放掉，这就可以利用 LinkedHashMap 提供的机制来实现，参考下面的示例：

  1. LinkedHashMap<String, String> accessOrderedMap = new LinkedHashMap<String, String>(16, 0.75F, true){
  2.     @Override
  3.     protected boolean removeEldestEntry(Map.Entry<String, String> eldest) { // 实现自定义删除策略，否则行为就和普遍Map没有区别
  4.         return size() > 3;
  5.     }
  6. };

存储结构

HashMap 的存储结构是由数组 + 链表 + 红黑树（JDK 8 增加了红黑树部分）实现的。每个数组元素上都一个链表结构，当数据被 hash 后，得到数组索引下标，把数据放在对应下标元素的链表上。
c0a12608e37753c96f2358fe0f6ff86f.webp
JDK 1.8 的 HashMap 相比于 JDK 1.7 有了很多变化，具体如下：

  • Entry 结构变成了 Node 结构，hash 变量加上了 final 声明，即不可以进行 rehash 了。
  • put() 的时候插入节点的方式从头插法变成了尾插法。
  • 引入了红黑树，避免链表过长导致的效率下降。
  • 扩容方法的优化，不需要重新计算 hash 值，并且从头插法改成了尾插法。

其中，Node 是 HashMap 的一个内部类，实现了 Map.Entry 接口，本质是就是一个键值对。

  1. static class Node<K,V> implements Map.Entry<K,V> {
  2.     // 用来定位数组索引位置
  3.     final int hash;
  4.     final K key;
  5.     V value;
  6.     // 链表的下一个Node节点
  7.     Node<K,V> next;
  8. }

并且 HashMap 内部维护了一个 Node 数组，用来存储 Node 元素，该数组在第一次使用时被初始化。

  1. // 默认负载因子
  2. static final float DEFAULT_LOAD_FACTOR = 0.75f;
  3. // 链表转红黑树最小阈值
  4. static final int TREEIFY_THRESHOLD = 8;
  5. // 红黑树退化成链表最小阈值
  6. static final int UNTREEIFY_THRESHOLD = 6;
  7. // 链表转红黑树最小容量
  8. static final int MIN_TREEIFY_CAPACITY = 64;
  10. // Node数组，用来存储元素
  11. transient Node<K,V>[] table;
  12. transient Set<Map.Entry<K,V>> entrySet;
  13. // 当前实际存在的key-value对数量
  14. transient int size;
  15. // HashMap在结构上修改的次数，此字段用于对集合迭代过程中的修改进行快速失败，见ConcurrentModificationException
  16. transient int modCount;
  17. // 所能容纳的key-value对极限，超过阈值则需要扩容
  18. int threshold;
  19. // 负载因子，它使hashmap在node节点快用满的时候就进行扩容，避免可用节点太少，导致链表过长
  20. final float loadFactor;

  • table 数组的初始化长度默认是 16，loadFactor 默认值是 0.75。

  • threshold 代表 HashMap 所能容纳的最大数量的 Node 数。threshold = table.length * loadFactor。在存取数据的过程中，当 Node 节点的数量大于 threshold 阈值时，就会进行扩容，扩容后 HashMap 的容量是之前容量的两倍。

  • modCount 用来记录 HashMap 内部结构发生变化的次数，主要用于迭代的快速失败。内部结构发生变化指的是结构发生变化，例如 put 新键值对，但是某个 key 对应的 value 值被覆盖不属于结构变化。

  • 当链表过长（默认超过8）且当前容量大于可以转化红黑树的最小容量时，链表就会转换为红黑树，利用红黑树快速插入、删除、查找的特点提高 HashMap 的性能。否则进行 resize() 扩容，当链表长度变小（默认小于6）时，红黑树转为链表。

    哈希函数

    HashMap 中的哈希计算逻辑会取 key 的 hashCode 值、高位运算、取模运算，得到 hash 值再计算下标。这种算法即减少系统开销，又有效减少 Hash 碰撞。因为有些数据计算出的哈希值差异主要在高位，而 HashMap 里的哈希寻址是忽略容量以上的高位的，那么这种处理就可以有效避免类似情况下的哈希碰撞

    1. static final int hash(Object key) {
    2.   int h;
    3.   return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    4. }

    之后，通过 (n-1)&hash 计算数组下标，其中 n 为数组长度
    image.png
    key.hashCode() 函数调用的是 key 键自带的哈希函数，返回 int 型散列值。理论上散列值是一个 int 型，如果直接拿散列值作为下标访问 HashMap 数组的话，考虑到 2 进制 32 位带符号的 int 值范围从 -2147483648 到 2147483648。前后加起来大概 40 亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的，所以这个散列值是不能直接拿来用的。

    为什么要右移 16 位？
    上面先右位移（>>>） 16 位，正好是 32bit 的一半，然后自己的高半区和低半区做异或（^），就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。由于混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。而且（^）这个符号生成的 0、1 值是比较平均的，各 50% 的几率（10、01 都是 1，11、00 都是 0），而位与（&）或位或（|）都是 25%、75% 的几率。

为什么要混合高位？
因为计算出哈希值后，我们还需要对 2 的幂次大小的数组进行一次取模计算，而对二的幂次取模相当于直接截取数字比较低的若干位，这在数组元素较少的时候，相当于只使用了数字比较低位的信息，而放弃了高位的信息，可能会增加冲突的概率。所以，JDK 的代码引入了^ h >>> 16 这样的位运算，这样我们在后续的取模时就可以用到高位的信息了。

1. 控制数组长度为2的整数次幂

HashMap 的 Entry 数组长度总是为 2 的整数次幂，那 HashMap 是如何进行控制的呢？

在 HashMap 中，修改数组长度总共有两种情况：

  • 初始化时指定的数组长度
  • 扩容时的长度增量

先看第一种情况。默认情况下，如未在 HashMap 构造器中指定长度时，默认初始长度为 16。16 是一个较为合适的经验值，太小会频繁触发扩容，太大又会浪费空间。如果在构造函数中指定一个非 2 的整数次幂的值，则会自动转化成大于该指定数的最小 2 的整数次幂。具体见 HashMap 调用的 tableSizeFor() 方法。

  1. public HashMap(int initialCapacity, float loadFactor) {
  2.     ......
  3.     this.loadFactor = loadFactor;
  4.     this.threshold = tableSizeFor(initialCapacity);
  5. }
  7. static final int tableSizeFor(int cap) {
  8.     int n = cap - 1;
  9.     n |= n >>> 1;
  10.     n |= n >>> 2;
  11.     n |= n >>> 4;
  12.     n |= n >>> 8;
  13.     n |= n >>> 16;
  14.     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  15. }

tableSizeFor() 方法看起来很复杂，作用是使得最高位 1 后续的所有位都变为 1，最后再加 1 则得到刚好大于 initialCapacity 的最小 2 的整数次幂数。如下图（这里使用了 8 位进行模拟，32 位也是同理）：
image.png
那为什么必须要对 cap 进行减 1 之后再进行运算呢？因为如果指定的数刚好是 2 的整数次幂的话，没有减 1 的结果会变成比他大两倍的数，比如：00100 —> 高位1之后全变1 —> 00111 —> 加1 —> 01000

第二种改变数组长度的情况是扩容。HashMap 每次扩容的大小都是原来的两倍，在扩容时控制了数组大小一定是 2 的整数次幂，相关源码如下：

  1. final Node<K,V>[] resize() {
  2.     ......
  3.     else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  4.             oldCap >= DEFAULT_INITIAL_CAPACITY)
  5.         newThr = oldThr << 1; // double threshold
  6. }

2. 哈希冲突解决方案

再优秀的 hash 算法永远无法避免出现 hash 冲突。hash 冲突指的是两个不同的 key 经过 hash 计算之后得到的数组下标是相同的。解决 hash 冲突的方式很多，如开放地址法、再哈希法、链地址法等。HashMap 采用的是链地址法，在 JDK 8 之后还增加了红黑树的优化，红黑树查找操作的时间复杂度为 O(logN)，但红黑树只有在数据量较大时才能发挥它的优势。

关于红黑树的转化，HashMap做了以下限制：

  • 当链表的长度 >=8 且数组长度 >=64 时，会把链表转化成红黑树
  • 当链表长度 >=8 但数组长度 <64 时，会优先进行扩容，而不是转化成红黑树
  • 当红黑树节点数 <= 6 时会回退到链表结构

那为什么需要数组长度到 64 才会转化红黑树呢？

当数组长度较短时，假如链表长度已经达到了 8，此时如果转化成红黑树，因为当前数组长度较短，很可能后续又会进行扩容操作，而之后的扩容会再一次把红黑树拆分平均到新的数组中，这样非但没有带来性能的好处，反而会降低性能。所以当数组长度低于 64 时，优先进行扩容。

为什么要大于等于 8 转化为红黑树，而不是 7 或 9？

树节点比普通节点更大，在链表较短时红黑树并未能明显体现性能优势，反而会浪费空间，在链表较短时采用链表而不是红黑树。在理论数学计算中，链表的长度到达 8 的概率是百万分之一，因此把 7 作为分水岭，大于 7 则转化为红黑树。红黑树的出现是为了在某些极端的情况下，抗住大量的 hash 冲突，正常情况下使用链表是更加合适的。

常用方法

  1. public V get(Object key)
  2. public boolean containsKey(Object key)
  3. public V put(K key, V value)
  4. public void putAll(Map<? extends K, ? extends V> m)
  5. public V remove(Object key)
  6. public boolean containsValue(Object value)
  7. public Set<K> keySet()
  8. public Collection<V> values()
  9. public Set<Map.Entry<K,V>> entrySet()
  11. // 返回指定键所映射到的值，如果key不存在则返回defaultValue    
  12. public V getOrDefault(Object key, V defaultValue)
  14. // 如果key不存在或者key对应的值为null则添加键值对，否则不处理   
  15. public V putIfAbsent(K key, V value)
  17. // 仅当当前key映射到指定值时，才删除指定键的条目  
  18. public boolean remove(Object key, Object value)
  20. // 仅当当前映射到指定值时，才替换指定键的条目    
  21. public boolean replace(K key, V oldValue, V newValue)
  22. // 如果key有映射值时，则进行替换     
  23. public V replace(K key, V value)
  25. // 如果key不存在或者key对应的值为null，则尝试使用给定的映射函数计算其值    
  26. public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)
  27. // 如果key存在且对应值非空，则尝试在给定键及其当前映射值的情况下计算新映射    
  28. public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)
  29. // 尝试为指定键及其当前映射值（如果没有当前映射，则为null）计算映射
  30. public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)
  32. // 合并指定key的value值
  33. public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)
  35. public void forEach(BiConsumer<? super K, ? super V> action)
  36. // 用该function的结果替换map中的每个key对应的值    
  37. public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)

1. put

添加一个元素只需要传入一个键和一个值即可，putVal() 方法是关键。

  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
  2.     // tab是HashMap内部数组，p是该下标对应的节点
  3.     Node<K,V>[] tab;
  4.     Node<K,V> p;
  5.     // n是数组的长度，i是要插入的下标
  6.     int n, i;
  7.     // 如果table数组还未被初始化，则调用resize方法进行初始化扩容
  8.     if ((tab = table) == null || (n = tab.length) == 0)
  9.         n = (tab = resize()).length;
  10.     // 根据键的hash值找到该键对应到数组中存储的索引位置，如果为null，则说明此索引位置没有被占用，可以直接插入
  11.     if ((p = tab[i = (n - 1) & hash]) == null)
  12.         tab[i] = newNode(hash, key, value, null);
  13.     // 不为null，说明此处已经被占用，只需要构建一个新节点插入到这个链表的尾部即可
  14.     else {
  15.         Node<K,V> e; K k;
  16.         // 如果当前结点和将要插入的结点的hash值和key值都相同，说明这是一次修改操作
  17.         if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
  18.             e = p;
  19.         // 如果这个头结点是红黑树结点的话，则以红黑树的插入形式进行插入
  20.         else if (p instanceof TreeNode)
  21.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  22.         // 遍历此链表，构建一个新的节点插入到该链表的尾部
  23.         else {
  24.             for (int binCount = 0; ; ++binCount) {
  25.                 if ((e = p.next) == null) {
  26.                     p.next = newNode(hash, key, value, null);
  27.                     // 如果插入新节点后链表长度大于等于8了，则将链表裂变成红黑树
  28.                     // 注意，treeifyBin方法中会进行数组长度判断，
  29.                     // 若小于64，则优先进行数组扩容而不是转化为树
  30.                     if (binCount >= TREEIFY_THRESHOLD - 1)
  31.                         treeifyBin(tab, hash);
  32.                     break;
  33.                 }
  34.                 // 遍历过程中，如果发现与某个结点的hash值和key值都相等，这依然是一次修改操作
  35.                 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
  36.                     break;
  37.                 p = e;
  38.             }
  39.         }
  40.         // 如果e不为null，说明当前的put操作是一次修改操作并且e指向的就是需要被修改的结点
  41.         if (e != null) {
  42.             V oldValue = e.value;
  43.             if (!onlyIfAbsent || oldValue == null)
  44.                 e.value = value;
  45.             afterNodeAccess(e);
  46.             return oldValue;
  47.         }
  48.     }
  49.     // 如果不是更新旧值，说明HashMap中键值对数量发生变化，modCount+1表示结构改变
  50.     ++modCount;
  51.     // 如果添加Node节点后，判断数组容量是否达到阈值，是则进行扩容
  52.     if (++size > threshold)
  53.         resize();
  54.     afterNodeInsertion(evict);
  55.     return null;
  56. }

下面通过画一张图总体再加深一下整个流程的印象：
image.png
当 bin 的数量大于 TREEIFY_THRESHOLD 时：

  • 如果容量小于 MIN_TREEIFY_CAPACITY，只会进行简单的扩容。
  • 如果容量大于 MIN_TREEIFY_CAPACITY，则会进行树化改造。

2. get

  1. 首先将 key 进行 hash 之后定位到对应的哈希桶。
  2. 如果桶为空直接返回 null，否则判断桶的链表头节点的 key 是否为要查询的 key，是就直接返回 value。
  3. 如果第一个不匹配，则判断它的结构是红黑树还是链表。如果是红黑树就按照树的查找方式返回值；否则按照链表的方式遍历查找返回值。
    1. final Node<K,V> getNode(int hash, Object key) {
    2.  Node<K,V>[] tab;
    3.  Node<K,V> first, e;
    4.  int n;
    5.  K k;
    6.  if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
    7.      // 检查头结点
    8.      if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
    9.          return first;
    10.      if ((e = first.next) != null) {
    11.          // 按红黑树的方式进行查找
    12.          if (first instanceof TreeNode)
    13.              return ((TreeNode<K,V>)first).getTreeNode(hash, key);
    14.          // 遍历链表的方式进行查找
    15.          do {
    16.              if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
    17.                  return e;
    18.          } while ((e = e.next) != null);
    19.      }
    20.  }
    21.  return null;
    22. }

    3. remove

    删除操作就是一个【查找+删除】的过程，相对于添加操作其实容易一些。
    1. final Node<K,V> removeNode(int hash, Object key, Object value,
    2.                         boolean matchValue, boolean movable) {
    3.  Node<K,V>[] tab; Node<K,V> p; int n, index;
    4.  // table数组不为空，并且索引处有值，执行查找操作
    5.  if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
    6.      Node<K,V> node = null, e; K k; V v;
    7.      // 如果跟头节点相等，则将待删除node指针指向头节点
    8.      if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
    9.          node = p;
    10.      else if ((e = p.next) != null) {
    11.          // 如果是红黑树，通过红黑树的操作方法获得node
    12.          if (p instanceof TreeNode)
    13.              node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
    14.          else {
    15.              // 否则遍历链表查找待删除的node
    16.              do {
    17.                  if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
    18.                      node = e;
    19.                      break;
    20.                  }
    21.                  p = e;
    22.              } while ((e = e.next) != null);
    23.          }
    24.      }
    25.      // 如果node不为空，执行删除操作
    26.      if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
    27.          // 如果是红黑树，则使用红黑树的方法进行删除
    28.          if (node instanceof TreeNode)
    29.              ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
    30.          // 如果是头节点，则直接将下一个节点设置为头节点
    31.          else if (node == p)
    32.              tab[index] = node.next;
    33.          else
    34.              // 否则，将头节点的下一个节点设置为待删除的下一个节点
    35.              p.next = node.next;
    36.          ++modCount;
    37.          --size;
    38.          afterNodeRemoval(node);
    39.          return node;
    40.      }
    41.  }
    42.  return null;
    43. }

    扩容方案

    当 HashMap 中的数据越来越多，那么发生 hash 冲突的概率也就会越来越高，因此通过数组扩容可以利用空间换时间的策略，将查找效率维持在常数时间复杂度。那什么时候会进行扩容呢？

实际上，HashMap 的扩容由一个关键参数控制：装载因子。装载因子 = HashMap 中节点数/数组长度，当达到装载因子比例时就会触发扩容；即装载因子控制了当前数组能够承载的节点数的阈值。如数组长度是 16，装载因子是 0.75，那么可容纳的节点数是 12。

装载因子的数值大小需要仔细权衡，装载因子越大，数组利用率越高，同时发生哈希冲突的概率也就越高；装载因子越小，数组利用率降低，但发生哈希冲突的概率也降低了。在理论计算中 0.75 是一个比较合适的数值，当大于 0.75 时哈希冲突概率呈指数级别上升，而小于 0.75 冲突减少并不明显。因此 HashMap 中装载因子的默认值是 0.75，在没有特殊要求的情况下不建议修改这个值。

那么在到达阈值后 HashMap 是如何进行扩容的呢？

首先 HashMap 会把数组长度扩展为原来的两倍，再把旧数组的数据迁移到新的数组，而 HashMap 针对迁移做了优化：使用 HashMap 数组长度是 2 的整数次幂的特点，以一种更高效的方式完成数据迁移。

JDK 7 之前的数据迁移比较简单，就是遍历所有的节点，把所有的节点依次通过 hash 函数重新计算新下标再插入到新数组的链表中。这样会有两个缺点：一是每个节点都需要进行一次求余计算；二是插入到新的数组时候采用的是头插入法，在多线程环境下会形成链表环。因此在 JDK 8 之后进行了优化，原因在于 HashMap 控制了数组的长度始终是 2 的整数次幂，每次扩展数组都是原来的 2 倍，带来的好处是 key 在新的数组的 hash 结果只有两种：在原来的位置或者在原来位置+原数组长度。具体为什么可以看下图：
image.png
从图中可以看到，在新数组中的 hash 结果，仅仅取决于高一位的数值。如果高一位是 0，那么计算结果就是在原位置，而如果是 1，则加上原数组的长度即可。这样只需要判断一个节点的高一位是 1 或 0 就可以得到他在新数组的位置，而不需要重复计算 hash 值。HashMap 把每个链表拆分成两个链表，对应原位置或原位置+原数组长度，再分别插入到新的数组中，保留原来的节点顺序，具体如下图所示：
image.png

1. resize

数组是无法自动扩容的，因此 resize() 方法使用一个新的数组代替已有的容量小的数组。扩容操作会重新进行内存的分配，并且会遍历 hash 表中的所有元素，是非常耗时的。

  1. final Node<K,V>[] resize() {
  2.     // 变量分别是原数组、原数组大小、原阈值；新数组大小、新阈值
  3.     Node<K,V>[] oldTab = table;
  4.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  5.     int oldThr = threshold;
  6.     int newCap, newThr = 0;
  7.     // 如果原数组长度大于0，说明不是初始化阶段的扩容，此时需要给旧数组扩容
  8.     if (oldCap > 0) {
  9.         // 如果原有数组的长度已经达到了容量限定的最大值，则不再扩容
  10.         if (oldCap >= MAXIMUM_CAPACITY) {
  11.             threshold = Integer.MAX_VALUE;
  12.             return oldTab;
  13.         }
  14.         // 如果还未达到最大值，则将数组容量扩大两倍，阈值也扩大两倍
  15.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
  16.             newThr = oldThr << 1; // double threshold
  17.     }
  18.     // 原数组长度为0，但最大限度不是0，则把数组长度设置为阈值
  19.     // 对应的情况就是新建HashMap的时候指定了数组长度
  20.     else if (oldThr > 0)
  21.         newCap = oldThr;
  22.     // 按默认值进行table数组和负载因子的初始化
  23.     else {
  24.         // 第一次初始化，默认初始容量为16、负载因子为0.75
  25.         // 对应使用默认构造器新建HashMap对象
  26.         newCap = DEFAULT_INITIAL_CAPACITY;
  27.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  28.     }
  29.     if (newThr == 0) {
  30.         float ft = (float)newCap * loadFactor;
  31.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  32.                   (int)ft : Integer.MAX_VALUE);
  33.     }
  34.     threshold = newThr;
  35.     @SuppressWarnings({"rawtypes","unchecked"})
  36.     // 根据新的容量初始化一个新的node数组
  37.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  38.     table = newTab;
  39.     // 如果旧数组不为null，表示这次的resize是一次扩容行为，而非初始化
  40.     if (oldTab != null) {
  41.         // 将旧数组中的每个节点位置相对静止地拷贝到新数组中
  42.         for (int j = 0; j < oldCap; ++j) {
  43.             Node<K,V> e;
  44.             // 获取头结点
  45.             if ((e = oldTab[j]) != null) {
  46.                 oldTab[j] = null;
  47.                 // 如果他没有后继节点，则说明链表或红黑树只有一个头结点，转移至新表
  48.                 if (e.next == null)
  49.                     newTab[e.hash & (newCap - 1)] = e;
  50.                 // 如果e是红黑树结点，红黑树分裂，转移至新表
  51.                 else if (e instanceof TreeNode)
  52.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  53.                 // 这部分是将链表中的各个节点原序地转移至新表中
  54.                 // 新的位置只有两种可能：原位置，原位置+老数组长度
  55.                 // 把原链表拆成两个链表，然后再分别插入到新数组的两个位置上，不用多次调用put方法
  56.                 else {
  57.                     ......
  58.                 }
  59.             }
  60.         }
  61.     }
  62.     // 返回新数组
  63.     return newTab;
  64. }

由代码可知，每次扩容都会扩容一倍的数量，所以元素的位置要么在原位置，要么在原位置移动 oldCap 的位置上。因此我们在扩容 HashMap 的时候，不需要重新计算 hash 值（JDK 1.8 以前要重新计算 hash 值），只需要看原来的 hash 值高位新增的那个 bit 是 1 还是 0，是 0 的话索引不变，是 1 的话索引变成“原索引+oldCap”, 因此原链表将直接拆分为高低链表。

这样既省去了重新计算 hash 值的时间，而且由于新增的 bit 是 0 还是 1 可以被认为是随机的，因此 resize 的过程均匀的把之前冲突的节点分散到新的 bucket 了。
image.png

2. 扩容产生的问题

在 JDK 7 的时候，HashMap 的 resize() 方法在扩容过程中移动元素时，会将元素放在链表的头部，而不是放在尾部，这样做是为了避免尾部遍历，因此链表中存储的元素次序会反过来。但这样的方式在多线程调用的情况下可能会存在条件竞争，如果条件竞争发生了可能会出现环形列表，那么当我们调用 get(key) 操作时就可能会发生死循环了。
image.png

参考链接：https://coolshell.cn/articles/9606.html
参考链接：https://mailinator.blogspot.com/2009/06/beautiful-race-condition.html

而在 JDK 8 中，HashMap 采用了尾插法的方式，在扩容时会保持链表元素原本的顺序，并且不会出现在并发情况下链表成环的问题了。