本文内容均转载自网络，版权所有归原作者。
参考文章:
- 从基础到实践，一文带你看懂HashMap: 未转载进本文，但可跳转阅读参考
- HashMap源码分析
- HashMap加载因子及转红黑树探究
HashMap源码分析/HashMap数据结构及2的整数次幂探究/HashMap探究（一）
HashMap 的数据结构
- JDK1.7：数组+链表
- JDK1.8：hash表=数组+链表+红黑树
什么是哈希表？
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
HashMap添加元素分析
在HashMap中，当添加元素时，会通过哈希值和数组的长度来计算得出一个计算下标，用它来准确的定位该元素应该put的位置。通常，我们为了使元素分布均匀会使用取模运算，用一个值去模上总长度，例如：
index = hashCode % arr.length //实际并非这样，后面讲解
计算出index后，就会将该元素添加进去，理想状态下是将每个值都均匀的添加到数组中，但问题是不可能达到这样的理想状态，这时候就会产生哈希冲突。例如：大狂神通过计算添加到了数组3号位置；
但是，此时佩雨这个元素通过计算产生了一个与大狂神相同的索引位置，这是就产生了哈希冲突；于是此时，就产生了第二种数据结构——链表，冲突的元素会在该索引处以链表的形式保存；
了解：解决Hash冲突四个方法
1、开放定址法（以冲突的下标为基础再次记算hash，直到不冲突）
这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
2、重Hash法（多个hash函数，一个hash函数计算出来的索引冲突了就换一个函数记算，直到不冲突）
这种方法是同时构造多个不同的哈希函数，当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
3、链地址法
这种方法的基本思想是将所有哈希地址为 i 的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
4、建立公共溢出区
将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。
红黑树
之前的情况，当链表的长度过长时，其固有弊端就显现出来了，即查询效率较低，链表查询的时间复杂度是O(n),数组的查询时间复杂度是O(1)，链表查询效率非常低，所以就引出了第三种数据结构——红黑树，链表长度>=8时链表转为红黑树，红黑树是一棵接近于平衡的二叉树，其查询时间复杂度为O(logn)，远远比链表的查询效率高。
思考：那为什么要在链表长度大于等于8的时候变成红黑树呢？
如果链表的长度没有达到这个长度的话，因为红黑树它自身的这种维护，插入的这种维护的开销也是非常大的，因为每次一去插入一个元素的时候很有可能会破坏掉他的平衡。也就是说hashmap的 put 操作非常多的时候，极有可能会影响插入的性能，因为插入一个元素的话，极有可能会打破它原有的平衡，那么每时每刻它都需要再恢复平衡（也就是红黑树的再平衡，需要左旋右旋，以及重新着色），就非常影响性能；
为什么数组的长度必须是2的指数次幂
hashmap中数组的初始长度（如果不传参，默认为16）
/** * The default initial capacity - MUST be a power of two. * 秦疆翻译：默认初始容量-必须是2的幂 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
**最大容量：**如果具有参数的任一构造函数隐式指定，则使用最大容量。必须是2的幂且 <= 1 << 30。
/** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */
static final int MAXIMUM_CAPACITY = 1 << 30;
如果我们传入的初始容量不是2的指数次幂，他就会将这个数改成大于该数且最接近这个数的2的指数次幂
比如以下这段代码：
HashMap<Object, Object> map = new HashMap<>(13);
map.put("秦疆","Java");
传入的初始容量是13，他就会将13转换为大于13且最接近13的2的指数次幂的一个数：
13----->16
再比如：
7 ----->8
5 ----->8
3 ----->4
源码分析
当我们使用构造方法传进来一个初始容量的值initialCapacity，默认会传入一个加载因子0.75；
/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and the default load factor (0.75). */
public HashMap(int initialCapacity) {
//默认的加载因子仍是0.75，其通过this关键字调用了本类的另外一个重载方法
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
继续追踪分析代码：
public HashMap(int initialCapacity, float loadFactor) {
//1.这里会先判断传来的初始容量是不是小于零的数字。如果是直接抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
//2.再判断是不是超过了hash定义的最大容量2的30次幂，如果超过了则让其等于最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//3.再接着判断传来的加载因子,如果小于零或者不是一个数字直接抛出异常。
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
//4.然后调用了一个tableSizeFor()方法去处理传进来的初始容量
this.threshold = tableSizeFor(initialCapacity);
}
继续追踪分析代码：进入到tableSizeFor()方法 ： 这个处理初始容量的方法；
/** * Returns a power of two size for the given target capacity. * 它的作用是返回一个大于输入参数,且最接近的2的整数次幂的数 */
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
/* 解释下这个算法 ： 需要先了解： 右移 和 位或这里使用的是位运算：假设n的二进01xxx…xxx；先对n右移1位则结果为：001xx…xxx，再进行位或结果为：011xx…xxx；再对n右移2位则结果为：00011…xxx，再进行位或结果为：01111…xxx；此时前面已经有四个1了，再右移4位，然后进行位或可得8个1；同理，有8个1，再右移8位，然后进行位或肯定会让后八位也为1；综上可得，该算法让最高位的1后面的位全变为1。最后再让结果n+1，即得到了2的整数次幂的值了。而最开始：cap-1再赋值给n的目的是：让找到的目标值 >= 原值*/
解释：HashMap为了实现存取高效，要尽量减少碰撞，就是要尽量做到：把数据分配均匀，保证每个链表长度大致相同，我们就需要一个算法来实现：将存入的数据保存到那个链表中的算法；而这个算法实际就是取模：hash%length
但是，大家都知道这种运算不如位移运算快。因此，源码中做了优化 hash&(length-1)。
也就是说 hash%length==hash&(length-1)
那为什么是2的n次方呢？
因为2的n次方实际就是1后面n个0，而2的n次方-1，实际就是n个1。
例如长度为8时候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞。而长度为5的时候，3&(5-1)=0 2&(5-1)=0，都在0上，出现碰撞了。所以，保证容积是2的n次方，是为了保证在做(length-1)的时候，每一位都能 &1 ，也就是和1111……1111111进行与运算。即：两位同时为“1”，结果才为“1”，否则为0
那么为什么要把初始容量转成2的指数次幂呢？不转成2的指数次幂也是可以存储的啊，为什么要转？
首先看HashMap的put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
其中的hash方法用于计算key的哈希值；
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
关于这个Hash的思考
为什么为什么要先高16位异或低16位再取模运算?
hashmap这么做，只是为了降低hash冲突的几率。
打个比方，当我们的length为16的时候，哈希码(字符串“abcabcabcabcabc”的key对应的哈希码) 和 (16-1)进行与操作，对于多个key生成的hashCode，只要哈希码的后4位为0，不论不论高位怎么变化，最终的结果均为0。因为与运算中两位同时为“1”，结果才为“1”，否则为0; 如下：
而加上高16位异或低16位的“扰动函数”后，结果如下
可以看到: 扰动函数优化前：1954974080 % 16 = 1954974080 & (16 - 1) = 0 扰动函数优化后：1955003654 % 16 = 1955003654 & (16 - 1) = 6 很显然，减少了碰撞的几率。
我们一开始提到过，添加元素时索引的下标可以通过取模运算获得，但是我们知道计算机的运行效率：加法(减法)>乘法>除法>取模，取模的效率是最低的。所以我们要在HashMap中避免频繁的取模运算，又因为在我们HashMap中他要通过取模去定位我们的索引，并且HashMap是在不停的扩容，数组一旦达到容量的阈值的时候就需要对数组进行扩容。那么扩容就意味着要进行数组的移动，数组一旦移动，每移动一次就要重回记算索引，这个过程中牵扯大量元素的迁移，就会大大影响效率。那么如果说我们直接使用与运算，这个效率是远远高于取模运算的！
putVal方法，它是实现具体的put操作的方法
再来看putVal方法，它是实现具体的put操作的方法,来看一下源码；
//实现put操作
//返回值: @return 之前的value
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//1. 如果当前table为空，新建默认大小的table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2. 获取当前key对应的节点
if ((p = tab[i = (n - 1) & hash]) == null)
//3. 如果不存在，新建节点
tab[i] = newNode(hash, key, value, null);
else {
//4. 存在节点
Node<K,V> e; K k;
//5. key的hash相同，key的引用相同或者key equals，则覆盖
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//6. 如果当前节点是一个红黑树树节点，则添加树节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//7. 不是红黑树节点，也不是相同节点，则表示为链表结构
else {
for (int binCount = 0; ; ++binCount) {
//8. 找到最后那个节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//9. 如果链表长度超过8转成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//10.如果链表中有相同的节点，则覆盖
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
//是否替换掉value值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//记录修改次数
++modCount;
//是否超过容量，超过需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
由以上源码第2步，tab[i = (n - 1) & hash]中tab就是HashMap的实体数组，其下边通过i = (n - 1) & hash来获取（n表示数组长度，hash表示hashCode值），但是这必须保证数组长度为2的整数次幂，我们继续往下看
现在我们可以使用与运算(n-1) & hash取代取模运算hash%length，因为这两种方式记算出来的结果是一致的（n就是length），也就是(length-1)&hash = hash%length，例如：假设数组长度为4，哈希值为10
(n-1) & hash = (4-1) & 10 = 00000011 & 00001010 = 00000010 = 2
hash % length = 10 % 4 = 2
但是当数组的长=长度不为2的指数次幂时，两种方式计算的结果不一样，即（length-1)&hash ≠ hash&length
例如：再假设数组长度为5，哈希值10
(n-1) & hash = (5-1) & 10 = 00000100 & 00001010 = 00000000 = 0
hash % length = 10 % 5 = 2
显然，当数组长度不为2的整数次幂时二者是不相等的！
但最重要的一点，是要保证定位出来的值是在数组的长度之内的，不能超出数组长度，并且减少哈希碰撞，让每个位都可能被取到，我们来看下面例子：
例如：(16-1) & hash
二进制的15： 0000 0000 0000 1111
hash(随机) 1101 0111 1011 0000
hash(随机) 1101 0111 1011 1111
结果 0000 0000 0000 0001 ~ 0000 0000 0000 1111
即得出的索引下标只能在0~15之间，保证了所有索引都在数组长度的范围内而不会越界
并且由于2的指数次幂-1都是...1111的形式的，即最后一位是1
这样，由于hash是随机的，进行与运算后每一位都是能取到的
========================================================================
反例：(7-1) & hash
二进制6： 0000 0000 0000 0110
hash 1011 1001 0101 0000
hash 1001 0001 0000 1111
结果 0000 0000 0000 0000 ~ 0000 0000 0000 0110
即得出的索引范围在0~6，虽然不会越界，但最后一位是0
即现在无论hash为何值，0001，0011，0101这几个值是不可能取到的
这就加剧了hash碰撞，并且浪费了大量数组空间，显然是我们不想看到的
总结：首先使用位运算来加快计算的效率，而要使用位运算，就需要数组-1然后与hash值保证其在数组范围内，只有当数组长度为2的指数次幂时，其计算得出的值才能和取模算法的值相等，并且保证能取到数组的每一位，减少哈希碰撞，不浪费大量的数组资源！
HashMap加载因子及转红黑树探究/HashMap探究（二）
今天我们来探究下：负载因子为什么是0.75？为什么红黑树扩容是当链表长度>=8时扩容？Java7的hashmap扩容死锁演示与环链形成分析？
负载因子为什么是0.75？
我们先来看看源码：在构造函数中未指定时使用的加载因子
/** * The load factor used when none specified in constructor. */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
我们知道，最理想的情况就是，当我们put进来的元素刚好平铺在数组上，而不产生链表，尽量不产生 Hash 碰撞。但是我们明白这种情况只是理想化的，是难以实现的。
那么我们反证一下：当我们将负载因子不定为0.75的时候（两种情况）：
1、 假如负载因子定为1（最大值），那么只有当元素填慢数组长度的时候才会选择去扩容，虽然负载因子定为1可以最大程度的提高空间的利用率，但是我们的查询效率会变得低下（因为链表查询比较慢）
结论：所以当加载因子比较大的时候：节省空间资源，耗费时间资源
2、加入负载因子定为0.5（一个比较小的值），也就是说，知道到达数组空间的一半的时候就会去扩容。虽然说负载因子比较小可以最大可能的降低hash冲突，链表的长度也会越少，但是空间浪费会比较大
结论：所以当加载因子比较小的时候：节省时间资源，耗费空间资源
但是我们设计程序的时候肯定是会在空间以及时间上做平衡，那么我们能就需要在时间复杂度和空间复杂度上做折中，选择最合适的负载因子以保证最优化。所以就选择了0.75这个值，Jdk那帮工程师一定是做了大量的测试，得出的这个值吧~
为什么红黑树扩容是当链表长度>=8时扩容
看源码：当链表数量大于8时转化为树
/** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. * 树阈值 = 8； */
static final int TREEIFY_THRESHOLD = 8;
泊松分布
当我们在put一个元素，产生hash冲突的时候，会遵循泊松分布（通过概率学统计出来）的规则;
泊松分布公式：(exp(-0.5) * pow(0.5, k)
泊松分布图：
意思就是说，当负载因子为0.75的时候，还有当链表的长度的增加。如果再添加新的节点进链表的时候，这个添加进当前链表概率是随着节点的增加而越来越少（泊松分布）。JDK源码中有这样的解释：
也就是说，当put进来一个元素，通过hash算法，然后最后定位到同一个桶（链表）的概率会随着链表的长度的增加而减少，当这个链表长度为8的时候，这个概率几乎接近于0，所以我们才会将链表转红黑树的临界值定为8
当然，虽然在hashmap底层有这种红黑树的结构，但是我们要知道能产生这种结构的概率也不大，所以我们知道在 JDK1.7 到 JDK1.8 这其中HashMap的性能只提高了 7%-8% 左右，提高的并不多。
Java7的hashmap扩容死锁演示与环链形成分析
Java7的hashmap扩容死锁演示与环链形成分析
我们首先来看一下JDK1.7中put方法的源码
我们打开addEntry方法如下，它会判断数组当前容量是否已经超过的阈值，例如假设当前的数组容量是16，加载因子为0.75，即超过了12，并且刚好要插入的索引处有元素，这时候就需要进行扩容操作，可以看到resize扩容大小是原数组的两倍，仍然符合数组的长度是2的指数次幂
我们再进入resize方法如下，它首先会对之前的数组容量进行判断，看是否已经达到了数组最大容量，如果没有，后面会进行数组的转移操作，即transfer方法
JDK1.7中，当数组容量达到16*0.75=12的时候，数组就需要扩容，在扩容的时候，我们都知道会涉及元素的迁移，那么下面代码就是元素迁移的主要代码：JDK1.7中HashMap存在死锁问题的原因也主要集中在这
//将老的表中的数据拷贝到新的结构中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;//容量
for (Entry<K,V> e : table) { //遍历所有桶：即数组
while(null != e) { //遍历桶中所有元素（是一个链表）
Entry<K,V> next = e.next;
if (rehash) {//如果是重新Hash，则需要重新计算hash值
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);//定位Hash桶
e.next = newTable[i];//元素连接到桶中,这里相当于单链表的插入，总是插入在最前面
newTable[i] = e;//newTable[i]的值总是最新插入的值
e = next;//继续下一个元素
}
}
}
我们将重新记算hash值的逻辑先去掉（回顾：为什么使用位运算而不使用取模运算：因为位运算效率高，取模运算效率低，在数组迁移的时候会进行重hash，如果效率不高会极大的影响put的效率）。只留下主要的迁移数组的代码：
for (Entry<K,V> e : table) { //遍历所有桶
while(null != e) { //遍历桶中所有元素（是一个链表）
Entry<K,V> next = e.next;
e.next = newTable[i];//元素连接到桶中,这里相当于单链表的插入，总是插入在最前面
newTable[i] = e;//newTable[i]的值总是最新插入的值
e = next;//继续下一个元素
}
}
举例：
假设有两个线程，两个线程都对这个hashmap进行扩容，扩容就要执行数组迁移代码。
假设线程T2先来对数组进行迁移，当线程而二执行到Entry<K,V> next = e.next的时候，然后线程T2突然阻塞了;
外层for循环来遍历数组的，当数组的值不是空的时候就进入内层的while循环去遍历链表，假设线程T2两个指针（一个叫做e2，一个叫做next2），当遍历到这个结点的时候：e2表示的就是大狂神这个节点，next2表示e2的下一个节点，也就是佩雨的这个节点；
然后刚好线程T1也跑进啦这个逻辑里面了，那么线程T1也有两个指针（e，next），e也指向的是大狂神，next也指向的是佩雨
T1线程继续跑这个逻辑（下面是T1线程自己的扩容与迁移图），会继续转移这个链表，转移完成之后发现一个问题：转移过去后两个节点的上下位置反了（大狂神和佩雨已经反了）
然后T2这个时候又唤醒了，因为线程T2一直都是指向这两个元素的（e2–>大狂神，next–>佩雨），也就是成下图这样
然后T2也要去循环执行这个逻辑
e.next = newTable[i];//元素连接到桶中,这里相当于单链表的插入，总是插入在最前面
newTable[i] = e;//newTable[i]的值总是最新插入的值
e = next;//继续下一个元素
最后会产生这样的情况，就是最终会形成一个环
Java8中的HashMap扩容优化（不会出现死环）
JDK1.8中HashMap扩容的代码
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.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
然后用当前节点的hash值和旧数组的长度（16）做’与’运算
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
分析：
hash值： 0010 1111 1010 1110
数组的长度(16) 0000 0000 0000 1000
‘与’运算的结果，只可能有两种值：
0000 0000 0000 0000---------------0
0000 0000 0000 1000---------------16
也就是说当前节点用当前节点的hash值和旧数组的长度（16）做'与'运算的结果只可能是0或16
用当前节点的hash值和旧数组的长度（16）做’与’运算，结果出来如果时0就是低位指针，如果是16就是高位指针，那么我们再看：
// 如果是0，则使用低位的指针
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else { // 如果是16，则使用高位的指针
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
如果说 ‘与’ 出来的值是0，那么就会用低位的指针去迁移该数组。如果判断出来的是16，就会用高位的指针去迁移。
那么我们的最终的指针就会成下面的样子：
然后就开始迁移
低位迁移：首先：先将高位和低位断开（将低位的尾部的next置为空）
if (loTail != null) {
//把低位的尾部节点的next值为空（先将高位和低位断开）
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
就成下面这样了：
紧接着将低位的头部loHead付给新数组的某个值，也就是将低位的所有节点移动过去，并且放在与就索引相同的位置；
if (loTail != null) {
//把低位的尾部节点的next值为空（先将高位和低位断开）
loTail.next = null;
newTab[j] = loHead; //将高位的头部赋给新数组的某个值，也就是将高位的所有节点移动过去
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
高位迁移：先将高位的尾部断开
if (loTail != null) {
//把低位的尾部节点的next值为空（先将高位和低位断开）
loTail.next = null;
newTab[j] = loHead; //将高位的头部赋给新数组的某个值，也就是将高位的所有节点移动过去
}
if (hiTail != null) {
hiTail.next = null; //把高位的尾部节点的next值为空
newTab[j + oldCap] = hiHead;
}
再将高位的头部放到新数组的j + oldCap索引处（当前索引+旧数组的长度），比如说现在的索引是3，再加上数组长度16，最后就是将高位放到新数组的索引为19的地方去；
然后我们发现这个设计非常的巧妙，避免了顺序的颠倒，再也不会出现狂神和佩雨颠倒的问题了
总结
在JDK1.8之后，HashMap底层的数组扩容后迁移的方法进行了优化。把一个链表分成了两组，分成高为和低位分别去迁移，避免了死环问题。而且在迁移的过程中并没有进行任何的rehash（重新记算hash），提高了性能。它是直接将链表给断掉，进行几乎是一个均等的拆分，然后通过头指针的指向将整体给迁移过去，这样就减小了链表的长度
Q.E.D.
