本文主要基于jdk1.8去解析hashmap的源码
一、概述：
1、hashmap的基本特性
HashMap 底层是基于
数组 + 链表组成的，不过在 jdk1.7 和 1.8 中具体实现稍有不同。1.8的链表当长度大于8时转换为红黑树，长度小于6时转换为链表。（7对于链表的平均查找和红黑树的平均查找都差不多，所以可以防止在链表和红黑树之间频繁转换消耗内存，即7相当于给转换设置了一个缓冲区。）HashMap是基于哈希表实现的,每一个元素是一个key-value对,其内部通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长.
HashMap是非线程安全的,只适用于单线程环境,多线程环境可以采用并发包下的concurrentHashMap
HashMap 实现了Serializable接口，因此它支持序列化，实现了Cloneable接口，能被克隆(这里是深拷贝)
HashMap是基于哈希表的Map接口的非同步实现.此实现提供所有可选的映射操作,并允许使用null值和null键.此类不保证映射的顺序,特别是它不保证该顺序恒久不变.（无序的）
Java8中又对此类底层实现进行了优化，比如引入了红黑树的结构以解决哈希碰撞、头插法变为尾插法解决死循环等等
2、jdk1.7、1.8的源码
3、jdk1.7到1.8改变了什么，这些改变解决了什么问题？1.7到1.8没改变且重要的知识点？
4、jdk1.8后hashmap还存在什么问题？需要怎么去解决currenthashmap？？
二、源码分析
1、HashMap最常见的实现方法是拉链法——即一系列链表为数组元素组成的数组。如图：（使用数值+链表实现）
从上图我们可以看到，HashMap由链表+数组组成（1.8当链表长度大于等于8则转红黑树、小于等于6转链表），他的底层结构是一个数组，而数组的元素是一个单向链表。图中是一个长度为16位的数组，每个数组储存的元素代表的是每一个链表的头结点。
上面我们说了有关Hash算法的事情，通过Key进行Hash的计算，就可以获取Key对应的HashCode。好的Hash算法可以计算出几乎出独一无二的HashCode，如果出现了重复的hashCode，就称作碰撞，就算是MD5这样优秀的算法也会发生碰撞，即两个不同的key也有可能生成相同的MD5。
正常情况下，我们通过hash算法，往HashMap的数组中插入元素。如果发生了碰撞事件，那么意味这数组的一个位置要插入两个或者多个元素，这个时候数组上面挂的链表起作用了，链表会将数组某个节点上多出的元素按照尾插法(jdk1.7及以前为头插法)的方式添加。
下面去看hashmap的底层源码结构和实现
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
......
//默认初始容量为16，这里这个数组的容量必须为2的n次幂。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量为2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//以Node<K,V>为元素的数组，也就是上图HashMap的纵向的长链数组，起长度必须为2的n次幂
//存放真实的数据
transient Node<K,V>[] table;
//已经储存的Node<key,value>的数量，包括数组中的和链表中的
transient int size;
//扩容的临界值，或者所能容纳的key-value对的极限。当size>threshold的时候就会扩容
int threshold;
//加载因子
final float loadFactor;
......①DEFAULT_INITIAL_CAPACITY&MAXIMUM_CAPACITY
首先当我们通过无参的构造函数new一个hashMap的时候，系统就会帮我们指定你HashMap的默认大小为DEFAULT_INITIAL_CAPACITY也就是16，当然我们可以刻自己制定初始容量的大小，只不过要注意必须是2n且小于MAXIMUM_CAPACITY(
)。
②DEFAULT_LOAD_FACTOR&loadFactor
LOAD_FACTOR(负载因子)和上面的CAPACITY(容量)的关系，简单来说,Capacity就是数组的长度/大小，loadFactor是这个数组填满程度的最大比比例。同样的，我们可以根据有参的HashMap构造函数来指定初始负载容量的大小，如果不指定，默认的负载因子为0.75。
③size&threshold
size表示当前HashMap中已经储存的Node<key,value>的数量，包括数组和链表中的的Node<key,value>。threshold表示扩容的临界值，如果size大于这个值，则必需调用resize()方法进行扩容，具体的扩容过程我们之后会讲。
这里先说一下threshold值是怎么得到的，在jdk1.7及以前，threshold = length * Load factor，其中length为数组的长度，也就是说数组的长度成负载因子的数量。这里需要说明一点，默认负载因子0.75是是对空间和时间(纵向横向)效率的一个平衡选择，建议大家不要修改。而在jdk1.8中，这个值的计算算法得到了进一步改进，成了这个：
/** * Returns a power of two size for the given target capacity. */ 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; }cap是我们初始传递的Capacity值(或者默认的
)，看注释我们可以知道，这么一系列位移操作算法最后是为了得到一个power of two size的值。为什么jdk中一再要强调这个
④Node<K,V>[] table
最后来重点说说这个Node<K,V>[] table，他是整个HashMap的组成子元素，是构成HashMap的一砖一瓦：
static class Node<K,V> implements Map.Entry<K,V> { final int hash; //每个储存元素key的哈希值 final K key; //key V value; //value Node<K,V> next; //链表下一个node Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; ...... } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { ...... } public final V setValue(V newValue) { ...... } public final boolean equals(Object o) { ....... } }可以看到，这个Node<K,V>[]是HashMap的一个内部类，他既是HashMap底层数组的组成元素，又是每个单向链表的组成元素。它其中包含了数组元素所需要的key与value，以及链表所需要的指向下一个节点的引用域next。当然这个hash值是系统在创建Node时通过一定的算法计算出来的一个int值，之后我们会讲。
2.HashMap的构造函数
jdk1.8中，HashMap共有四种构造函数:
public HashMap(int initialCapacity, float loadFactor) {//传入初始大小和负载因子
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
//负载因子 loadFactor);
this.loadFactor = loadFactor;
//这里的tableSizeFor(initialCapacity)传进去初始大小，然后调用tableSizeFor方法计算扩容的临界值，然后返回给threshold。
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {//默认负载因子
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}3.HashMap的put添加功能实现：（即增加操作源码）
上面逻辑图主要步骤：
①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，执行resize()扩容
下面进入源码分析
public V put(K key, V value) {
//传入一个元素key、value，此时调用hash（key）产生hash值
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i; //tab[]为数组，p是每个桶
① if ((tab = table) == null || (n = tab.length) == 0) //第一步，table为空，则调用resize()函数创建一个，n为初始长度
n = (tab = resize()).length;
② if ((p = tab[i = (n - 1) & hash]) == null) //第二步，计算元素所要储存的位置index,并对null做出处理。（即要存储的数组下标处为null，则创建一个node元素处理）
//注意这里，如果tab[i]==null，说明这个位置上没有元素，这个时候就创建一个新的Node元素
tab[i] = newNode(hash, key, value, null);
else { //else,否则，也就是，这个要添加的位置上面已经有元素了，也就是发生了碰撞。这个时候就要具体情况分
//分类讨论：1.key值相同，直接覆盖 2.链表已经超过了8位，变成了红黑树 3.链表是正常的链表
Node<K,V> e; K k;
if (p.hash == hash && //如果节点key存在，则覆盖原来位置的key（此时key填充完）
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //将p链先赋给e
③ else if (p instanceof TreeNode) //第三步，判断该链是否为红黑树，是则调用用红黑树对应的put方法
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //最后则tab和p不为空，且链不是红黑树，即链为单向链表
for (int binCount = 0; ; ++binCount) {//循环计算该链表的长度
if ((e = p.next) == null) {//如果p.next为null（即循环到p链的最后一个元素了），则直接将传进来的接到最后一个的next去
p.next = newNode(hash, key, value, null);
//链表长度大于8转换为红黑树（调用相应方法）
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果节点key存在，则覆盖原来位置的key，同时将原来位置的元素，沿着链表向后移一位（这里是先用e记录该节点然后在下面进行value值的替换）
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;//将p.next传给下一次循环的p，即向下循环p链
}
}
if (e != null) { // existing mapping for key//这里进行上面记录的相同key的节点的value值的替换
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
④ resize(); //第四步：超过最大容量限制，扩容
afterNodeInsertion(evict);
return null;
}上面代码中加了一些注释，希望读者仔细分析这段代码中的逻辑。可以看到，我们将put一个元素的过程分为四步，下面我们分步骤讲解：
第一步：table为空，则调用resize()函数创建一个
这里的table就是我们在第一大点“HashMap基本元素”中说的Node<K,V>[] table;也就是HashMap的基本子节点。关于这个元素，这里还需要多说一点，在他声明的地方有一段注释:
/** * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics that are currently not needed.) */ transient Node<K,V>[] table;其中明确提到:这个table数组在第一次使用时需要初始化。在JDK1.7中源码的构造函数中，我们发现：
public HashMap(int initialCapacity, float loadFactor) { ...... this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; //注意这里初始化了 init(); }也就是说，在jdk1.7中，当HashMap创建的时候，table这个数组确实会初始化；但是到了jdk1.8中，我们观察上面四个构造函数，除了第四个构造函数调用了resize()外，其他三个常用的构造函数都没有与table初始化相关的迹象，而真正table初始化的地方是在我们上面讲的putVal()方法中，即首次向HashMap添加元素时，调用resize()创建并初始化了一个table数组。
这里笔者的理解是，类似于“懒加载”，用的时候再初始化，这样有利于节省资源~~同时，估计1.7和1.8的代码不是一个工程师写的吧，代码优化之后注释忘了改...关于resize()方法，我们之后再讲。
第二步：计算元素所要储存的位置index,并对null做出处理
储存位置即研究这个这个新添加的元素是通过何种规则添加到什么位置的，我们注意到这句源码:
p = tab[i = (n - 1) & hash]可以看到，index = (n - 1) & hash。n是新创建的table数组的长度：(tab = resize()).length;，那么hash是什么呢？注意到这两段代码:public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { ......可以看待，hash是由hash(key)这个方法计算所得：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }这里可以看到，首先将得到key对应的哈希值：
h = key.hashCode()，然后通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)我们分布来讲解这个index产生的步骤:(1).取key的hashcode值：
①Object类的hashCode
返回对象的经过处理后的内存地址，由于每个对象的内存地址都不一样，所以哈希码也不一样。这个是native方法，取决于JVM的内部设计，一般是某种C地址的偏移。
②String类的hashCode
根据String类包含的字符串的内容，根据一种特殊算法返回哈希码，只要字符串的内容相同，返回的哈希码也相同。
③Integer等包装类
返回的哈希码就是Integer对象里所包含的那个整数的数值，例如Integer i1=new Integer(100)，i1.hashCode的值就是100 。由此可见，2个一样大小的Integer对象，返回的哈希码也一样。
④int，char这样的基础类
它们不需要hashCode，如果需要存储时，将进行自动装箱操作，计算方法包装类。(2).hashCode()的高16位异或低16位
在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。
(3). (n-1) & hash; 取模运算
这个n我们说过是table的长度，那么n-1就是table数组元素应有的下标。这个方法非常巧妙，它通过hash & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，hash&(length-1) 运算等价于对length取模，也就是hash % length，但是&比%具有更高的效率。
关于为什么要先高16位异或低16位再取模运算，我们这里先看第三步：
我们知道，n代表的是table的长度length，之前一再强调，表table的长度需要取2的整数次幂，就是为了这里等价这里进行取模运算时的方便——取模运算转化成位运算公式:a%(2^n) 等价于 a&(2^n-1),而&操作比%操作具有更高的效率。
当length=2n时，(length - 1)正好相当于一个"低位掩码","与"操作的结果就是散列值的高位全部归零，只保留低位，用来做数组下标访问:
低位&运算.png
可以看到，当我们的length为16的时候，哈希码(字符串“abcabcabcabcabc”的key对应的哈希码)对(16-1)与操作，对于多个key生成的hashCode，只要哈希码的后4位为0，不论不论高位怎么变化，最终的结果均为0。也就是说，如果支取后四位(低位)的话，这个时候产生"碰撞"的几率就非常大(当然&运算中产生碰撞的原因很多，这里只是举个例子)。为了解决低位与操作碰撞的问题，于是便有了第二步中高16位异或低16位的“扰动函数”。
右移16位，自己的高半区和低半区异或，就是为了混合原始哈希码的高位和低位，以此来加大低位随机性。
“扰动”后&操作.png
可以看到:
扰动函数优化前：1954974080 % 16 = 1954974080 & (16 - 1) = 0
扰动函数优化后：1955003654 % 16 = 1955003654 & (16 - 1) = 6
很显然，减少了碰撞的几率。
第三步，判断该链是否为红黑树并添加元素（尾插法）
else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //是红黑树 else { for (int binCount = 0; ; ++binCount) { //不是红黑树而是链表 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } }关于是红黑树的部分，不在我们本节的讨论范围之内，我们主要看else里边的内容:
for (int binCount = 0; ; ++binCount) {表示循环遍历链表，这个for循环当中实际上经历了以下几个步骤：
①e = p.next以及for语句之外后面的p = e;实际上是在向后循环遍历链表。
开始的时候P为每个桶的头元素，然后将P的引用域(本来指向的是下一个元素)指向空节点e，这个时候实际上就相当于将p的下一个元素赋值给了e,即e已经变成了p的下一个元素。
②此时我们把这个复制的e单独提出来，进行了两个判断：
第一个if：if ((e = p.next) == null)
如果e也就是p.next == null,那么说明当前的这个P已经是链表最后一个元素了。这个时候采取尾插法添加一个新的元素:p.next = newNode(hash, key, value, null);,即直接将p的引用域指向这个新添加的元素。如果添加新元素之后发现链表的长度超过了TREEIFY_THRESHOLD - 1也就是超过了8，那么调用treeifyBin(tab, hash);把这个链表转换成红黑树接着玩。
第二个if:if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
如果发现key值重复了，也就是要插入的key已经存在，那么直接break，结束遍历(不用再费劲去插入了)。
③然后又将e赋给p，这个时候的p已经向后移动了一位。重复上面的过程，直到循环完整个链表，或者break出来。
整个不是红黑树的for循环(或者else)中就做了这三件事。总结：当要插入的链不是红黑树而是链表时：循环p.next，当p.next为null时则表示已经循环到该链的最后一个元素了，此时直接将要传入的元素赋给p.next即可（即尾插法）。其中循环中间会看该链插入后是否变为8了，如果为8则将链表转换为红黑树存储。
第四步：超过最大容量限制，扩容
if (++size > threshold) resize(); afterNodeInsertion(evict);注意：对于上面的判断是否转为红黑树中，所谓的阈值为8对此进行代码分析
for (int binCount = 0; ; ++binCount) {//循环计算该链表的长度 if ((e = p.next) == null) {//如果p.next为null（即循环到p链的最后一个元素了），则直接将传进来的接到最后一个的next去 p.next = newNode(hash, key, value, null); //链表长度大于8转换为红黑树（调用相应方法） if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; }看上面的代码，当链表只有1个元素时，此时进入该if条件，则将新增元素插入到尾部去，此时链表有2个元素。
即此时 binCount=0，而链表长度为2。依次类推当binCount=7时则满足将其转换为红黑树，而此时的链长却为9
不是所谓的阈值8。那么此时为什么为9呢？因为网上说的>=8转换为红黑树的说法是错的，真正的说法是大于8.（可以去看美团发的hashmap说的就是大于8）
具体的扩容操作，我们接下来具体再讲
HashMap扩容机制的实现-----------resize方法
首先上源码，我们在下面的源码中会加上详细的注释，希望读者们一起跟着走一遍:
上面图中重新设置扩容阈值是在保存旧数据之前的（这里是借用别人的图之后有时间自己再画一个）(构造函数等到要调用时再去初始化扩容，这类似一种“懒加载”的思想，即用到再去加载的编程思想)
扩容(resize)就是重新计算容量,向HashMap对象里不停的添加元素,内部的数组无法装载更多的元素时,就需要扩大数组的长度.
当然Java里的数组是无法自动扩容的,方法是使用一个新的数组代替已有的容量小的数组
/**
* 该函数有2种使用情况：1.初始化哈希表 2.当前数组容量过小，需扩容
*情况1是初始化采用的（初始化hashmap有无参、带参的初始化扩容（又分带两个和带一个））
*情况2是对数据达到扩容临界值产生的扩容情况
*所以说下来一共又四种情况：对应if-elseif-else-if 这四个条件筛选
*/
final Node[] resize() {
Node[] oldTab = table; //老数据
int oldCap = (oldTab == null) ? 0 : oldTab.length;//老数据长度（该长度是总长度）
int oldThr = threshold; //老数据的扩容临界值
int newCap, newThr = 0; //新数组的长度，扩容临界值（先赋值为0）
// 针对情况2：若扩容前的数组容量超过最大值，则不再扩充
if (oldCap > 0) {//有老数据则进行扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;//申请（整型的最大值），之后则不再扩容
return oldTab;
}
// 针对情况2：若无超过最大值，就扩充为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//if（）中将newCap设置为oldCap的2倍并小于MAXIMUM_CAPACITY，且大于默认值, 新的threshold增加为原来的2倍
newThr = oldThr << 1; //临界值也扩容为两倍
}
// 针对情况1：初始化哈希表（采用指定 or 默认值）
else if (oldThr > 0) // initial capacity was placed in threshold
// threshold>0, 将threshold设置为newCap,所以要用tableSizeFor方法保证threshold是2的幂次方（这里是用于带参的构造函数所用的扩容初始化）
newCap = oldThr;//将临界值赋给新数组长度。
else { // zero initial threshold signifies using defaults
// 默认初始化（这个是无参构造函数初始化hashmap中用到的）
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize上限（用于只传数组长度的构造函数初始化扩容）
if (newThr == 0) {
// newThr为0，newThr = newCap * 0.75，上面已经将旧的临界值赋给新的数组长度
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//上面经过四种情景已经将新的newThr、newCap设置好了，下面是用设置好的两个新值做操作
threshold = newThr;//最后将上面几种情况设置好的扩容临界值重新赋给扩容临界值
//下面是new一个新的数组（用几种情况选择设置好的新的数组长度），然后老数据重算hash计算后存进新数组中
@SuppressWarnings({"rawtypes","unchecked"})
// 新生成一个table数组
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// oldTab 复制到 newTab
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 链表只有一个节点，直接赋值
//为什么要重新Hash呢？因为长度扩大以后，Hash的规则也随之改变。
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// e为红黑树的情况
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order链表优化重hash的代码块
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}上面这段代码中，前面一部分我们做了详细的注释，从下面的for()循环开始，我们需要单独拉出来讲一下，因为这一段是重点的数组迁移，也是比较难以理解的：
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
首先命名了两组Node<K,V>对象，loHead = null, loTail = null;与hiHead = null, hiTail = null;，这两组对象是为了针对(e.hash & oldCap) == 0是否成立这两种情况，而作出不同的处理；结合后面的：
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
可以知道，如果(e.hash & oldCap) == 0，则 newTab[j] = loHead = e = oldTab[j]，即索引位置没变。反之 (e.hash & oldCap) != 0, newTab[j + oldCap] = hiHead = e = oldTab[j],也就是说，此时把原数组[j]位置上的桶移到了新数组[j+原数组长度]的位置上了。
这是个啥意思呢?我们借用美团点评技术团队Java 8系列之重新认识HashMap一文中的部分解释(这篇文章讲的确实很好，网上很多讲解1.8中HashMap的博客都是抄的这篇):
数组重排运算示意.png
我们之前一直说的一个移位运算就是—— a % (2^n) 等价于 a & (2^n - 1)，也即是位运算与取模运算的转化，且位运算比取模运算具有更高的效率，这也是为什么HashMap中数组长度要求为2^n的原因。我们复习一下，HanshMap中元素存入数组的下表运算为**index = hash & (n - 1) **，其中n为数组长度为2的整数次幂。
在上面的图中，n表示一个长度为16的数组，n-1就是15，换算成二进制位1111。这个时候有两种不同的哈希码来跟他进行与操作(对应位置都为1结果为1，否则为0)，这两种哈希码的低四位都是相同的，最大的不同是第五位，key1为0，key2为1；
这个时候我们进行扩容操作，n由16变为32，n-1=32,换算成二进制位11111，这个时候再和key1,key2进行与操作，我们发现，由于第5位的差异，得到了两种不同的结果：
结果.png
可以看到，得出的结果恰好符合上面我们将的两种情况。这也就是1.8中扩容算法做出的改进，至于为什么这么搞？借用刚那篇文章中的一句话——由于(hashCode中)新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。
这个时候有些同学就有问题了，刚刚说了半天hash & (n - 1)，源码中明明是if ((e.hash & oldCap) == 0) {，并没有减1啊~~我们可以看看如果不减1的话，16就是10000，和key1(第5位为0)相与结果为0，而和key2(第5位上面为1)就成了16了(！=0)，也符合上面两种情况。扩容之后同理。
（对于重新计算每个数据在数组中的存储位置和key的hash（）计算方法（即1.7的方法）之后再讨论）
注意：(为何为2的幂次方？)
1、1.7/1.8数据的key的存储位置都是通过hash&（length-1）位运算得到的(hash(key)方法也是该方法)（hash是hashcode（key）获得的，hash（）方法中就是调用了该方法）
2、为什么用hash&（length-1）（这也是为什么初始长度都是2的幂次方的答案）？首先一开始为了尽量的减少hash冲突和均匀的分布key，采用了hash%length进行key位置计算，而后来发现当数组长度为2的幂次方时，hash&（length-1）==hash%length（两者等价），而位运算的效率远远大于取模运算，所以1.7/1.8都将数组的长度设置为2的幂次方，达到位运算和取模运算等价的情况，这样就可以大大的提高效率
3、1.7/1.8中在扩容时重新计算key的hash值的算法不同，但其实质还是用hash&（length-1）位运算，只是1.8的算法比1.7的更加高效
4、如果当自定义初始化的值不为2的幂次方时，例15，此时hashmap会拿大于15的第一个2的幂次方的数值作为该数组的容量，即16.
5、要使hash&（length-1）的值在0到length之间，也需要保证长度是2的幂次方（因为获取key在数组的位置都是以hash&（length-1）为下标的）
put方法分析完看下get方法：
/**
* 函数原型
* 作用：根据键key，向HashMap获取对应的值
*/
map.get(key)；
/**
* 源码分析
*/
public V get(Object key) {
Node e;
// 1\. 计算需获取数据的hash值
// 2\. 通过getNode（）获取所查询的数据 ->>分析1
// 3\. 获取后，判断数据是否为空
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* 分析1：getNode(hash(key), key))
*/
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
// 1\. 计算存放在数组table中的位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 4\. 通过该函数，依次在数组、红黑树、链表中查找（通过equals（）判断）
// a. 先在数组中找，若存在，则直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// b. 若数组中没有，则到红黑树中寻找
if ((e = first.next) != null) {
// 在树中get
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
// c. 若红黑树中也没有，则通过遍历，到链表中寻找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}在JDK1.7及以前的版本中，HashMap里是没有红黑树的实现的，在JDK1.8中加入了红黑树是为了防止哈希表碰撞攻击，当链表链长度为8时，及时转成红黑树，提高map的效率（红黑树是O(logn)，而不是链表的O(n)）效率提高
至此put（hash方法（1.7链表的hash生成方法，1.8的链表部分则是用新的方法计算新hash值）、扩容机制resize）、get方法基本解析完，下面则是另一个1.7到1.8要解决的另一个热点问题：死循环问题（1.8将头插法改为尾插法解决了该问题）。分析该问题直接看1.7的扩容机制resize及其中的transfer方法
/**
* 源码分析：resize(2 * table.length)
* 作用：当容量不足时（容量 > 阈值），则扩容（扩到2倍）
*/
void resize(int newCapacity) {
// 1\. 保存旧数组（old table）
Entry[] oldTable = table;
// 2\. 保存旧容量（old capacity ），即数组长度
int oldCapacity = oldTable.length;
// 3\. 若旧容量已经是系统默认最大容量了，那么将阈值设置成整型的最大值，退出
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 4\. 根据新容量（2倍容量）新建1个数组，即新table （形参传进的newCapacity已经扩容了2倍）
Entry[] newTable = new Entry[newCapacity];
// 5\. （重点分析）将旧数组上的数据（键值对）转移到新table中，从而完成扩容 ->>分析1.1
//这里将旧数据转移到新数组上去的步骤用了头插法导致了死循环问题
transfer(newTable);
// 6\. 新数组table引用到HashMap的table属性上
table = newTable;
// 7\. 重新设置阈值
threshold = (int)(newCapacity * loadFactor);
}
/**
* 分析1.1：transfer(newTable);
* 作用：将旧数组上的数据（键值对）转移到新table中，从而完成扩容
* 过程：按旧链表的正序遍历链表、在新链表的头部依次插入
*/
void transfer(Entry[] newTable) {
// 1\. src引用了旧数组（table是旧数组）
Entry[] src = table;
// 2\. 获取新数组的大小 = 获取新容量大小
int newCapacity = newTable.length;
// 3\. 通过遍历 旧数组，将旧数组上的数据（键值对）转移到新数组中
for (int j = 0; j < src.length; j++) {
// 3.1 取得旧数组的每个元素
Entry e = src[j];
if (e != null) {
// 3.2 释放旧数组的对象引用（for循环后，旧数组不再引用任何对象）
src[j] = null;
do {
// 3.3 遍历 以该数组元素为首 的链表
// 注：转移链表时，因是单链表，故要保存下1个结点，否则转移后链表会断开
Entry next = e.next;
// 3.3 重新计算每个元素的存储位置（这里的计算存储位置和1.8的不同）
int i = indexFor(e.hash, newCapacity);
// 3.4 将元素放在数组上：采用单链表的头插入方式 = 在链表头上存放数据 = 将数组位置的原有数据放在后1个指针、将需放入的数据放到数组位置中
// 即 扩容后，可能出现逆序：按旧链表的正序遍历链表、在新链表的头部依次插入
e.next = newTable[i];
newTable[i] = e;
// 访问下1个Entry链上的元素，如此不断循环，直到遍历完该链表上的所有节点
e = next;
} while (e != null);
// 如此不断循环，直到遍历完数组上的所有数据元素
}
}
}上面可看出：在扩容resize（）过程中，在将旧数组上的数据 转移到 新数组上时，转移数据操作 = 按旧链表的正序遍历链表、在新链表的头部依次插入，即在转移数据、扩容后，容易出现链表逆序的情况
设重新计算存储位置后不变，即扩容前 = 1->2->3，扩容后 = 3->2->1
因为使用头插法：先按正序遍历(即是按1、2、3依次取出的)（如果3各还是在同一链上）
：取出1然后按头插法将1插入新数组链表的第一个。
：取出2，头插法插在1前面：2->1。
：取出3，头插法插在2之前：3->2->1。
此时则出现了链表逆序的情况
在去看死循环之前先声明：
1、每次扩容要转移数据时都是取一个数组元素（即一条链）然后删除旧数组的引用。再循环这条链表的各个数值转移到新数组
2、1.7是先扩容完，再插入之前要插入的数据（就是该数据导致要扩容的），1.8是先插入再扩容的。（所以分析1.7的链不用加上即将插入的那个数据）。
3、线程1先扩容新数组长度，但此时还没有将旧数据转移到新数组上（此时还没有获取到旧数据链表）；线程2是将扩容和转移旧数据都完成了（此时旧数据引用被赋予null相当于没有了，后面线程1回去获取线程2重新逆排序后的链表）。
注意：形成多线程死循环的三个必要条件：
1.新建立的链表跟原链表顺序相反
2.线程A将构造出来的逆向链表刷新到主内存
3.线程B重新从主内存获取到新的链表引用jdk8已经修复这个问题，新构造出来的链表顺序与原链表相同
此时若并发执行 put 操作，一旦出现扩容情况，则 容易出现 环形链表，从而在获取数据、遍历链表时 形成死循环（Infinite Loop），即死锁：总体流程如下
流程图演示
1、
2、线程1重新运行
此时发现死循环。1.8后将头插法改为尾插法解决了死循环的问题
解决完死循环，但hashmap在多线程仍然存在Fast-fail的问题:
1、什么是Fast-fail机制
迭代HashMap采用快速迭代机制，而Hashtable不是快速失败（Fail-Fast）机制：对于线程不安全的集合对象的迭代器，如果在使用迭代器的过程中有其他线程修改了集合对象结构或者元素数量，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。
迭代 HashMap 采用快速失败机制，而 HashTable 不是，因为 HashTable 是线程安全的。
java的快速失败机制，即fail-fast，它是Java集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。记住是有可能，而不是一定。
例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。
2、怎么解决hashmap的Fast-fail机制
单线程条件下，为避免出现ConcurrentModificationException，需要保证只通过HashMap本身或者只通过Iterator去修改数据，不能在Iterator使用结束之前使用HashMap本身的方法修改数据。因为通过Iterator删除数据时，HashMap的modCount和Iterator的expectedModCount都会自增，不影响二者的相等性。如果是增加数据，只能通过HashMap本身的方法完成，此时如果要继续遍历数据，需要重新调用iterator()方法从而重新构造出一个新的Iterator，使得新Iterator的expectedModCount与更新后的HashMap的modCount相等。
多线程条件下，可使用Collections.synchronizedMap方法构造出一个同步Map，或者直接使用线程安全的ConcurrentHashMap。
那么关于ConcurrentHashMap是什么？怎么·解决hashmap的快速失败机制的？
看我下一篇文章关于ConcurrentHashMap的分析：https://mp.csdn.net/console/editor/html/105062515
hashmap可以用String、Integer作为起可以吗？为什么？
三、总结1.7到1.8发生了哪些改变，这些改进解决了什么问题？
总结下hashmap1.7到1.8改变了什么？解决了什么问题？
1、4个构造函数中3个主要的构造函数采用调用才调用扩容方法resize进行初始化扩容（懒加载的思想）
2、1.7：先扩容数组再插入数据； 1.8：先插入数据再扩容数组
3、1.7:采用头插法，1.8使用尾插法插入数据，解决了死循环的问题
4、1.7是数组+链表的存储结构，1.8是数组+链表/红黑树的存储结构（大于8转换为红黑树，小于6转换为链表）
5、扩容方法中重新计算数据存放位置的方法不同（这里后面会写一篇两个方法的解析文章）
上面则为1.7到1.8hashmap主要的改变
学完上面的知识对hashmap此时提出一些问题思考：
为什么大于等于8转红黑树、小于等于6转链表？那7是用来干嘛的？
头插法和尾插法有什么不同？解决了什么问题？
初始值数组的容量必须为2的n次？
------详细看https://blog.csdn.net/qq_44933374/article/details/98469424
https://blog.csdn.net/apeopl/article/details/88935422
https://zhuanlan.zhihu.com/p/21673805 也可看上文的解答
为什么负载因子是0.75？
每个map元素的hash值是怎么运算的？
扩容临界值方法tableSizeFor(initialCapacity)怎么计算的？
key的hash值是怎么计算的？
为什么1.8要用红黑树、不用其他树？
扩容方法中重新计算数据存放位置的方法不同？有什么用？
为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键？
HashMap 中的 key若 Object类型， 则需实现哪些方法？
四、1.8存在的问题及怎么去解决
话不多说，存在最大的问题就是安全问题。
可使用Collections.synchronizedMap方法构造出一个同步Map（但其效率低）
或者直接使用线程安全的ConcurrentHashMap。具体看下篇文章https://mp.csdn.net/console/editor/html/105062515
此时有一疑问hashtable呢？他不是线程安全吗？他和hashmap有什么区别？具体看下一篇文章https://blog.csdn.net/qq_35599414/article/details/105076735
最后该文主要参考：https://www.jianshu.com/p/1e9cf0ac07f4