深入理解 Java 集合扩容机制：从原理到实践

深入理解 Java 集合扩容机制：从原理到实践

在 Java 中，集合类如 ArrayList、HashMap 等在执行增删操作时，常常会遇到需要动态扩容的情况。理解 Java 集合的扩容机制，对于优化性能、避免内存浪费以及避免不必要的性能开销非常重要。

我们将从以下几个方面深入探讨 Java 集合扩容的原理与实践：

1. 扩容的背景与目的
2. ArrayList 扩容机制
3. HashMap 扩容机制
4. 优化扩容策略
5. 实际示例与性能分析

1. 扩容的背景与目的

在 Java 中，大多数集合类（如 ArrayList、HashMap）都采用了动态扩容策略。当集合容量达到一定阈值时，它会通过扩容来保证能继续存储数据。

扩容的目的：

• 避免频繁的内存分配：动态调整容量，以适应不同的使用场景。
• 提升性能：通过减少内存分配次数，避免了在每次插入数据时都重新分配内存。
• 内存利用：合理地控制集合的容量，避免内存浪费。

2. ArrayList 扩容机制

ArrayList 是 Java 中最常用的动态数组实现。当元素的数量超过当前容量时，ArrayList 会自动扩容。具体的扩容规则和过程如下：

ArrayList 的底层实现

• ArrayList 使用一个数组来存储元素，初始化时，ArrayList 会分配一个默认的数组容量（通常为 10）。
• 每次向 ArrayList 添加元素时，如果当前数组已满，ArrayList 会自动进行扩容。

扩容规则

• 默认扩容倍数：当 ArrayList 的容量不足时，它会将容量扩大为原容量的 1.5 倍（即容量的 50%）。
• 扩容过程：
  1. 创建一个新的更大的数组，大小为原数组的 1.5 倍。
  2. 将旧数组中的所有元素复制到新数组中。
  3. 释放原数组的引用。

扩容的源码分析

public class ArrayList<E> extends AbstractList<E> implements List<E> {    private Object[] elementData; // 存储数据的数组    private int size; // 当前 ArrayList 中元素的个数    private static final int DEFAULT_CAPACITY = 10;    public ArrayList() {        this.elementData = new Object[DEFAULT_CAPACITY]; // 默认容量为 10    }    public void add(E e) {        ensureCapacityInternal(size + 1); // 保证容量足够        elementData[size++] = e;    }    private void ensureCapacityInternal(int minCapacity) {        if (elementData.length < minCapacity) {            grow(minCapacity);        }    }    private void grow(int minCapacity) {        int oldCapacity = elementData.length;        int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容 50%        if (newCapacity - minCapacity < 0) {            newCapacity = minCapacity;        }        elementData = Arrays.copyOf(elementData, newCapacity);    }}php911 Bytes© 菜鸟-创作你的创作

解释：

• ensureCapacityInternal() 方法用来检查是否需要扩容，如果需要扩容，则调用 grow() 方法。
• grow() 方法将当前数组的容量增加 50%（即原容量的 1.5 倍）。

扩容过程的性能影响

• 扩容是一个 O(n) 的操作，因为需要将所有元素从旧数组复制到新数组。因此，频繁扩容会影响 ArrayList 的性能，尤其是当数据量非常大时。

3. HashMap 扩容机制

HashMap 是基于哈希表的集合，它的扩容机制与 ArrayList 类似，但有所不同。HashMap 中的扩容与 负载因子（load factor）和 容量（capacity）密切相关。

HashMap 的底层实现

HashMap 通过数组存储键值对，数组中的每个元素是一个链表或树结构（在高冲突情况下）。当 负载因子 达到一定阈值时，HashMap 会进行扩容。

扩容规则

• 初始容量：默认初始容量为 16。
• 负载因子：默认负载因子为 0.75，即当哈希表中已填充 75% 时，HashMap 会进行扩容。
• 扩容倍数：HashMap 扩容时，会将容量翻倍。

扩容过程

1. 计算负载因子：当 size > capacity * load factor 时，触发扩容。
2. 创建新的数组：新数组的容量是原容量的两倍。
3. 重新散列：遍历原数组，将元素重新分配到新的数组中（根据哈希值进行重新计算）。

扩容的源码分析

public class HashMap<K, V> {    private transient Entry<K, V>[] table; // 哈希表数组    private int size = 0; // 元素数量    private int threshold; // 扩容阈值    private final float loadFactor; // 负载因子    public HashMap(int initialCapacity, float loadFactor) {        this.loadFactor = loadFactor;        this.threshold = (int) (initialCapacity * loadFactor); // 计算扩容阈值    }    public void put(K key, V value) {        if (size >= threshold) {            resize();        }        // 哈希插入代码...    }    private void resize() {        int newCapacity = table.length * 2; // 容量翻倍        threshold = (int) (newCapacity * loadFactor); // 重新计算阈值        table = Arrays.copyOf(table, newCapacity); // 创建新数组        // 重新散列所有元素...    }}php738 Bytes© 菜鸟-创作你的创作

解释：

• resize() 方法在元素数量超过阈值时调用，触发容量的翻倍。
• 扩容时，threshold 会重新计算，防止容量不够。

扩容的性能影响

• 扩容时，HashMap 需要重新计算每个元素的哈希值，并将它们放入新数组中。这是一个 O(n) 的操作，因此频繁扩容会影响性能。

4. 优化扩容策略

虽然扩容是一个有效的性能优化手段，但频繁的扩容会带来不必要的性能开销。以下是一些优化扩容策略的方法：

优化 ArrayList 扩容

• 提前预估容量：在 ArrayList 初始化时，如果能够预估元素的数量，可以直接指定合适的初始容量，避免不必要的扩容。List<String> list = new ArrayList<>(100); // 提前指定容量

优化 HashMap 扩容

• 合理设置初始容量：根据应用的需求，合理设置 HashMap 的初始容量和负载因子，避免不必要的扩容。Map<String, Integer> map = new HashMap<>(100, 0.75f); // 设置初始容量和负载因子

减少扩容次数

• 批量添加元素：如果知道将要添加的元素数量，可以一次性将所有元素添加到集合中，减少多次扩容。

5. 实际示例与性能分析

ArrayList 扩容性能分析

考虑一个需要不断添加元素的应用，假设从 1 万个元素增加到 100 万个元素。若使用默认的 ArrayList 初始化容量为 10，扩容机制会频繁发生，从而影响性能。

HashMap 扩容性能分析

在 HashMap 的使用中，频繁的扩容和重新散列操作会带来额外的开销，尤其是当负载因子不合适时。可以通过调整初始容量和负载因子来减少扩容次数，提高性能。

总结

Java 集合类的扩容机制是为了在动态增长时提供更高效的内存管理和性能优化。了解不同集合类（如 ArrayList 和 HashMap）的扩容规则和实现，可以帮助我们在开发中优化性能，减少不必要的内存开销和处理时间。

优化建议：

• 提前预估并设置合适的初始容量，避免频繁扩容。
• 根据实际需求调整 HashMap 的负载因子。
• 适当批量添加元素，减少扩容操作的次数。

理解这些扩容机制，能够帮助我们在大数据量处理和高并发场景下提高程序的性能和稳定性。https://www.52runoob.com/archives/5129