1、概述

HashMap是Map中最为常用的一种，在面试和工作中也经常会被问到相关的问题。由于HashMap数据结构较为复杂，回答相关问题的时候往往不尽人意，尤其是在JDK1.8之后，又引入了红黑树结构，其数据结构变的更加复杂，本文就JDK1.8源码为例，对HashMap进行分析；

只要耐心看完本篇HashMap源码解析，我相信你一定可以告诉别人精通HashMap源码。当然了，如果有什么问题也欢迎提出来，一起进步。下面直接上硬核

2、源码解析

1.HashMap底层存储结构

在JDK1.7的时候只有数组加链表的，但是在JDK1.8之后使用了数组加链表加红黑树。也是为了提升性能。看下面的图可能比较直观：

每一个节点就是一个Node，Node有四个属性；

Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash; //hash值this.key = key;this.value = value;this.next = next; //下一个指针}

问题一: 为什么直接就用数组呢？

1. 数组我们都知道，在内存中是一块连续的空间，所以如果数组很大的情况下，会很耗费内存。
2. HashMap是通过hash取值落到数组上的，那么就会有一个问题，没错HASH碰撞，如果两个元素的HASH值一样，那么他们落在同一个槽位上怎么办，所以就有了链表，如果链表足够长，就会变为红黑树，下面会详细剖析这些。

问题二：什么是红黑树呢？

红黑树是一个自平衡的二叉查找树，也就是说红黑树的查找效率是非常的高，查找效率会从链表的o(n)降低为o(logn)。如果之前没有了解过红黑树的话，也没关系，你就记住红黑树的查找效率很高就OK了。

问题三：为什么不一下子把整个链表变为红黑树呢？

这个问题的意思是这样的，就是说我们为什么非要等到链表的长度大于等于8的时候，才转变成红黑树？在这里可以从两方面来解释

（1）构造红黑树要比构造链表复杂，在链表的节点不多的时候，从整体的性能看来， 数组+链表+红黑树的结构可能不一定比数组+链表的结构性能高。就好比杀鸡焉用牛刀的意思。

（2）HashMap频繁的扩容，会造成底部红黑树不断的进行拆分和重组，这是非常耗时的。因此，也就是链表长度比较长的时候转变成红黑树才会显著提高效率。

OK，到这里相信我们对hashMap的底层数据结构有了一个认识。下面我们看一下一些重要的成员变量

2.HashMap的重要成员变量

1. DEFAULT_INITIAL_CAPACITY = 1 << 4;  Hash表默认初始容量 16
位运算：0000 0001  左移四位后 0001 0000  变成了2的四次方=16
2. MAXIMUM_CAPACITY = 1 << 30;  最大Hash表容量，Int的最大值
3. DEFAULT_LOAD_FACTOR = 0.75f; 缺省负载因子(装逼可以说泊松分推导的)
4. TREEIFY_THRESHOLD = 8;链表转红黑树阈值
5. UNTREEIFY_THRESHOLD = 6;树降级称为链表的阈值
6. MIN_TREEIFY_CAPACITY = 64;树化的另一个参数，当哈希表中的所有元素个数超过64时，才会允许树化
7. transient int size;当前哈希表中元素个数
8. transient int modCount;当前哈希表结构修改次数(替换不算)
9. int threshold;扩容阈值，当你的哈希表中的元素超过阈值时，触发扩容(capacity * loadFactor).
10.final float loadFactor;0.75 默认就是上面的 DEFAULT_LOAD_FACTOR（当负载因子较大时，去给table数组扩容的可能性就会少，所以相对占用内存较少（空间上较少），但是每条entry链上的元素会相对较多，查询的时间也会增长（时间上较多）。反之就是，负载因子较少的时候，给table数组扩容的可能性就高，那么内存空间占用就多，但是entry链上的元素就会相对较少，查出的时间也会减少。所以才有了负载因子是时间和空间上的一种折中的说法。所以设置负载因子的时候要考虑自己追求的是时间还是空间上的少。（一般情况下不需要设置，系统给的默认值已经比较适合了）

3.构造方法解析

HashMap 的构造方法不多，只有四个。HashMap 构造方法做的事情比较简单，一般都是初始化一些重要变量，比如 loadFactor(负载因子0.75) 和 threshold（扩容阈值）。而底层的数据结构则是延迟到插入键值对时再进行初始化。HashMap 相关构造方法如下：

/ 构造方法 1 */
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}/ 构造方法 2 */
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}/ 构造方法 3 */
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;this.threshold = tableSizeFor(initialCapacity);
}/ 构造方法 4 */
public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);
}

上面4个构造方法中，大家平时用的最多的应该是第一个了。第一个构造方法很简单，仅将 loadFactor 变量设为默认值。构造方法2调用了构造方法3，而构造方法3仍然只是设置了一些变量。构造方法4则是将另一个 Map 中的映射拷贝一份到自己的存储结构中来，这个方法不是很常用。

上面就是对构造方法简单的介绍，构造方法本身并没什么太多东西，所以就不说了。接下来详细说说构造方法 3中给threshold(扩容阈值)是怎么赋值的。方法tableSizeFor

/* 作用：返回一个大于等于当前值cap的一个数字，并且这个数字一定是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;}

上面的代码长的有点不太好看，反正我第一次看的时候不明白它想干啥。不过后来在纸上画画，知道了它的用途。总结起来就一句话：找到大于或等于 cap 的最小2的幂。至于为啥要这样，后面再解释。我们先来看看 tableSizeFor 方法的解释：
在这里我举个列子，仔细看应该可以，如果cap=10;
那么n=10-1=9; 如果对无符号右移运算符不了解的，可以看一下这篇文章了解一下
下面我也把位运算的几个基本内容贴一下：

与：两个是1才是1
或：只要有一个是1就是1
异或：只有11跟或不同，其他一样。（更好的记忆方式：相同是0）
取反：0变1，1变0

下面我们仔细看看上面怎么算的
9的二进制为0b1001

n |= n >>> 1; 无符号右移一位1001前面加1个0后面舍去最后1位得0b0100
0b1001 | 0b0100 => 0b1101
n |= n >>> 2;无符号右二位1101前面加2个0后面舍去最后2位得0b0100
0b1101 | 0b0011 => 0b1111
n |= n >>> 4;
0b1111 | 0b0000 => 0b1111
n |= n >>> 8;
0b1111 | 0b0000 => 0b1111
n |= n >>> 16;
0b1111 | 0b0000 => 0b1111
你会发现到最后其实都是一样的了。
那么n=0b1111 转换为10进制为：
(1*2的0次方=1)+(1*2的1次方=2)+(1*2的2次方=4)+(1*2的3次方=8)=1+2+4+8=15
(n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
n=15不小于0，并且不大于容量的最大值，则n=n+1=16。
但是一般不用这个构造方法

另外，需要注意一下的是，第一步 int n = cap - 1; 这个操作，执行这个操作的主要原因是为了防止在cap已经是2的n次幂的情况下，经过运算后得到的结果是cap的二倍的结果，例如如果n为16，经过一系列运算之后，得到的结果是0001 1111，此时最后一步n+1 执行之后，就会返回32，有兴趣的可以自己进行尝试；

4.Put方法解析

先看图，看懂图再看源码

/ 作用：让key的hash值的高16位也参与路由运算* 异或：相同则返回0，不同返回1
*/public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}

先说第一步怎么计算Hash值的
这段代码叫做扰动函数，也是hashMap中的hash运算，主要分为下面几步：

• key.hashCode()，获取key的hashCode值，如果不进行重写的话返回的是根据内存地址得到的一个int值
• key.hashCode() 获取到的hashcode无符号右移16位并和元hashCode进行^ ，这样做的目的是为了让高位与低进行混合，让两者都参与运算，以便让hash值分布更加均匀

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
如果key不为空，并且取到k的hash值为：
h1 = 0b 0010 0101 1010 1100 0011 1111 0010 1110  将它无符号右移16位后做异或运算
^
h2 = 0b 0000 0000 0000 0000 0010 0101 1010 1100=> 0b 0010 0101 1010 1100 0001 1010 1000 0010主要目的就是为了让hash值更加分散不重复

下面看主要得put源码，直接贴代码了，我把注释也写在代码了，耐心读下去。在最后面我会把源码注释文件地址贴出来。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {//tab：引用当前hashMap的散列表//p：表示当前散列表的元素//n：表示散列表数组的长度//i：表示路由寻址 结果Node<K,V>[] tab; Node<K,V> p; int n, i;//延迟初始化逻辑，第一次调用putVal时会初始化hashMap对象中的最耗费内存的散列表if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//最简单的一种情况：寻址找到的桶位 刚好是 null，这个时候，直接将当前k-v=>node 扔进去就可以了if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {//e：不为null的话，找到了一个与当前要插入的key-value一致的key的元素//k：表示临时的一个keyNode<K,V> e; K k;//表示桶位中的该元素，与你当前插入的元素的key完全一致，表示后续需要进行替换操作if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)//红黑树，下期讲。e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//链表的情况，而且链表的头元素与我们要插入的key不一致。for (int binCount = 0; ; ++binCount) {//条件成立的话，说明迭代到最后一个元素了，也没找到一个与你要插入的key一致的node//说明需要加入到当前链表的末尾if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//条件成立的话，说明当前链表的长度，达到树化标准了，需要进行树化if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//树化操作 在里面还判断了，需要table的数组长度大于64才会树化treeifyBin(tab, hash);break;}//条件成立的话，说明找到了相同key的node元素，需要进行替换操作if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//e不等于null，条件成立说明，找到了一个与你插入元素key完全一致的数据，需要进行替换if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}//modCount：表示散列表结构被修改的次数，替换Node元素的value不计数++modCount;//插入新元素，size自增，如果自增后的值大于扩容阈值，则触发扩容。if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

从代码看，put方法分为三种情况：

• table尚未初始化，对数据进行初始化
• table已经初始化，且通过hash算法找到下标所在的位置数据为空,直接将数据存放到指定位置
• table已经初始化，且通过hash算法找到下标所在的位置数据不为空，发生hash冲突（碰撞），发生碰撞后，会执行以下操作：

判断插入的key如果等于当前位置的key的话，将 e 指向该键值对
如果此时桶中数据类型为 treeNode，使用红黑树进行插入
如果是链表，则进行循环判断， 如果链表中包含该节点，跳出循环，如果链表中不包含该节点，则把该节点插入到链表末尾，同时，如果链表长度超过树化阈值（TREEIFY_THRESHOLD）且table容量超过最小树化容量（MIN_TREEIFY_CAPACITY），则进行链表转红黑树（由于table容量越小，越容易发生hash冲突，因此在table容量<MIN_TREEIFY_CAPACITY 的时候，如果链表长度>TREEIFY_THRESHOLD,会优先选择扩容，否则会进行链表转红黑树操作）

取模运算 (n - 1) & hash

在hashMap的代码中，在很多地方都会看到类似的代码：

first = tab[(n - 1) & hash]) 

hash算法中，为了使元素分布的更加均匀，很多都会使用取模运算，在hashMap中并没有使用hash%n这样进行取模运算，而是使用(n - 1) & hash进行代替，原因是在计算机中，&的效率要远高于%；需要注意的是，只有容量为2的n次幂的时候，(n - 1) & hash 才能等效hash%n，这也是hashMap 初始化初始容量时，无论传入任何值，都会通过tableSizeFor(int cap) 方法转化成2的n次幂的原因，这种巧妙的设计真的很令人惊叹；
至于为什么只有2的n次幂才能这样进行取模运算，这里就不再详细叙述了

5.Get方法解析

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;}
final Node<K,V> getNode(int hash, Object key) {//tab：引用当前hashMap的散列表//first：桶位中的头元素//e：临时node元素//n：table数组长度Node<K,V>[] tab; Node<K,V> first, e; int n; K k;if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//第一种情况：定位出来的桶位元素 即为咱们要get的数据if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;//说明当前桶位不止一个元素，可能 是链表 也可能是 红黑树if ((e = first.next) != null) {//第二种情况：桶位升级成了 红黑树if (first instanceof TreeNode)//return ((TreeNode<K,V>)first).getTreeNode(hash, key);//第三种情况：桶位形成链表do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;}

get方法相对于put来说，逻辑实在是简单太多了

1. 根据hash值查找到指定位置的数据
2. 校验指定位置第一个节点的数据是key是否为传入的key，如果是直接返回第一个节点，否则继续查找第二个节点
3. 如果数据是TreeNode（红黑树结构），直接通过红黑树查找节点数据并返回
4. 如果是链表结构，循环查找所有节点，返回数据
5. 如果没有找到符合要求的节点，返回null

6.resize 扩容方法解析

resize方法逻辑比较复杂，需要静下心来一步步的分析，但是总的下来，分为以下几步：

• 首先先判断当前table是否进行过初始化，如果没有进行过初始化，此处就解决了调用无参构造方法时候，threshold和initialCapacity 未初始化的问题，如果已经初始化过了，则进行扩容，容量为原来的二倍
• 扩容后创建新的table，并对所有的数据进行遍历

如果新计算的位置数据为空，则直接插入
如果新计算的位置为链表，则通过hash算法重新计算下标，对链表进行分组
如果是红黑树，则需要进行拆分操作

/*
*为什么需要扩容？为了解决哈希冲突导致的链化影响查询效率的问题，扩容会缓解该问题。
*/
final Node<K,V>[] resize() {//oldTab：引用扩容前的哈希表Node<K,V>[] oldTab = table;//oldCap：表示扩容之前table数组的长度int oldCap = (oldTab == null) ? 0 : oldTab.length;//oldThr：表示扩容之前的扩容阈值，触发本次扩容的阈值int oldThr = threshold;//newCap：扩容之后table数组的大小//newThr：扩容之后，下次再次触发扩容的条件int newCap, newThr = 0;//条件如果成立说明 hashMap中的散列表已经初始化过了，这是一次正常扩容if (oldCap > 0) {//扩容之前的table数组大小已经达到 最大阈值后，则不扩容，且设置扩容条件为 int 最大值。if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//oldCap左移一位实现数值翻倍，并且赋值给newCap， newCap 小于数组最大值限制 且 扩容之前的阈值 >= 16//这种情况下，则 下一次扩容的阈值 等于当前阈值翻倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}//oldCap == 0,说明hashMap中的散列表是null//1.new HashMap(initCap, loadFactor);//2.new HashMap(initCap);//3.new HashMap(map); 并且这个map有数据else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;//oldCap == 0，oldThr == 0//new HashMap();else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;//16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12}//newThr为零时，通过newCap和loadFactor计算出一个newThrif (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;//说明，hashMap本次扩容之前，table不为nullif (oldTab != null) {for (int j = 0; j < oldCap; ++j) {//当前node节点Node<K,V> e;//说明当前桶位中有数据，但是数据具体是 单个数据，还是链表 还是 红黑树 并不知道if ((e = oldTab[j]) != null) {//方便JVM GC时回收内存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;//高位链表：存放在扩容之后的数组的下表位置为 当前数组下标位置 + 扩容之前数组的长度  index=15=>index=31Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;//hash-> .... 1 1111//hash-> .... 0 1111// 0b 10000if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;}

7.remove 方法解析

public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;}
final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {//tab：引用当前hashMap中的散列表//p：当前node元素//n：表示散列表数组长度//index：表示寻址结果Node<K,V>[] tab; Node<K,V> p; int n, index;if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {//说明路由的桶位是有数据的，需要进行查找操作，并且删除//node：查找到的结果//e：当前Node的下一个元素Node<K,V> node = null, e; K k; V v;//第一种情况：当前桶位中的元素 即为 你要删除的元素if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;else if ((e = p.next) != null) {//说明，当前桶位 要么是 链表 要么 是红黑树if (p instanceof TreeNode)//判断当前桶位是否升级为 红黑树了//第二种情况//红黑树查找操作，下一期再说node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {//第三种情况//链表的情况do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}//判断node不为空的话，说明按照key查找到需要删除的数据了if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {//第一种情况：node是树节点，说明需要进行树节点移除操作if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);//第二种情况：桶位元素即为查找结果，则将该元素的下一个元素放至桶位中else if (node == p)tab[index] = node.next;else//第三种情况：将当前元素p的下一个元素 设置成 要删除元素的 下一个元素。p.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}}return null;}

从源码可以看出来，通过key找到需要移除的元素操作过程和get方法几乎一致，最后在查找到key对应的节点之后，根据节点的位置和类型，进行相应的移除操作就完成了，过程非常简单

3、Jdk7-扩容死锁分析

在1.7的时候采用的是头插法，如果在多线程的情况下，发生了扩容，就会出现死锁问题。
单线程是没问题的
先来看看1.7的扩容方法代码;

void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {//记录oldhash表中e.nextEntry<K,V> next = e.next;//第一行if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}//rehash计算出数组的位置(hash表中桶的位置)int i = indexFor(e.hash, newCapacity);//第二行e.next = newTable[i];//第三行newTable[i] = e;//第四行e = next;//第五行}}
}

去掉了一些冗余的代码， 层次结构更加清晰了。

• 第一行：记录oldhash表中e.next
• 第二行：rehash计算出数组的位置(hash表中桶的位置)
• 第三行：e要插入链表的头部， 所以要先将e.next指向new hash表中的第一个元素
• 第四行：将e放入到new hash表的头部
• 第五行： 转移e到下一个节点， 继续循环下去

下面就是多线程同时put的情况了， 然后同时进入transfer方法中：假设这里有两个线程同时执行了put()操作，并进入了transfer()环节

while(null != e) {Entry<K,V> next = e.next;//第一行，线程1执行到此被调度挂起int i = indexFor(e.hash, newCapacity);//第二行e.next = newTable[i];//第三行newTable[i] = e;//第四行e = next;//第五行
}

那么此时状态为：

从上面的图我们可以看到，因为线程1的 e 指向了 key(3)，而 next 指向了 key(7)，在线程2 rehash 后，就指向了线程2 rehash 后的链表。

然后线程1被唤醒了：

1. 执行e.next = newTable[i]，于是 key(3)的 next 指向了线程1的新 Hash 表，因为新 Hash 表为空，所以e.next = null，
2. 执行newTable[i] = e，所以线程1的新 Hash 表第一个元素指向了线程2新 Hash 表的 key(3)。好了，e 处理完毕。
3. 执行e = next，将 e 指向 next，所以新的 e 是 key(7)
   然后该执行 key(3)的 next 节点 key(7)了:
4. 现在的 e 节点是 key(7)，首先执行Entry<K,V> next = e.next,那么 next 就是 key(3)了
5. 执行e.next = newTable[i]，于是key(7) 的 next 就成了 key(3)
6. 执行newTable[i] = e，那么线程1的新 Hash 表第一个元素变成了 key(7)
7. 执行e = next，将 e 指向 next，所以新的 e 是 key(3)

此时状态为：
然后又该执行 key(7)的 next 节点 key(3)了：
1.现在的 e 节点是 key(3)，首先执行Entry<K,V> next = e.next,那么 next 就是 null
2.执行e.next = newTable[i]，于是key(3) 的 next 就成了 key(7)
3.执行newTable[i] = e，那么线程1的新 Hash 表第一个元素变成了 key(3)
4.执行e = next，将 e 指向 next，所以新的 e 是 key(7)
这时候的状态如图所示：

很明显，环形链表出现了。

Java8 HashMap扩容跳过了Jdk7扩容的坑，对源码进行了优化，采用高低位拆分转移方式，避免了链表环的产生。

4、最后总结

到这里，hashMap的源码基本就解析完成了，其余的方法和源码逻辑相对非常简单，大部分还是使用上述代码来实现的，例如containsKey（jey），就是使用get方法中的getNode（）来判断的，由于篇幅原因就不一一介绍。
另外，中间有很部分不影响逻辑理解的代码被一笔带过，比如 红黑树的转化，查找，删除等操作，有兴趣的可以自己进行学习，不过还有一些其他的特性需要提醒一下:

• HashMap 底层数据结构在JDK1.7之前是由数组+链表组成的，1.8之后又加入了红黑树；链表长度小于8的时候，发生Hash冲突后会增加链表的长度，当链表长度大于8的时候，会先判读数组的容量，如果容量小于64会先扩容（原因是数组容量越小，越容易发生碰撞，因此当容量过小的时候，首先要考虑的是扩容），如果容量大于64，则会将链表转化成红黑树以提升效率
• hashMap 的容量是2的n次幂，无论在初始化的时候传入的初始容量是多少，最终都会转化成2的n次幂，这样做的原因是为了在取模运算的时候可以使用&运算符，而不是%取余，可以极大的提上效率，同时也降低hash冲突
• HashMap是非线程安全的，在多线程的操作下会存在异常情况（如形成闭环（1.7），1.8已修复闭环问题，但仍不安全），可以使用HashTable或者ConcurrentHashMap进行代替

篇幅比较长，希望你可以耐心看下去，将军赶路，不追野兔。
如果有理解不对的地方还请指正。

带注释源码地址： com.example.sync.HashMap.HashMap