hashMap类中的几个属性
要想理清resize方法，必须先熟悉这几个hashMap类中的几个属性
//HashMap的 初始容量为 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的扩容因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//转换红黑树的临界值，当链表长度大于此值时，会把链表结构转换为红黑树结构
static final int TREEIFY_THRESHOLD = 8;
//转换链表的临界值，当元素小于此值时，会将红黑树结构转换成链表结构
static final int UNTREEIFY_THRESHOLD = 6;
//当数组容量大于 64 时，链表才会转化成红黑树
static final int MIN_TREEIFY_CAPACITY = 64;
//记录迭代过程中 HashMap 结构是否发生变化，如果有变化，迭代时会 fail-fast
transient int modCount;
//HashMap 的实际大小，可能不准(因为当你拿到这个值的时候，可能又发生了变化)
transient int size;
//存放数据的数组
transient Node<K,V>[] table;
// 扩容的门槛，有两种情况
// 如果初始化时，给定数组大小的话，通过 tableSizeFor 方法计算，数组大小永远接近于 2 的幂次方，
// 比如你给定初始化大小 19，实际上初始化大小为 32，为 2 的 5 次方。
// 如果是通过 resize 方法进行扩容，大小 = 数组容量 * 0.75
int threshold;
/** HashMap中的内部类 **/
//链表的节点 1.7之前叫Entry，1.8之后叫Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
//红黑树的节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {}
resize()方法整段代码如下：
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;
}
resize()方法体分段讲解
-
第一阶段：计算出新的newCap(扩容后的容量)和newThr(扩容后阈值)
首先得到扩容之前的table数组oldTab的最大容量oldCap和阈值oldThr，如果oldTab==null，则table数组仍指向空，还未被赋值
接着设置newCap和newThr初始值为0
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
如果oldCap大于0，进入另一个if -else if分支
如果oldCap已经达到了最大容量，那么直接返回oldTab不做处理
如果oldCap的2倍容量仍然比最大容量小，那就说明可以继续扩容，newCap设置为oldCap的2倍
同时将newThr设置为oldThr的2倍
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
}
如果oldCap=0，那就来到了如下判断语句：
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
一开始我觉得很奇怪，为啥oldCap=0，oldThr可能>0呢？后来明白了，想知道这是为啥就要先对hashmap的构造方法有一定了解：
//无参构造方法
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//带参构造方法 设定初始容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//带参构造方法 设定初始容量和扩容因子
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);
}
这时候比如我们使用的是无参构造方法
那么成员常量threshold==0，table==null,也就意味着oldCap==0，这时候如果调用resize方法，它就知道此时table数组需要默认初始化了，就会直接进入如下if判断中并初始化newCap和newThr
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
如果我们使用的是带参构造方法，情况会有很大的不同
上文中提到的带参构造方法有两种，区别就是扩容因子loadFactor采用个性值还是采用默认值，不管采用何值，扩容因子只是代表了阈值和容量之间的比例关系
关键在于我们可以设置个性值initialCapacity，也就是说可以自定义table数组的初始容量是多大。不过要注意的是，table数组最终的实际初始容量大概率不是我们自定义的初始容量，为什么呢？
public HashMap(int initialCapacity, float loadFactor) {
...
...
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
首先从这个带参构造方法可以看到，this.threshold = tableSizeFor(initialCapacity)，也就是通过我们设定的initialCapacity，通过tableSizeFor方法将返回值赋给成员变量threshold
tableSizeFor方法我们只需要知道它的返回值有什么特点就好，它会返回一个整数，这个整数是一个与initialCapacity最接近的，并且比initialCapacity大的 2的n次幂的整数。例如我们设定initialCapacity==7，那么return tableSizeFor(7)==8
所以我们现在清楚，尽管调用带参构造方法后threshold赋上值了，但是调用resize方法给table数组赋值之前，table数组就仍然指向null，对应的lodCap==0，而oldThr=threshold>0,因此以下分支结构是有可能执行到的：
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
我们看到改判断成立时，将oldThr赋值给了newCap，也就是说对于个性设置初始容量后，数组的容量最后等于首次被赋值的threshold。
然后到了如下if判断语句
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
这个if判断语句中newThr==0，其实newThr==0的情况就是之前所说的oldCap==0&&oldThr>0的情况，将newCap乘上一个扩容因子，因为有可能结果为浮点型，所以用float类型的局部变量ft接收，最后再将ft转成int类型赋值给newThr阈值，前提是newCap还未达到最大容量，否则就直接将最大容量赋给newThr。
threshold = newThr;
最后，不管执行上面哪种if判断语句，将得到的newThr赋值给threshold。这里注意对于进入if (newThr == 0)判断语句的threshold被重新赋值了，而原先的threshold值前文讲到已经被赋值给了newCap。
-
第二阶段：根据newCap和newThr构造出新的newTab
用newTab来接收一个新的存放Node节点类型数据的数组，newCap为初始数组容量，然后将table指向newTable，实质就是指向new Node[newCap]，注意这里的table就是hashmap类中的成员变量
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
接下来就进入到了第一个判断oldTab != null，我们知道当oldTab中已经存在元素，才会进行接下来的一系列因为扩容导致的索引位重排，元素重排等操作，因此先判断oldTab是否不为空是非常自然的
if (oldTab != null) {
...
...
接着进入一个循环，从j=0到j=oldCap-1 ，遍历hash table ，每次遍历都会定义一个Node节点类型的指针e，
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
...
...
进入循环后首先判断指针e指向的oldTab中下标为j的位置是否为空，不为空才需要进行接下来对该索引位元素的操作，对于索引位不为空的情况，把oldTab[j]重置为null，因为所有元素进行重排后最终会放入newTab中，oldTab中的元素被遍历并赋值给指针e后就可以置空了。
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
...
...
随后判断e指向的节点的下个节点是否为null，如果为null就说明还未形成链表，索引位上只有一个元素，然后将指针e指向的元素直添加到新创建的newCap容量的newTab中该元素对应应该存放的位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
如果指针e指向的节点属于树节点类型，那就通过TreeNode<K,V>类的split方法重排节点
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
-
Head节点 Head 节点/重排后节点的索引位
如果以上情况都不符合，那就说明指针e指向的元素所在位置已经形成了链表但还未树化，由于扩容后元素重排，重排的元素之间又会重新链接最终形成新的链表，所以我们需要先定义一些头指针，尾指针，来作为中间件连接重排后的节点
Node<K,V> loHead 指向 重排后仍会处于原索引位的节点之间重新链接后的链表的头节点 的指针
Node<K,V> loHead 指向 重排后仍会处于原索引位的节点之间重新链接后的链表的尾节点 的指针
Node<K,V> hiHead 指向 重排后应该处于新索引位的节点之间重新链接后的链表的头节点 的指针
Node<K,V>hiTail 指向 重排后应该处于新索引位的节点之间重新链接后的链表的尾节点 的指针
Node<K,V> next 节点类型的next 指针，用于指向下一个节点
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
讲到这里可能有些小伙伴有些疑惑，重排后节点所处的索引位与原索引位有啥关系呢？
假设某一节点的哈希值为300 哈希表初始容量为16
则初始索引位 300%16=12
第一次扩容后索引位 300%32=12
第二次扩容后索引位 300%64=44=32+12
第三次扩容后索引位 300%128=44
。。。。。。
我们可以看到索引位只有两种情况，一种是扩容后索引位=扩容前索引位，另一种情况是扩容后索引位=扩容前的索引位+扩容前的hash table容量
-
do...while 循环
回到代码继续看，接下来是一个do...while循环，这一部分是resize方法中的关键，节点的重排和链接在这段代码中完成，我慢慢讲
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);
首先看循环的终止条件:
do {
next = e.next;
...
...
}while ((e = next) != null);
next指针指向 e指向节点的下一个节点，随后while判断体内，首先让e指针也指向下一个节点，随后判断next指向的下一个几点是否为null，是null就代表原始链表的遍历结束，退出循环，如果不为null就继续遍历链表中剩下的节点，每次循环结束e指针立即指向后一个节点。
再来看循环体内的代码：这里有两个大的分支，第一个分支能使(e.hash & oldCap) == 0成立的情况就是：原索引位上的链表中，重排后仍会处于原索引位 的节点。第二个分支成立的情况就是：重排后将处于（原索引位+原hash table容量） 的节点
-
重排后仍会处于原索引位 的节点
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
注意，这个分支中接下来所述的节点都是 重排后仍会处于原索引位 的节点，这些节点之间不一定相邻
第一次进入该分支 loTail初始为null，将loHead头指针指向链表中的第一个节点（遍历到链表的第一位），随后将loTail尾指针指向链表中的第一个节点，此时头尾节点都指向链表中的第一个节点
随后经过若干轮循环，若第二次进入该分支，我们看到loHead头指针保持不动，尾指针指向的第一个节点对象中的next指针指向了此时遍历到的第二个节点，说白了就是第一个节点和第二个节点链接上了。随后尾指针重新指向了当前的尾节点，即第二个节点。
如此循环往复，直到链表中的所有元素遍历完，那么所有的节点都会重新链接上形成一个新的链表，这个链表中的节点都是 重排后仍会处于原索引位的节点
-
重排后将处于(原索引位+原hash table容量) 的节点
注意，这个分支中接下来所述的节点都是 重排后将处于新索引位 的节点，这些节点之间不一定相邻
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
这一部分的链接原理和第一个分支完全一样，只是形成的链表中的节点是 重排后将处于新的索引位的节点 而已
-
将两条链表添加到newTab
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
两条链表的尾节点最后都指向null
对于 重排后仍会处于原索引位的节点 组成的链表，将该链表的头节点指针赋给newTab中对应的索引位
对于 重排后将处于新索引位的节点 组成的链表，将该链表的头节点指针赋给newTab中对应的索引位
-
新哈希表newTab
那么最终就产生了一个扩容后的新hash table数组 newTab
return newTab
![Java小案例——随机数猜测随机数猜测[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)