【Java集合篇】HashMap 是如何扩容的

?? 为什么需要扩容?

HashMap在Java等编程语言中被广泛使用，用于存储键值对数据。HashMap的实现原理是基于哈希表，通过哈希函数将键转化为桶的位置，从而实现快速查找、插入和删除操作。

然而，当HashMap中的元素数量增加时，哈希冲突的概率也会随之增加，这可能导致HashMap的性能下降。具体来说，当一个桶中的元素过多时，查询、插入和删除操作的时间复杂度会变为O(n)，这违背了HashMap设计的初衷。为了解决这个问题，HashMap会在必要时进行扩容。

扩容的目的是为了增加HashMap的容量，从而减少哈希冲突的概率，提高查询、插入和删除操作的性能。扩容的过程涉及到重新计算所有元素的哈希值和重新分配元素到新的桶中，这是一个相对耗时的操作。因此，为了平衡性能和扩容的开销，通常会将HashMap的容量设定为一个较大的初始值，并在需要时进行扩容。

另外，扩容还可以帮助维持HashMap的性能稳定性。由于负载因子是存储元素的数量与哈希表容量的比值，当负载因子过高时，哈希表的性能会下降。通过适时地扩容，可以控制负载因子在一个合适的范围内，从而保证HashMap的性能。

HashMap需要扩容是为了减少哈希冲突的概率，提高查询、插入和删除操作的性能，以及维持性能稳定性。

当我们在Java 中使用 HashMap 时，可以通过以下代码示例来理解扩容的原理：

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        // 创建一个初始容量为16，负载因子为0.75的HashMap
        HashMap<String, Integer> map = new HashMap<>(16, 0.75f);

        // 添加元素到HashMap中
        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Charlie", 35);
        map.put("David", 40);

        // 输出当前HashMap的容量和已使用容量
        System.out.println("Initial capacity: " + map.capacity());
        System.out.println("Used buckets: " + map.size());

        // 添加更多元素，触发扩容
        map.put("Eve", 45);
        map.put("Frank", 50);
        map.put("Grace", 55);
        map.put("Henry", 60);

        // 再次输出当前HashMap的容量和已使用容量
        System.out.println("Current capacity: " + map.capacity());
        System.out.println("Used buckets: " + map.size());
    }
}

在上述代码中，我们创建了一个初始容量为16，负载因子为0.75的HashMap。当我们向HashMap中添加元素时，如果已使用容量超过了负载因子与当前容量的乘积，HashMap就会触发扩容。扩容后，HashMap的容量会增加，从而减少哈希冲突的概率，提高查询、插入和删除操作的性能。

参考前两篇博文：

【Java集合篇】负载因子和容量的关系
【Java集合篇】为什么HashMap的Cap是2^n，如何保证？

假设现在散列表中的元素已经很多了，但是现在散列表的链化已经比较严重了，哪怕是树化了，时间复杂度也没有O(1)好，所以需要扩容来降低Hash冲突的概率，以此来提高性能。

我们知道，当 ++size >threshold 之后详见java.util.HashMap#putVal 方法)，HashMap就会初始化新的新的桶数组，该桶数组的size为原来的两倍，在扩大桶数组的过程中，会涉及三个部分:

1 . 如果某桶节点没有形成链表，则直接rehash到其他桶中


2 . 如果桶中形成链表，则将链表重新链接


3 . 如果桶中的链表已经形成红黑树，但是链表中的元素个数小于6，则进行取消树化的操作

?? 桶元素重新映射

如果桶中只有一个元素，没有形成链表，则将原来的桶引用置为null，同时，将该元素进行 rehash 即可，如下代码所示:

if (e.next == null) {
	newTab[e.hash & (newCap - 1)] = e;
}

在Java的HashMap中，当元素数量增加到一定阈值时，为了提高性能和减少哈希冲突，会触发桶的重新映射（rehashing）。这是通过扩容来实现的。

桶的重新映射过程涉及到以下步骤：

1. 计算新的容量：扩容时，新的容量通常是旧容量的一个固定倍数（例如，默认情况下是原容量的两倍）。
2. 生成新的桶数组：根据新的容量，创建一个新的桶数组。这个数组的长度是原来的两倍（在默认情况下）。
3. 重新计算哈希值：遍历旧桶中的每个元素，并使用新的哈希函数重新计算它们的哈希值。这是为了确保元素能够均匀分布在新的桶数组中，减少哈希冲突。
4. 重新放置元素：根据新计算的哈希值，将每个元素放置在新的桶数组中的适当位置。
5. 更新HashMap状态：更新HashMap的容量、大小以及相关的内部状态。

这个过程是必要的，因为随着元素的增加，哈希冲突的概率也会增加，导致性能下降。通过扩容和重新映射，可以维持HashMap的高效性能。

??链表重新链接

假设有4个key，分别为a，b，c，d，且假定他们的hash值如下：

hash(a) = 3;  hash(a) & 7 = 3;    hash(a) & 8 = 0;
hash(b) = 11;  hash(b) & 7 = 3;   hash(b) & 8 = 8;
hash(c) = 27;  hash(c) & 7 = 3;   hash(c) & 8 = 8;
hash(d) = 59;  hash(d) & 7 = 3;hash(d) & 8 = 8;

假如此时HashMap的cap为 8，某个桶中已经形成链表，则可得到: table[3]=a->b->c->d。

如果此时扩容，将newCap设为16，我们可以看到如下结果:

hash(a) = 3; hash(a) & 15 = 3;
hash(b) = 11; hash(b) & 15 = 11;
hash(c) = 27; hash(c) & 15 = 11;
hash(d) = 59; hash(d) & 15 = 11;

我们会发现，当hash(k) & oldCap = 0 (即hash(a) = 3;的这个记录)时，这些链表的节点还是在原来的节点中(扩容后他的结果还是3) ，同时如果hash(k) & oldCap != 0时(11 27 59这几条记录)，这些链表的节点会到桶中的其他的位置中 (从3变成了11)。

所以，对于链表来说，我们就不用逐人节点重新映射，而是直接通过hash(k) & ldCap进行分类，之后统一移动他们的位置即可。源码如下:

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;
}

?? 取消树化

有了上面链表重新连接的经验，我们会发现，其实树化后的节点，也可以使用该操作来降低红黑树每人节点rehash时的时间复杂度，所以红黑树的 TreeNode 继承了链表的Node类，有了next字段，这样就可以像链表一样重新链接，源码如下:

TreeNode<K,V> loHead = null,loTail= null;
TreeNode<K,V> hiHead = null, hiTail = null;
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) {
		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;
	}
}

当上面的操作完结后，HashMap会检测两个链表的长度，当元素小于等于6的时候，就会执行取消树化的操作，否则就会将新生成的链表重新树化。

取消树化非常简单，因为之前已经是条链表了，所以只需要将里面的元素由TreeNode转为Node即可。

至于重新树化的过程，请听下回分解~

??拓展知识仓

??除了rehash之外，哪些操作也会将树会退化成链表?

在 remove 元素的时候，这个过程中也会做退化的判断，如以下代码中，也会在这个分支中执行退化的操作(untreeify)，如下代码所示:

if (root == null (movable 8& (root.right == null  (rl = root.left) == null rl.left == null))) {
	tab[index] = first.untreeify(map); // too small
	return;
}