数据结构与算法 / 系统课时

动态数组与扩容机制

动态数组与扩容机制

动态数组看似可以不断增长,底层仍是长度固定的普通数组。本课拆解容量检查、创建新数组、复制元素和替换引用的过程,并解释尾部追加为何具有均摊 O(1)O(1) 复杂度。

学习目标

  • 区分动态数组的有效长度 size 与底层容量 capacity。
  • 掌握按比例扩容、数据复制和零容量处理。
  • 能解释单次扩容 O(n)O(n) 与连续追加均摊 O(1)O(1) 的区别。

扩容本质与触发条件

动态数组始终满足 0 <= size <= capacity。当 size < capacity 时,新元素可直接写入下标 size;当二者相等时,必须先扩容。

扩容不是修改原数组长度,而是计算新容量、创建更大的数组、复制全部有效元素,再让字段引用新数组。旧数组失去引用后由运行时回收。

动态数组扩容与复制过程

按固定小增量扩容会频繁复制。通用动态数组通常按比例增长,例如两倍或约 1.5 倍。初始容量为 0 时不能直接翻倍,否则新容量仍为 0,必须设置最小起始容量。

为什么追加是均摊 O(1)

触发扩容的单次追加需要复制当前 n 个元素,因此最坏为 O(n)O(n)。但以两倍增长为例,连续加入 n 个元素时,历史复制量近似为 1 + 2 + 4 + ...,其总和小于 2n。

因此一系列追加的总工作量仍为 O(n)O(n),平均到每次操作就是均摊 O(1)O(1)。均摊结论描述操作序列,不代表每一次追加都耗时相同。

主示例:实现可扩容整数数组

下面的 Java 17 示例支持尾部追加、指定位置插入和显式 trimToSize。扩容采用两倍策略,零容量时从默认容量 4 开始。

java
import java.util.Arrays;

public class DynamicArrayDemo {

    public static void main(String[] args) {
        DynamicIntArray array = new DynamicIntArray(2);

        array.add(10);
        array.add(20);
        array.add(30);
        array.add(40);
        array.add(50);
        array.insert(2, 25);

        System.out.println(
                "扩容后: " + array
                        + ", size=" + array.size()
                        + ", capacity=" + array.capacity()
        );

        array.trimToSize();

        System.out.println(
                "整理后: " + array
                        + ", size=" + array.size()
                        + ", capacity=" + array.capacity()
        );
    }

    static final class DynamicIntArray {
        private static final int DEFAULT_CAPACITY = 4;

        private int[] elements;
        private int size;

        DynamicIntArray(int initialCapacity) {
            if (initialCapacity < 0) {
                throw new IllegalArgumentException("初始容量不能小于 0");
            }
            elements = new int[initialCapacity];
        }

        void add(int value) {
            ensureCapacity(size + 1);
            elements[size++] = value;
        }

        void insert(int index, int value) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException("插入位置越界");
            }

            ensureCapacity(size + 1);

            // System.arraycopy 能安全处理同一数组内的重叠区间。
            System.arraycopy(
                    elements,
                    index,
                    elements,
                    index + 1,
                    size - index
            );

            elements[index] = value;
            size++;
        }

        void trimToSize() {
            if (size != elements.length) {
                elements = Arrays.copyOf(elements, size);
            }
        }

        int size() {
            return size;
        }

        int capacity() {
            return elements.length;
        }

        private void ensureCapacity(int minimum) {
            if (minimum <= elements.length) {
                return;
            }

            int oldCapacity = elements.length;
            if (oldCapacity > Integer.MAX_VALUE / 2) {
                throw new IllegalStateException("数组容量已接近整数上限");
            }

            int newCapacity = oldCapacity == 0
                    ? DEFAULT_CAPACITY
                    : oldCapacity * 2;

            if (newCapacity < minimum) {
                newCapacity = minimum;
            }

            elements = Arrays.copyOf(elements, newCapacity);
        }

        @Override
        public String toString() {
            return Arrays.toString(Arrays.copyOf(elements, size));
        }
    }
}

编译并运行:

bash
javac DynamicArrayDemo.java
java DynamicArrayDemo

预期输出:

text
扩容后: [10, 20, 25, 30, 40, 50], size=6, capacity=8
整理后: [10, 20, 25, 30, 40, 50], size=6, capacity=6

容量策略与边界

扩容前必须先判断容量,不能先写入再扩容。Arrays.copyOf 返回新数组,若不接收返回值,底层引用仍指向旧空间。

删除后不一定要自动缩容。过于积极地在添加和删除之间扩缩,会产生反复复制。工程实现常采用较低利用率阈值,或像示例一样提供显式整理方法。对象数组删除元素后还应清空失效尾部引用。

示例在翻倍前检查整数上限,用于说明容量计算必须防护;真实 JDK 集合还会考虑虚拟机允许的最大数组长度,并采用更严格的增长策略。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

动态数组与扩容机制

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通