前言
HashMap 源码和底层原理在现在面试中是必问的。因此，我们非常有必要搞清楚它的底层实现和思想，才能在面试中对答如流，跟面试官大战三百回合。文I * [ ; I # & G章较长，介绍t S g * Q D t ~了很多原理性的问题，希望对你有所帮助~
目录
本篇文章主要包括以D r f ) D W下内容：
- H^ Q X a ?ashMap 的存储结构
- 常用变量说明，如加载因子等
- HashMap 的四个构造函数
- tableSizeFor()方法及作用
- put()方法详解
- hash()方4 % l法，以及避免9 s D哈希碰撞的原理
- resize()扩容机制及原理
- ge( E M B T = c rt()方法
- 为什么HashMap链表会形成死循环，JDK1.8做了哪些优化
正文
说明：i P W d 5 x @ a本篇主要以JDK1.8的源码来分析，顺带讲下和JDK1.7的一些区别。
HashMap存储结构
这里需要区分一下，JDK1.7和 JDK1.8之后的 HashMap 存储结构。在JDK1.7及之前，是用数组加链表的方式存储的。
但是，众所周知，当链表的长度特别长的时候，查询效率将直线下降，查询S Z : E 3 . 9 . E的时间复杂度为 O(n)q Q & ! l = u。因此，JDK1.8 把M l O c U ~它设计为达到一个特+ W % k , ] B & V定的阈值之后，就将链表转化为红黑树。
这里简单说下红黑树的特点：
- 每个节点只有两种颜色：红色或者黑色
- 根节点必须是黑色
- 每个叶子节点（NIL）都是黑色的空节点
- 从根节点到叶子节点，不能出现两个连续的红色节点
- 从任一节点出发，到它下边的子节点的路径包含的黑色节点数目都相w U 0 + # d ]同
由* C C - I于红黑树，是一个自平衡的二叉搜索树，因! q ^ v ? = r 0此可以使查询的时间复杂度降为O(logn)。（红黑树不是本文重点Q M O [ z K n w，不了解的童鞋可自行查阅相关资料哈）
HashMap 结构示意图：
常用的变量
在 HashMap源码中，比较重要的常用变量，主要有以下这些。还有两个内部类来表示普通链表的节点和红黑树节点。
//默认的初始化容量为16，必须是2的n次幂
static final int DEFAULT_INITIN @ pAL_CAPAa ~ p g C b HCITY = 1 <<t 0 A 4; // aka 16
//最大容量为 2^30
static final int MAXIMUw ) cM_CAPACITY = 1 << 30;
//默认的加载因子0.Y K E 9 } ( ; +75，乘以数组容量得到的值，用来表示元素个数达到多少时，需要扩容。
//为什么设置 0.75 这个值呢，简单来说就是时间和空间的权衡。
//若小于0.75如0.5，则数组长度达到一半大小就需要扩容，空间使用率大大降低，
//若大于0.75如0.8，则会增大hash冲突的概率，影响查询效率。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//刚才提到了当链表长度过长时，会有一个阈值，超过这个阈值8就会转化为红黑树
static final int TREEIFY_THRESHOLV Z M V 5 0 _ mD = 8;
//当红黑树上的元素个数，减少到6个时，就退化为链表1 U w :
static final int UNTREEIFY_THRESHOLO I cD = 6;
//链表转化为红黑树，除了有阈值的限制，还有另外一个限制，需要数组容量至少达到64，才会树化。
//这是为了避免，数组扩容和树化阈值之间的冲突。
static final int MIN_TREEIFY_CAPACITY = 64;
//存放所有Node节点的数组
transient Node<K,V>[] table;
//存放所有的键值对
t3 b = N k # Qransient Se@ I & @ 6 r 9 jt<Map.Entryt t _ 0 ` = V<K,V>> eX G m ( LntrySet;
//map中的实际键值对个数，即数组中元素个数
transient int size;
//每次结构改变时，都会自增，fail-fast机制，这是一种错误检测机制。
//当迭代集合的时候，如果结构发生改变，则会发生 fail-fast，抛出异常。
transientA C 2 + m @ g int modCount;
//数组扩容! 3 Z i阈值
int threshold;
//加载因子
fx Q S O E z inal float loadFactor;
//普通单向链表节点类
static class Node<K,V> implements Map.Entry<K,V> {
//key的hash值，put和get的时候都需要用a W } 9 c k j 1 T到它来确定元素在数组中的位置
fis q N o = ; z c Pnal int hash;
final K key;
V value;
//指向单h 0 l r B 3链表的下一个节点
Node<K,V>{ K c 4 P T 4 y w next;
Node(f b 1 & Y E pint hash, K key, V value, Node<K,V>m u 9 /; next) {I C f / L N
this.hash = hash;
this.key =w g e V o m 3 key;
this.value = value;
thio r )s.next = next;
}
}
//转化为红黑树的节点类
static final class TreeNode<K,V&0 g Ugt; extendI v ) |s LinkedHashMap.Entry<K,V> {
//当前节点的父节点
TreeNode<K,V> parent;
//左孩子节点# d s P c - v y
TreeNode<K,V> left;
//右5 F o F , F . J孩子节点
TreeNodeb C E 5 [ i 2<K,V> right;
//指向前一个节点
TreeNode<K,V> prev; // needed to unlink next upon deletion
//当前节点是红色或者黑色的标识 &
bo` c ^ x ~ {olean! p ~ _ f L C red;e F s
TreeNode(int hashU V C 5 C q N U x, K key, V val, Node<K,V> next) {
super(hash, keyH d ~ ), val, next);
}
} HashMap 构造函数
HaV ) ) y E W qshMap有四个构造函数可供我们使用，一起来看下：
//默认无参构造，指定一个默认的加载因子
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACT6 ) W y - s 1 LOR;
}
//可指定容量的有参构造，但是需要注意当前我们指定的容量并不一定就是实际的容量，下面会说
public HashMap(int initialCapacity) {
//同样使用默认加载因子
this(iw u u `nitialCapacity, DEFAULT_LOAD_FACTOR);
}
//可指定容量和加载因子，但是笔者, = 1 B S B T J不建议自己手动指定非0.75的加载因子
public Hasr L ghMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
t, t L , U y & V 1hrow nC w ~ C Oew IllegalArgumentException(\"Illeg( N ^ $ q ` Aal initial capacity: \" +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFacto/ . E S b w Vr <= 0 || Fll m +oat.isNaN(loadFactor))
throw new Illega| U a } O V r W slArgumentException(\"IllegO b { D i gal load factor: \" +
loadFactor);
this.loadFactor = loadFactor;
//这里就是把我们指定的容量改为一个大于它的的最小的2次幂值，如传过来的容量是14，则返回16
//注意这里，按理说返回的值应该赋值给 capaci| ] Q r $ty，即保证数组容量总是2的n次幂，为什么这里赋值给了 threshold 呢？
//先卖个关子，等到 resize 的时候再说
this.threshold = tableSizeFor(initial5 C / !Capacity);
}
//可传入一个已有的map
public HashMap(Map&l@ j ` T g ! st;? extends K, ? exJ * _ z R n V Htends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
//把传入的map里] R m = Z 8 K边的元素都加载到当前map
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft &l/ l K @ B Gt; (float)MAX) ] ) R 1 w 5 ]IMUM_CAPACITY) ?& + & R e V
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)e P u v ] ` n
threshold = tableSizeFor(t);
}
else if (s >H 3 X c l t O threshold)
resize();
for (Map.Entry<? extends K, ? extends V>` ? . e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
//put方法的具体实现，后边讲
putVal(hash(key), key, val^ O ? p N D l ( nue, false, evict);
}
}
}tableSizeG d hFor()
上边的第三个构造函数中，调用C A @了 tableSizeFor 方法，这个方法是怎么实现的呢？
static final int tableSizeFor(int cap) {
int n = cs = Eap - 1;
n |= n >>> 1C C 2 P E h : v;
n |= n >l G D i>> 2;
n |A e Y W E I= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
red k _ } v qturn (n &l` } = B = s E ?t; 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}我们以传入参数为14 来举例，计算这个过程。
首先，14传进去之后先减1，n此时为13。然后是一系列的无符号右移运算。
//1] K = Y $ w 2 3的二进制
0000 0000 0000 0000 0000 0000 0000 1101
//无右移1位，高位补0
0000 0000 0000 0000 0000 0000 0000 0110
//然后把它和原来的13做或运算得到，此时M m = Q的n值
0000 0000 0000 0000 0000 0000 0000 1111
//再以上边的值，右移2位
0000 0000 0000 0000 0000 0000 0000 0011
//然后和第一次或运算之后的 n 值再做或运算，此时得到的n值
0000 0000 0000 0000 0000 0000 0000 1111
...
//我们会发现，再执行右移 4,8,16位，同样n的值不变
//当n小于0时，返回1，否则判断是否大于最大容量，是的话返回最大容量，否则返回 n+1
return (n < 0) ? 1n 9 j + ~ J Z B ? :r | L ~ (n >= MAXIMUM_CAPACITY) ? MAXIY c 7 jMUM_CAPACITYj x - : $ : n + 1;
//很明显我们这里返回的是 n+1 的值，
0000 0000 0000 0000 0000 0000 0000 1111
+ 1X a A 7 x ] ? ~ @
0000 0000 0000 0000 0000 0000 0001 0000将它转为十进制，就是 2^4 = 16 。我们会发现一个规律，以上的右移运算，最终会把最低位的值都转化为 1111 这样的结构，然后再加1，就是1 0000 这样的结构，* y B ? J / 9它一定是 2的n次幂。因此，这个方法返回的就是大于当前传入值的最小（最接近当前值）的一个2的n次幂的值。
pu j &t()方法详u X ]解
//put方法，会先调用一个hash()方法，得到当前key的一个hash值，
//用于确定当前key应该存放在数组的哪个下标位置
//这里的 hash方法，我们姑且先认为是key.hashCode()，其实不是的，一会儿细讲
public V put(K key, V value) {
return putVal(hash(key), key, value, fal 5 ; , C )se, true);
}
//把hash值和当前的key，valv i r d . ; &ue传入进来
//这里onR ^ G blyIfAbsent如果为true，表明不能修改已经存在的值，因此我们传入false
//evict只有在方+ $ 4 b法 afterNodeInsert- 4 w -ion(boolean evicd ) u G Z M g L qt) { }用到，可以看到它是一个空实现，因此不用关注这个参数
final V putVal(int hash, K key,: $ & * s [ s V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<e 0 & *K,V> p; int* z A 3 . n, i;
//判断table是否为空，如) | ) ,果空的话，会先调用resize扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根据当前key的hash值找到它在数组中的下标，判断当前下标位置是否已经存在元素，
//若没有，则把key、value包装成Node节R m k _ N d点，直接添加到此位置。
// i = (n - 1) & hash 是计算下标位置的，为什么这样算，后边讲
if ((p = tab[i = (n - 1) &amB u % :p; h+ 8 ! cash]v j J . v 3) == null)
tab[i] = newNor k = H n [ T A qde(hash, key, value, null);
else {
//如果当前位v 1 p h o 7 ~ 置* w ? 3 K已经有元素了d / ` ^ 9 & d，分为三种情况。
Node<K,V> e; K k;
//1.当前位置元素的hash值等于传过来的hash，并且他们的key值也相等，
//则把p赋值给e，跳转到①处，后续需要做值的覆盖处理
if K * _ w _ (p.hash == hash &m u 0 = 6 .amp;&
((k = p.key: l B s) == key ||j Z } c D (key != null && key.equalsu n 0 w & I(k))))
e = p;
//2.如果当前是红黑树结构，则把它加入到红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(0 d _ e R }this, tab, hash, key, value);
else {
//3.说明此位置已存在元素，并且是普通链表结构，则采用尾插法，把新节点加入到链表尾部
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//如果头结点的下一个节点为空，则插入新节点
p.next = newNode(hash, key, value, null);
//如果在插入的过程P 7 ? & 1 ( % # {中，链表长度超过了8，则转化为红黑树
if (binCod * # m o aunt >= TREEIFY_THRESHOLD - 1) // -1 foV _ F N ar 1st
treeifyBin(tab, hash);
//插入成功之后，跳出循环，跳转到①处
break;{ . y m & { E
}
//若在链表中找到了相同key的话，直接退出循环，跳转R S [ B T R 0到①处
if (e.hash == hash &&
((k = e.key) =5 } 2 M } K f u ,= key || (_ 0 I Ikey != null && key.eo q P ` v } (quals(k))))
break;
p = e;
}
}
//①x ! 7 6 $ P d 此时e有两种情况
//1.说明发生了碰撞，e代表的是旧值7 s h Z A H，因此节点位置不变，但是需要替换为新值
//2.: 5 , C 说明e是插入链表或者红黑树，成功后的新节点
if (e != null) { // existing mapping for key
V oldValue = e.value;
//用新值替换旧值，并返回旧值。
//oldVal6 @ N 4 a q jue为空，说明e是新增的节点或者也有可能旧值本来就是空的，因为hashmap可存空值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//看方法名字即可知，这是在node被访问之后需要做的操作。其~ j | N实此处是一个空实现，
//只有在 LinkedHashMap才会实现，用于实现根据F / P g R [ Z 6访问先后顺序对元素进行排序，hashmap不提供? x ; R /排序功能
// Callbacks to allow LinkedU } u u * PHashMap post-actions
//void afterNodeAccess(Node<K,V> p) { }
ax u gfterNodeAccess(e);
return oldValue;
}
}
//fail-fast机w ! [ t z B制
++modCount;
//如果当前数组中的元素个数超过阈值，则扩容
if (++size > threshold)
resize();
//同V , P ~ *样的空实现
a} # a sfterNodeInsertion(evict);
return null;
}hash()计算原理
前面 put 方法中说到，需要先把当前key进行哈希处理，我们看下这个方法是怎么实现的。
static final int hash(Object key) {
int h;
return (key =E ` F ( V / A= null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}这里，会先判断key是否为空，若为空则返回0。这也说明了hashMap是支持keD ( = ^y传 null 的。若非空，则先计算key的hashCo+ ( n [ n 6 K 8 :de值，赋值给h，然后把h右移16位，并与原来的h进行异或处理。为什么要这样做，这样做有什么好处呢？
我们知f c C n , _ ? O l道，hashCode()方法继承自父类Object，它返回的是一个 int 类型的数值，可以保证同一个应用单次执行的每次调用，返回结果都是相同的（这个说明可以在) 3 4hashCode源码上找到），这就保证了hash的确定性。在此基础上，再进行某些固定的运算，肯定结果也是可以确定的。
我随便运行一段程序，把s r -它的 hashCode的二进制打印出来，如下5 @ j E。
public static void main(String[] args) {
Object o = new Object();
iA t 6 w 4nt hal R 6 9 G 5sh = oM # S T Z.has, a L D - = : D :hCode();
System.out.println(hash);
System.out.println(Integer.toBinaryString(hash));
}
//1836019240
//1101101011011110110111000101000然后，进行 (h = key% - m b.hashCode()) ^ (h >>> 16) 这一段运算。
//h原来的值
0110 1101 0110 1111 0110 1110 0010 1000
//无符号右移16位，其实相当于把低位16位舍去，只保留高1p U W Z b6位
0000 0000 0000 0000 0110 1101 0110 1111
//然后高16位和原 h进行异或运算
0110 1101 0110 1111 0110 1110 0010 1000
^7 b v 7 H
0000 0000 0000 0000 011N ] }0 1101} ^ ` # n O d 5 0110 1111
=
0110 1101 0110 1111 0000 0011 0100 0111可以看到，其实相当于，我们把高16位值和当前h的低16位进行了混合，这样可以尽量保留高16位的特征，从而降低哈希碰撞的概率。
思考一下，为什么这样做，就@ C # m C # } + |可以降低哈希碰撞的概率呢？先别着急，我们需要结合 i = (n - 1) & hash 这一段运算来理解。
** (n-1) & hash 作用**
//②
//这是 put 方法中用k n O %来根据hash()值寻找在数组中的下标的逻辑，
//n为数组长度， hash为调T * v Q ] r用 hash()方法混] m w 6 Q U K合处理之后的hash值。
i = (n - 1) & hash复制代码我们知道，如果给定某个数值，去找它在某个数组中的下标位置时，直接用模运算就可以了（假设数组值从0开始递增）。如，我e @ * W `找 14G : ) 3 在数组长度为16的数组中的下标，即为 14 % 16，等于14 。 18的位置即为 18%16，等于2。
而②中，就是取模运算的位运算形式。以18%16为例
//18的二进制
0001 0010
//16 -1 即 15的二进制
0000 1111
//与运算之后的结果为
0000 0010
//G 7 z ( g ; a _ 可/ e v 9 r _以看到，上边的R j . Y z , q 8结果转化为十进制就是 2 。
//其实我们会发现一个规律，因为n是2的V N Zn次幂，因此它的二进制表现形式肯定是类似于
0001 0000
//这样的形式，只有一个位是1，其他位都是0。而它X * *减 1 之后的形式就是类似于
0000 1111
//这样的形式，高位都是0，低位V u 4 _ % w都是1，因此它和任意值进$ t @ ` o行与运算，结果值肯定在这1 + $ #个区间内
0000 0000 ~ 0000 1111
//也就是0到15之间，（以n为16为例）
//因此Y D i 7 M 4，这个运算就可以实现取模运算，而且位运算还有个好处，就是速度比较快。复制代码为什么高低位异或运算可以减少哈希碰撞
我们想象一下，假如用, { * _ t z key 原来的hashCode值，直接和 (n-1) 进行与运算来Q i H求数组下标，而不进行高低位混合运算，会产生什么样的结果。
//例如我有另外一个h2，和原来的 h相比较，高16位有很大的不同，但是低16位相似度很高，甚至相同的话。
//原h值
0110 11& g R v S % / Q f01 0110 11 S % / 411 0110 1110 0010 1000
//另外一个h2值
0100 0101 1110 1011 0110 0110 0010 1000
// n -1 ,即 15 的二进制
0000 0000 0000 0000 0000 0000 0000 1111
//可以发现 h2 和 h 的高位不& * R k D相同，但是低位相似度非9 Z u D 7 1 T q常高。
//他们分别和 n -1 进行与运算时，得到的结果却是相同的。（此处n假设为16） $ I s X m ) [ q
//因为 n-1V E @ P B ? V 的高16位都是0，不管 h 的高 16 位是什么，与运算之后，都不影响最终结果，高位一定全是 0
//因此，哈希碰撞的概率就大大增加了，并且 h 的高16 位特征全都丢失了。爱思考的同学可能就会有疑问了，我进行高低16位混合运算，是可以的，这样可以保证尽量减少高区位的0 _ 2 + k s特征。那么，为什么选择用异或运算呢f - 1 ( + r }，我用与、或、非运算不行吗？
这是有一定的道理的。我们看@ { ` - A %一个表格，就能明白了。
可以看到两个值进行与运算，结果会趋向于0；或运算，结果会趋向于1；而只有异或运算，0和1的比例可以达到1:f B Z 7 S $1的平衡状态。（非呢？别扯犊子了，两个值怎么做非运算。。。）
所以，异或运算之后，可以让结果的随机性更大，而随机性大了之后，N u 7 Y U哈希碰撞的概率当然就更小了。
以上，就是为什么要对一个hash值进行高低位混合，M | @ C并且选择异或运算来混* + , e A : Y K i合的原l 2 1因。
resize() 扩容机制
在上边 put 方法中，我们会发现，当数组为空的时候，会调用T T U 9 u e _ resize 方法，当数组的 size 大于阈值的时候，也会调用 resize方法。 那么看下 resize 方法都做了哪些V r p u z m 4事情吧。
final Node<K,V>[] resize() {
//旧数组
Node<K,V>[] oldTah I ^ * r n &b = table;
//旧数组的容量
int oldCap = (oldTab == null) ? 0 : oldTab.lZ { Dength;
//旧数组的# 5 h 3 H :扩容阈值，注意看，这里取的是当前对象的 threshold 值，下边的第2种情K L 3 # D ` 6 4况会用到。
int oldThr = threshold;
//初b ~ & i始化新数组的容量和阈值，分三种情况讨论。
int newCap,8 P 6 Q z n * h newThr = 0;
//1.当W . ~旧数组的容量大于0时，说明在这之前肯定调用过 rg 5 X T J R +esize扩容过一次，才会导致旧容量不为0。
//为什么这样说呢，之前我在 tableSizeFor 卖了个关子，? R & $需要注意的是，它返回的值是赋给了: r S threshold 而不是 capacity。
//我们, 3 y 4 v 2 % a在这之前，压根就没有在任何地方看到过，它给 capacity 赋初始值。
if (oldCap > 0) {
//容量达到了最大值
ifR I X z v (oldCap >= MAX/ l i F iIMUM_CAPACITY) {
threshold = Integer.MA% 2 g m r e I CX_VALUE;
return oldTab;
}
//新数组的容量和阈值都扩大原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAU4 P ?LT_INITIAL_- = . W T b 5 *CAPACITY)
n_ v D )ewThr = oldThr << 1; // double threshold
}
//2.到这里，说明 oldCap <= 0，并且 oldThr! j I d E | % k R(threshold) > 0，这就是 map 初始化X u ) I (的时候，第一次调用 resize的情况
//而 oldW C # 9 X 8 # C iThr的值等_ o * I于 threshold，此时的 threshold 是通过 tableSizeFor 方法得到的一个2的n次幂的值(我们以16为例)。
//因此，需要把 oldThr 的值，也就q k [ d l是 threshold ，赋值给新数组的容量 newCap，以保证数组的容量是2的n次幂。
//所以我们可以得出结论，当map第一次 put 元素的时候，就会走到这个分支，把数组的容量设置为正确的值 + p D ~ 2 C . 2（2的n次幂)
//但是，此时 threshold 的值也是2的n次幂，这不对啊，它应该是数组的容量乘以加载因子才对。别着6 S b @ s V K U ]急，这个会在③处理。Z E G @ n n W C d
else if (oldThr > 0) // initial capacitH s p Y qy was placed in threshold
newCap =Z V T g # ? { ( oldThr;
//3.到这里，说明 oldCap 和 oldThr 都是小于等于0的。也说明我们的map是通过默认无参构造来创建的，
//于是，数组的容量和阈值都取默认值就可以了，即 16 和 12。
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAU. z 9 SLT_INITIG H 6 # ~ e S 0 ;AL_CAPACITY);
}
//③ 这里就是处理第2种情况，因为 p f j U X s只有这种情况 newThr 才为0，
//因此计算 newThr（用 newCap即16 乘以加载因子 0.75，得到 12） ，并把它赋值给 threshold
iff & o C (newThr == 0) {
float ft = (float)newCap * loadFactor;
n] ( # f { t A ?ewThr = (newCap &l ) M x } %lt; MAXIMUM_CAPACITY &&) } q X % + & D a; ft &l/ I Pt; (float)MAXIMUM_CAPACITY ?
(int)ft : IntO z P Heger.MAX_V3 X E b e 8 7ALUE);
}
//赋予 threshold 正确的值，表示数组下次需2 R ` c % ?要扩容的阈值（此时就把原来的 16 修正为了 12）。
threshold = newThr;
@SuppressWarnin- / T j n ( cgs({\"rawtypes\",\"unchecked\"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];6 } 9 r z
table = newTab;
//如果原来的数组不为空，那么我们就需要把原来数组中的元素重新分配到新的数组中
//如果是第2种情况，由于是第一次调用resize，此时数组肯定是空的，因此也就不需( 0 ( & I要重新分配元素。
ifu ; q , d (oldTab != null) {
//遍历旧数组
for (int j- z g s i = 0; j < oldCap; ++j) {
Node<K,V> e;
//取到当前下标的第一个元素，如果存在，则分三种情况重新p D A h R o分配位置
if ((e = oldTab[j]) != null) {
oldTa1 E ib[j] = null;
//1.如果当前元素L o V b 6 & 1的下一个元素为空，则说明此处只有一个元素
//则直C ? e _ 7 | $ X #接用它的hash()值和新数组的容量取G ` D L 6模就可以了，得到新的下标位( t n 5 6置。
if (e.next == null)
newTab[e.hash &: S w Iamp; (newCap - 1)] = e;
//2X J N @.如u k H % U + % *果是红黑树结构，则拆分红黑树，必要时n w E有可能退化为链表
else if (e instanceof TreeNode)
((Treea , A 5Node<K,V>)e).split(r + v L } zthis, newTab4 [ ?, j, oldCap);
//3.到这里说明，这是一个长度大于 1 的普通链表，则需要计算并
//判断当前位g F 0 v置的链表是否需要移动到新的位置
else { // preserve order
// loHead 和 loTail 分别代表链表旧位置的头尾节点
Node<z [ G P;K,V> loHead = null, loTail = null;
// hiHead 和 hiTail 分1 A I y , w *别代表链表移动到新位置的头尾节点
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//如果当前元素的hash值和oldCap做与运算为0，则原位置不变
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//否则，需要移动到新的位置
else {
if (hH k ( miTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail =b [ d e;
}
} while ((e = next) != null);
//v i U原= } R位置不变的一条Y e d E链N ^ B表，数组下标不变
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//移动到新位| k 2 M # I 1 [ H置的B J - E f = $ 一条链表，数组下标为原下标加上旧数组的容量
if (hiTail != null) {0 C g g P V Q
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return n( # a * s ZewTab;
}上边还有一个非常重要的运算，我们没有讲解。就是下边这个判断，它用于把原来的普通h B 9 1 { ( a Q链表拆分为两条链表，位置不变或者放在新的位置。
if ((e.hash &t a V : { s [ v J; oldCap) == 0) {} else {}我们以原数组@ 6 H ~容量16为例，扩容之后容量为32。说明下为什么这样计算。
还是用之前的hash值举例。
//e.hash6 p | Y /值
0110 1101 0110 1111 0110 1110 0010 1000
//oldCa6 5 A & @p值，即16
0000 0000 0000 0000 0000 0000 0001 0000
//做与运算，我们会发现结果不是0就是非0，
//而且它取决于 e.hash 二进制位的倒数第五位是 0 还是 1，
//若倒数第五位为0，z / R则结果为0，若倒数第五位为1，则结果为非0。
//那这个和新数组有什么关系呢？
//别着急，我们看下新数组的容量是32，如果求当] x m | M 1 R y前hash值在新数组8 % ] a z 5 C中的下标，k : ) { s则为
// e.hash &( 32 - 1) 这样的运算 ，即 hash 与 31 进行与运算，
0110 1101 0110 1111 0110 1110 0010 1000
&
0000 0000 0000 0000 0000 0000 0001 1111
=
0000 0000 0000 0000 0000 0000 0000 1000
//接下来，我们对比原来的下标计算结果和新u S E 2的下标结果，看图看下面的图，我们观察，hash值和旧数组进行与运算的结果 ，跟新数组的与运算结果有什么不同。
会发现一个规律：
若hash值的倒数第五位是0，则新下标与旧下标结果相同，都为 0000 1000
若hash值的倒数第五位是1，则新下标（0001 1000）与旧下标（0000 1000）结果值相差了 16 。
因此，我们就d y m U L S可以根据 （e.hash & oldCap == 0） 这个判断O . ; ! d w的真假来决定，当前元素应该在原来的位置不变V ) R @ B，还是在新的位置t 4 3(原位置 + 16)。
如果，上边的推理还是不明白的话，我再举个简单的例子。
18%16=2 18%321 ~ M 1 ~ [ 8 q a=18
34%16=2 34%32=2
50%16=2 50%32=18怎么样，发现规律没，有没有那个感觉了？$ r ~ W
计算中的18，34 ，50 其实就相当于 e.hash 值，和新旧数组做取模运算，得到的结果，要么就是原来的位置不变，要么就是原来的位置加上旧数组的长度。
get()方法
有了前面的基础，get方法就比较简单了。
public V get(Object key) {
Node<K,V> e;
//如果节点为空，则返回null，否则返回节点的vy . 4 v k a 3 8 }alue。这也说明，hashMap是支持value为null的。
//因此，我们就明白了，为什么hashMap支持Key和va. ; R Qlue都为null
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getN8 g r Code(int hash, Object key) {
Node<K,V>[] tab; Node<K,d n g @ B . o ]V> first, e; int n; K k;
//首先要确保数组不能为空，然后取到A w _ H _ i 1 & c当前hash值计算出来的下标位置的第一个元素
if ((tab = table) != null &a3 8 { 8mp;& (n = tab.l & jlength) > 0 &P ~ M P n X `&
(first = tab[(n - 1) & hash]) != null) {
//若hash值和key都相等，3 U . @ ~则说j Y L 4 {明我们要找的就是第一个元素，直接返回
if (first.hash == hash && // always che v W + 5 u A 1 veck fc ) { [irst node
((kg 2 r } 7 Z = first.d % a U Ykey) == key || (key != null && key.e* Z t e Qquals(k))))
retg ! J ? i Uurn first;
//如果不是的话，就遍历当前链表（或红黑树）
if ((e = first.next) != null) {
//如果是红黑树结构，则找到当前key所在的节点位置
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash,$ B * P 8 , + + 5 key);
//如果是普通链表，则向后遍历查找，直到找到或者遍历到链表末尾为止。
do {
if (e.hash == hash &&
((k = e.a c ; . x o @key) ==e x p z F key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//否则，说明没有找到，返回nuX } D s _ _ll
return nT u x A h K h ^ -ull;
}为什么HashMa] } O h D H cp链表会形成死循环
准确的讲应该是 JDK1.7 的 HashMap 链表会有死循环的可能，因为JDK1.7是采用的头插法，在多线程环境下有可能会使链表形成环状，从而导致死循环。JDK1.? + h %8做了改进，用的是尾插法，p k 7 ! 8 y [ z不会产o 1 ) A 5 _生死循环。
那么，链表是7 K = a P怎么形成环状的呢？
关于这. W /一点的解释，我发现网上文章抄来抄去的，而且都来自左耳朵耗子，更惊奇的是，连配图都是一模一样的。（别问我为什么知道，因为我也看过耗子叔的文章，哈哈。然而，菜鸡的我，那篇文章，并没有看懂。。。）
我实在看不下6 / + O L }去了，于是一怒之下，就有了这篇文章。我会照着源码一步一步的分析变量之间的关系怎么变化T $ (的，并有配图哦。
我们从 puY ` i n P | ` /t()方法开始，最终找到线J M i x L E T程不安全的那个方法。这里省略中间不重要的B @ f 1 o x ^ ?过程，我只把方法的跳转流程贴出来：
//添加元素方法 -> 添加新节点方法 -> 扩容方法 -> 把原数组元素重新分配到新数组中
put() --> addEntry() -1 L h 0 )-> r= g 6 - / P 0esize() --> transfer()问题就发生在 transfH @ | ner 这个方法中。
我们假设，原数组容量只有2，其中一条链表上有两个元素 A,B) N q k % b =，如下图
现在，有两个线程都执行 transfer 方法。每个线程都会在它们自己的工作内存生成一个newTable 的数组，N Y v 6 n _ f i O用于存储变化后的链表，它们互不影响（这里互不影[ t A { & 3 b响，指的是两个新数组本身互不影响）。但是，需要? W { w : 9注意的是，它们操作的$ 1 E数据却是同一份。
因为，真正的5 r l { y数组中的内容在堆中存储，它们指向的是同一份数据内容。就相当于，有两个不同的引用 X，Y，但是它们都指向同一个对象 Z。这里 X、Y就是两个线程V / u : n &不同的新数组，Zf ! - H |就是B V % M C V B [ F堆中的A，B 等元素对象。
假设线程一执行到了上图1中所指的代码①处，恰好 CPU 时间片到了，线程U C f S N被挂起，不能继续执行了。 记住此时，线程 1 h M 8 = E D一中记录的 e = A ， e.next = B。
然后线程二正常执行，扩容后的数组长度为 4， 假设 A，B两个元素又碰撞到了同一个桶中。然后，通过几次 while 循环h a 6 k =后，采用头插法，最} ! } o 9 = K T z终呈现的结构如下：
此时，线程一解挂，继续往下执行。注意，此时线程一，记录的还是 e = A，e.next = B，因为它还未感知到最新的变化。
我们主要关注图1中标注的①②③④处的变量变化：
/**
* next = e.next
* e.next = newTabl? 8 @ D t m 3 9e[i]
* newTable[i] = e;
* e = next;
*/
//第一次循环,(伪代码)
e=A;next=B;
e.next=null //此时线程[ ) n一的新数组刚初始化完成，还没有元素
newTab[i] = A->null //把Av c B 4 ? 1 * `节点头插到新数组中
e=B; //下次循环的e值第一次循环结束后，线程一新数组的结构如下图：
然后，由于 e=B，不为空，进入第二次循环。
//第二次循环
e=B;next=A; //此时A，B的内容已经被线程_ ~ U二修改为 B->A->null，然后被线程一读到，所以B的下一个节点指向A
e.next=A->null // A->null 为第一次循环后线y o o ; ~ % {程一新数组的结构
newTab[i] = B-&Y Y _ / y M ugt;A->nulK w F } 1 K { ,l //新节点B插入之后，线程一新数组的结构
e=A; //下次循环的 e 值第二次循环结束后，线程一新数组的结构如下图：
此时，由于 e=A，不为空，继续循环。
//第三次循环
e=A;next=nullK ( o v i W Q; // A节点后边已经没有节点了
ef M : J E.next= B->A->null // B->A->null 为第二. ` u + & G次循环后线程一新数组的结构
//我们把A插入后，抽象的表达为 A->B->Y ! Z hA->null，J t ` P V D :但是，A只能是一个，不能分身啊z m A [ w q D l L
//因此实际上是 e(A).next指向发生了变化，AK u D S 4 { m v %的 next 由指向 null 改为指向了 B，
//而 B 本身又指向A，因此A和B互相指向，成环
newTab[i] = A-6 L i - | + j ~>B 且 B->A
e=next=null; //e此u X @ ? m b 3时为空，结束循环第三次循环结束后，看下图，A的指向由 null ，改为指向为 B，因此 A 和 B 之间成环。
这时，有的同学可能就会问了，就算他们成环了，又怎样，跟死循环有什么关系？
我们看下 get() 方法（最终调用 getEntry 方法），
可以看到查找元素时，只要 e 不为空，就会一直g E 6 ? . 4 l ~ ,循环查找下去。若有某个元素 C 的 hash 值也落在了和 A，B元素同一个桶中，则会由于， A，B互相指向，e.next 永远不t ` : j A p M Z @为2 * & r Q B E 0空，就会形成死循环。
作者：烟雨星空
原文链H T } t %接：https://juejin.im/post/5e93ca9d6fb9a03c3176248$ D ] o 5 D If