如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

题目详细答案

当HashMap的大小超过了负载因子（load factor）定义的容量时，HashMap会进行扩容（resize）。

扩容的具体步骤

假设当前HashMap的容量是N，负载因子是L，当插入的键值对数量超过N * L时，HashMap会进行扩容。具体步骤如下：

  1. 计算新的容量： 新的容量通常是当前容量的两倍。假设当前容量是N，新的容量是2 * N。
  2. 创建新的桶数组： 根据新的容量创建一个新的桶数组。
  3. 重新哈希所有的键值对： 对旧桶数组中的所有键值对重新计算哈希值，并将它们放入新的桶数组中。这一步是必要的，因为哈希值是基于数组长度计算的，数组长度改变后，哈希值也需要重新计算。

代码 Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.HashMap;
import java.util.Map;

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

        // 插入一些键值对
        map.put(1, "one");
        map.put(2, "two");
        map.put(3, "three");
        // 触发扩容
        map.put(4, "four");

        // 打印扩容后的HashMap
        System.out.println(map);
    }
}

在上述代码中，当插入第四个键值对时，HashMap的大小超过了4 * 0.75 = 3，因此会触发扩容，容量从 4 增加到 8。

扩容的具体实现

在 Java 的HashMap实现中，扩容的具体代码在resize方法中。以下是resize方法的简化版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void resize() {
    // 计算新的容量
    int newCapacity = oldCapacity * 2;

    // 创建新的桶数组
    Node<K,V>[] newTable = (Node<K,V>[])new Node[newCapacity];

    // 重新哈希所有的键值对
    for (Node<K,V> node : oldTable) {
        while (node != null) {
            Node<K,V> next = node.next;
            int hash = node.hash % newCapacity;
            node.next = newTable[hash];
            newTable[hash] = node;
            node = next;
        }
    }

    // 替换旧的桶数组
    table = newTable;
}

注意事项

性能影响：扩容是一个相对昂贵的操作，因为它需要重新哈希并移动所有现有的键值对。因此，在设计HashMap时，应尽量选择合适的初始容量和负载因子，以减少扩容次数。

线程安全：默认的HashMap是非线程安全的。如果在多线程环境中使用HashMap，需要使用Collections.synchronizedMap或使用ConcurrentHashMap。

内存消耗：扩容会临时占用更多的内存，因为需要同时维护旧的和新的桶数组。因此，在内存受限的环境中需要谨慎使用。

wechat
天生我才必有用