HashMap系列：2次方扩容
（一）HashMap系列：负载因子0.75
（二）HashMap系列：树化阀值8，退化阀值6
（三）HashMap系列：2次方扩容
（四）HashMap系列：put元素（不看完将后悔一生！）
红黑树系列：
一、《算法—深入浅出》N叉树的介绍
二、《算法—深入浅出》红黑树的旋转
三、《算法—深入浅出》红黑树的插入
四、《算法—深入浅出》红黑树的删除
一、前言
HashMap系列前两篇已经多次提到，HashMap 在元素达到负载因子阀值时，会自动扩容，HashMap 的初始化大小与扩容也是非常有讲究的，初始化大小的默认值不是随便定义的，扩容策略也是有考究的，今天我们就来聊聊：
- 初始化大小的默认值为何是 16；
- 扩容为何每次都是当前数组大小的 2 倍；
二、计算对象所在HashMap的下标
大家一般能想到的计算下标方式，应该都是从大学课本中学到的：
int index = K % Array.length;
含义很简单：对K取模，模数是数组的长度；
看起来没有问题，那有没有更快的计算方式呢？
HashMap源码就给了我们一种新的计算方式：（按位）与！
当我们有一个数组，长度为16，那么23这个数应该放在这个数组中的哪个下标位置上呢？
23 & (16 - 1) = ?
23: 0001 0111
16 - 1 = 15: 0000 1111
-------------------------
result: 0000 0111 (7)
&(与)： 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0；即：任何数 & 0 = 0
为什么 23 & (16 - 1) 而不是 23 & 16 呢？
因为数组的下标是从 0 开始！
16 是 2 的N次幂，16 - 1 = 15 其二进制为低位全是 1（16的二进制为 0001 0000，15的二进制为 0000 1111），因此，任何一个数与 15 做『与』操作，直接将高位置0，而低位则是遇1保留，与0则0，因此就能非常方便的获取实际的下标值。
不信的话，我们可以再来几个例子：
16 & (16 - 1) = ? 22 & (16 - 1) = ?
16: 0001 0000 22: 0001 0110
16 - 1 = 15: 0000 1111 16 - 1 = 15: 0000 1111
---------------------------- -----------------------------
result: 0000 0000 (0) result: 0000 0110 (6)
HashMap 源码中，默认的数组大小就是 16，那为何不能是其它数呢？
假设数组长度为 10：
2 & (10 - 1) = ? 6 & (10 - 1) = ?
2: 0000 0010 6: 0000 0110
10 - 1 = 9: 0000 1001 10 - 1 = 9: 0000 1001
-------------------------- -------------------------
result: 0000 0000 (0) result: 0000 0000 (0)
发现没？当数组长度为非 2 次幂时，虽然 key 不同，但是计算出来的下标都一样（0），非常容易出现 hash 冲突，而 2次幂则完美的解决这个冲突的问题。
三、当前数组大小的2倍扩容
在第二节中，我们了解到如何快速计算 hash数组的下标，以及 HashMap 源码中，默认初始的数组大小是 16 。本小中，我们将来看看，当新增元素达到数组的阀值时（数组大小 * 负载因子），HashMap 会开始扩容，扩容也是有讲究的，每次扩容都是当前数组大小的2倍。
例如，初始大小是16，当元素达到 12（16 * 0.75）时，会进行2倍扩容，大小变为 32（16 * 2）；下次扩容也是2倍变成64。每次扩容都保证数组的大小是 2的N次幂，道理就是第二节中阐述的。
每次扩容后，还需要重新计算 hash数组中每个元素的新的下标（因为分母，即数组大小改变了，hash下标肯定不对了嘛）。
我们来看个例子：
public class Main {
public static void main(String[] args) {
// 初始数组大小 16，随机放 6 个数
int[] array = new int[16];
for (int i = 0; i < 6; i ++) {
int rand = (int) (Math.random() * 100);
int idx = rand & 15;
array[idx] = rand;
System.out.println(rand + "在（16数组大小）的下标 = " + idx);
}
System.out.println(Arrays.toString(array));
// 2倍扩容后，重新计算下标
int[] newArray = new int[32];
for (int i = 0; i < array.length; i ++) {
if (array[i] == 0)
continue;
int idx = array[i] & 31;
newArray[idx] = array[i];
System.out.println(array[i] + "在（32数组大小）的下标 = " + idx);
}
System.out.println(Arrays.toString(newArray));
}
}
重点一：注意标红的 19 在数组扩容后的下标变动
96在（16数组大小）的下标 = 0
4在（16数组大小）的下标 = 4
75在（16数组大小）的下标 = 11
12在（16数组大小）的下标 = 12
34在（16数组大小）的下标 = 2
[96, 0, 34, 19, 4, 0, 0, 0, 0, 0, 0, 75, 12, 0, 0, 0]96在（32数组大小）的下标 = 0
34在（32数组大小）的下标 = 2
4在（32数组大小）的下标 = 4
75在（32数组大小）的下标 = 11
12在（32数组大小）的下标 = 12
[96, 0, 34, 0, 4, 0, 0, 0, 0, 0, 0, 75, 12, 0, 0, 0, 0, 0, 0, 19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
四、HashMap.resize 分析
HashMap 如果只是数组扩容2倍，再调整数组中每个元素的下标，那咱们也没必要分析了。我们别忘记，HashMap的数组结构：
数组 +（单链表 <--> 红黑树）
因此，扩容后，如果还有链表或者红黑树，那么，这些元素也需要判断是否需要调整（hash数组大小变了，下标也就可能改变），所以，一次扩容，涉及到三种情况的调整：
- 数组中的元素的 next 为 null，表明没有链表，也没有黑红树，则直接计算新的下标，放到新的数组中；
- 数组中的元素是红黑树，则进行拆分调整，可能还涉及到树的退化；
- 元素是链表，遍历调整；
4.1、数组的 rehash
final Node<K,V>[] resize() {
......
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) { // e = oldTab[j]
oldTab[j] = null; // 将原数组中的对象置为null
if (e.next == null) // 如果 next 为null，表明该节点没有链表，也不是红黑树
newTab[e.hash & (newCap - 1)] = e; // 简单的放到新的下标中
}
}
}
4.2、红黑树的 rehash（建议大家先看：单链表的 rehash）
final Node<K,V>[] resize() {
......
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) { // e = oldTab[j]
oldTab[j] = null; // 将原数组中的对象置为null
else if (e instanceof TreeNode) // 如果是红黑树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
}
}
}
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) { // bit = oldCap
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
红黑树的调整，大家可能会感到害怕、颤抖！如果，大家听取我的建议，先看了链表的 rehash，那么，再看红黑树的调整，将会觉得非常的简单！代码看起来较多，同样，我们将其拆为两部分（再次建议，一定要先看完链表的 rehash ，再看这里！！！！）：
4.2.1、树节点拆分至高、低位链表
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// 与链表拆分相同，分为低位链表、高位链表
// 虽然类型是 TreeNode，但在拆解时，只用到了 next 节点
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
// 记录低位列表、高位列表中元素的个数
// 在树化与退化时，需要判断链表中的个数与8、6的关系
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
// 高低位区分
if ((e.hash & bit) == 0) { // bit = oldCap
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
// 高低位链表的树化与退化
.......
}
是不是非常的简单！但有一种极端情况，大家想的到么？
4.2.2、高低位链表的树化与退化
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
// 拆分为高、低位链表
......
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD) // 小于等于6，即树退化为单链表
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead; // 否则树化
if (hiHead != null) // else的情况：所有元素都在低位链表中，所以已经树化了！
loHead.treeify(tab);
}
}
////////////////////////////////////////////// 高位操作：同上！
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
至于，如何树化与退化，这其实与红黑树的算法有关，大家可以看源码，也可以看我的红黑树系列，这里就不再展开了。
4.3、链表的 rehash
final Node<K,V>[] resize() {
......
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) { // e = oldTab[j]
oldTab[j] = null; // 将原数组中的对象置为null
// 单个元素
...
// 红黑树
...
// 链表
else {
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) { // oldCap = oldTab.length;
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;
}
}
}
}
}
链表的拆分，代码较多，为了帮助大家能够快速的理解，我先给出一张逻辑图：
HashMap链接rehash .png
以及再将代码进行拆分，分为不同的维度来讲解，帮助大家理解：
4.3.1、变量
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
咋一看，有4个变量，但是，我们如果仔细想想，可以发现，其实是两个链表的首、尾索引（或者在C中叫指针更好理解）；这两个链表，分为低位链表（lo-link）和高位链表（hi-link）；
本来想和大家卖个关子，但想了想，还是先直接说出细节（低位链表、高位链表的作用）：
- 低位链表：原链表中的元素，如果 rehash 后，所对应到新扩容数组后的下标不变，则放入低位链表中；
- 高位链表：原链表中的元素，如果 rehash 后，所对应到新扩容数组后的下标发生改变，则放入高位链表中；
我们可以注意下，节点19，在数组 capacity = 16时，下标是3，而在数组 capacity = 32时，下标是19。
我们可以这么理解
：
节点 19 & 16 == 1，因此应该调整放入高位链表中，并且节点 19 新的下标 = 原下标 + 扩容前的数组大小，即 newIdx = oldIdx + oldCapacity ！
4.3.2、遍历链表
// 高、低位链表变量区
.....
// 链表遍历，从数组的第一个元素 e 开始
// e = oldTab[j]
do {
next = e.next;
.....
} while ((e = next) != null);
4.3.3、算法：高、低位节点区分（基于这个算法，可以衍生很多经典的算法）
do {
next = e.next;
if ((e.hash & oldCap) == 0) { // 放入低位链表
....
}
else { // 放入高位链表
....
}
} while ((e = next) != null);
什么？大家是不是看着很蒙？如果大家仔细看了第二小节中的：计算对象所在的 hash 下标，那么就容易想到（以 cap = 16 举例）：
23 & (16 - 1) = ? 23 & 16 = ?
23: 0001 0111 23: 0001 0111
16 - 1 = 15: 0000 1111 16: 0001 0000
----------------------------- -------------------------------
result: 0000 0111 (7) result: 0001 0000 (16)
差异就在于：
- 快速获取下标，方法是 e.hash &（n-1）；
- 高低位的区分，方法是 e.hash & n ；
- 如果原来的元素，其键值大于原来的数组大小（capacity），那么，和原来的 capacity 与操作，一定不等于0；反之则为0。
大家可以看上面，我写扩容 Demo 时，打印输出有醒目的提醒：
4.3.4、高低位链表加入添元素（高、低链表操作一样）
if ((e.hash & oldCap) == 0) {
if (loTail == null) // 如果低位链表尾索引为 null，表示链表为空
loHead = e; // 低位链表首索引 = e
else
loTail.next = e; // 尾索引不为 null，则 尾索引.next = e
loTail = e; // 调整尾索引，指向链表中的最后一个元素
}
else {
if (hiTail == null) // 高位链表操作 等同 低位链表操作
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
4.3.5、高低位链表放入到新的数组中
大家可以看我上面醒目提示的：重点二；高位链表所属的位置
// 低位链表，仍旧放在原来的下标：j
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 高位链表，将会放到新的下标：j + oldCap
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
如果大家多想一步，会发现，后面的其它待调整元素，是不会和现在的 j 或者 j + oldCap 有冲突的！
好啦！HashMap 的扩容调整，内容很多，如果第一次看源码或者本文，需要好好的消化下！
