动态数组的扩容和缩容

1. 引言

在编程中，数组是最常见的数据结构之一。它允许我们高效地访问和存储元素。但是，传统的静态数组在创建时就需要确定大小，一旦数组的大小被确定，就不能动态调整。当数组的元素数量发生变化时，静态数组的空间可能会不够用，或者会浪费空间。为了应对这种情况，我们引入了“动态数组”概念，它允许在运行时动态地调整数组的大小。

动态数组的核心特性是：它的容量可以根据需要自动扩展或缩减。扩容是指当数组满了时，自动增加其容量；缩容则是当数组中的元素数减少时，自动减少数组的容量。

在本节内容中，我们将详细讨论动态数组的扩容和缩容机制，并通过 Java 代码来演示这一过程。

2. 动态数组的扩容和缩容机制

2.1 扩容

当我们向一个动态数组中添加元素时，若数组已经满了，就需要对数组进行扩容。扩容的常见策略是：将当前数组的容量扩大为原来的两倍。这样可以确保数组能够容纳更多的元素，同时避免频繁地扩容操作带来的性能问题。

扩容时，我们通常需要进行以下几个步骤：

创建一个新的更大容量的数组。
将原数组中的元素复制到新数组中。
释放旧数组的内存并将引用指向新数组。

扩容的时间复杂度通常是 O(n)，因为我们需要遍历并复制所有的元素。

2.2 缩容

与扩容相反，缩容是在数组中存储的元素数量大大减少时，动态地减小数组的容量。缩容的常见策略是：当数组的元素数量低于容量的四分之一时，将数组的容量缩小为原来的二分之一。缩容的目的是节省内存空间，避免数组占用过多的无用空间。

缩容时的操作步骤与扩容类似：

创建一个新的更小容量的数组。
将原数组中的元素复制到新数组中。
释放旧数组的内存并将引用指向新数组。

缩容时的时间复杂度也是 O(n)，因为同样需要遍历并复制元素。

2.3 扩容和缩容的平衡

在动态数组的设计中，扩容和缩容的平衡非常重要。如果扩容和缩容的策略设置不当，可能会导致频繁的内存复制操作，影响性能。常见的做法是，扩容时将容量增大一倍，而缩容时将容量减少一半。这种平衡方式在大多数情况下能够有效地减少内存复制的次数，并在需要时动态地调整数组大小。

3. 动态数组的实现

3.1 自定义动态数组类

接下来，我们将通过代码实现一个简单的动态数组，演示其扩容和缩容的过程。

代码示例：

// 自定义动态数组的实现
public class DynamicArray<T> {
    // 存储数组元素的容器
    private Object[] elements;
    // 数组中实际存储的元素数量
    private int size;
    // 数组的默认容量
    private static final int DEFAULT_CAPACITY = 10;
    // 扩容倍数
    private static final int EXPANSION_FACTOR = 2;
    // 缩容的下限比例
    private static final double SHRINK_THRESHOLD = 0.25;

    // 构造方法，初始化数组
    public DynamicArray() {
        elements = new Object[DEFAULT_CAPACITY];
        size = 0;
    }

    // 获取数组的大小
    public int size() {
        return size;
    }

    // 向数组末尾添加一个元素
    public void add(T element) {
        // 如果数组已满，则扩容
        if (size == elements.length) {
            expand();
        }
        elements[size++] = element;  // 将元素添加到数组末尾
    }

    // 获取指定位置的元素
    @SuppressWarnings("unchecked")
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引超出范围");
        }
        return (T) elements[index];
    }

    // 删除指定位置的元素
    public void remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引超出范围");
        }
        // 将元素后移覆盖删除的位置
        for (int i = index; i < size - 1; i++) {
            elements[i] = elements[i + 1];
        }
        elements[--size] = null;  // 删除最后一个元素并更新大小
        // 如果数组的元素数量过少，进行缩容
        if (size < elements.length * SHRINK_THRESHOLD) {
            shrink();
        }
    }

    // 扩容方法
    private void expand() {
        int newCapacity = elements.length * EXPANSION_FACTOR;  // 扩容为原来容量的2倍
        Object[] newElements = new Object[newCapacity];
        System.arraycopy(elements, 0, newElements, 0, size);  // 复制旧数组到新数组
        elements = newElements;  // 更新数组引用
    }

    // 缩容方法
    private void shrink() {
        int newCapacity = elements.length / EXPANSION_FACTOR;  // 缩容为原来容量的一半
        Object[] newElements = new Object[newCapacity];
        System.arraycopy(elements, 0, newElements, 0, size);  // 复制元素到新数组
        elements = newElements;  // 更新数组引用
    }
}

3.2 代码解读

元素存储：我们使用一个数组 elements 来存储动态数组中的元素，同时用 size 记录数组中实际存储的元素数量。
扩容机制：当数组满时，我们调用 expand() 方法。扩容时，我们创建一个新的数组，其容量是原数组的两倍，然后将原数组中的元素复制到新数组中。
缩容机制：当数组中的元素数量少于容量的四分之一时，我们调用 shrink() 方法。缩容时，我们将容量减半，并将现有元素复制到新数组中。
添加元素：我们在 add() 方法中实现了元素的添加，如果数组满了就扩容。
删除元素：remove() 方法删除指定位置的元素，并在删除后检查是否需要缩容。

4. 使用示例

接下来，我们通过一个简单的使用示例来测试动态数组的扩容和缩容功能。

示例代码：

public class Main {
    public static void main(String[] args) {
        // 创建一个动态数组对象
        DynamicArray<Integer> dynamicArray = new DynamicArray<>();
        
        // 向数组中添加元素
        for (int i = 0; i < 15; i++) {
            dynamicArray.add(i);  // 添加元素 0 到 14
            System.out.println("添加元素: " + i + ", 当前数组大小: " + dynamicArray.size());
        }

        // 删除数组中的部分元素
        for (int i = 0; i < 5; i++) {
            dynamicArray.remove(0);  // 删除索引为 0 的元素
            System.out.println("删除元素, 当前数组大小: " + dynamicArray.size());
        }
    }
}

4.1 代码解释

我们创建了一个 DynamicArray<Integer> 对象，并依次向数组中添加了15个整数。可以观察到，随着元素的添加，数组会进行扩容，容量不断增大。
然后我们删除了前五个元素，观察到数组的大小逐渐减少。当数组中元素数量较少时，数组会进行缩容，减少不必要的内存占用。

5. 总结

今天我们学习了动态数组的扩容和缩容机制。通过动态数组，我们能够根据需求自动调整数组的大小，确保在存储更多元素时能够提供足够的空间，在元素数量减少时节省内存资源。扩容和缩容的操作虽然需要复制数组中的元素，但它们能够有效地保证程序在运行时的内存管理。希望通过本节内容，大家能够理解如何实现动态数组，并能够在实际编程中灵活运用这一技巧。

去1:1私密咨询