记录读源码-HashMap（2）

1.HashMap的扩容机制

  HashMap内部提供了resize()方法,该方法主要用于初始化生成table数组以及将原来的table数组（下面称为桶）进行扩容,HashMap按当前桶数组长度的2倍进行扩容。在扩容两倍之后, 原来数组中存放的Node要存放到新的数组中,重新计算键值对的位置，并把它们移动到合适的位置上去.  接下来我们来看看具体的实现：

  源码比较长，提取出来大概做了这几件事：

  1.重新计算数组大小newCap，以及新的临界值newThr;

  2.初始化新的数组，并将旧的数组中键值对节点重新映射到新的桶数组里

  对步骤1进行分解：

对步骤2中重新映射节点进行分解：

重新映射节点需要考虑节点类型。对于树形节点，需先拆分红黑树再映射。对于链表类型节点，则需先对链表进行分组，然后再映射。关于红黑树拆分的逻辑后面再说，先来看看链表是怎样进行分组映射的。

从源码中可以看出：元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置，也就是说原索引的位置和在原索引+oldCap的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

  元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化

2.树化

  链表树化是jdk1.8中HashMap新增加的一个优化，虽然降低了处理频繁的碰撞，代码复杂度也随之上升。笔者对红黑树不是很熟悉，只知道红黑树是一种自平衡的二叉查找树，本身就比较复杂。所以笔记不对红黑树展开描述，有需要了解请自行搜索学习。

  先来看一下链表转树的源码：

  从源码可以看到，当桶数组的长度较小时，如果节点超过阈值时，优先是扩容，优先扩容可以避免一些列的不必要的树化过程。同时，桶容量较小时，扩容会比较频繁，扩容时需要拆分红黑树并重新映射。所以在桶容量比较小的情况下，树化反而变成吃力不讨好，增加复杂度。HashMap具体怎么树化就不继续深入探究了。