集合

HashMap的扩容机制是什么？

❒ 扩容过程
✔ 初始化后第一次添加元素需要调用resize方法进行扩容，数据初始化数组长度为16。
✔ 以后每次扩容都是达到了扩容阈值(数组长度 * 0.75)。
✔ 每次扩容的时候，都是扩容之前容量的2倍。

❒ 扩容之后
✔ 会新创建一个数组，需要把老数组中的数据挪动到新的数组中。
✔ 没有hash冲突的节点，则直接使用e.hash & (newCap - 1)计算新数组的索引位置。
✔ 如果是红黑树，走红黑树的添加。
✔ 如果是链表，则需要遍历链表，可能需要拆分链表，判断(e.hash & oldCap)是否为0，该元素的位置要么停留在原始位置，要么移动到原始位置 + 增加的数组大小这个位置上。

✔ 因为 hash 值不变、oldCap 是扩容前的固定值，所以 hash & oldCap 的结果是唯一且确定的。
✔ 这就保证了每个元素在扩容时只会被分到「原索引」或「原索引 + oldCap」两个位置中的一个，不会有第三种可能。

❒ 链表长度 > 8，数组大小 >= 64的时候链表才会进化成红黑树
✔ 如果链表长度超过了长度阈值(TREEIFY_THRESHOLD) 8。
✔ 如果数组大小等于16，小于最小树化容量(MIN_TREEIFY_CAPACITY)64。
✔ 在这种情况下，即使链表长度超过了8，由于总容量小于64，链表不会转为红黑树，而是会进行扩容操作。