Java数组扩容原理

一、数组扩容的概念

在Java中，数组是一种非常常用的数据结构，它可以存储同一类型的多个元素，但是在实际的应用场景中，我们可能会遇到如下问题：

1. 数组长度不够，无法存储所有的元素；

2. 数组长度过长，导致内存的浪费。

针对这些问题，我们需要对数组进行扩容操作，扩容的本质就是新建一个更大的数组，并将原数组中的元素拷贝到新数组中。

二、数组扩容的实现

在Java中，数组扩容的实现通过Arrays.copyOf方法实现，该方法的源码如下：

public static  T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

private static native Object copyOf(Object original, int newLength, Class newType);

  

从源码可以看出，该方法可以复制任意类型的数组，需要传入两个参数：

1. 原数组；

2. 新数组长度。

该方法返回值为复制后的新数组。

在实际应用中，通常会将原数组的长度翻倍作为新数组的长度，这样可以提高扩容效率。

三、为什么数组长度翻倍扩容？

我们知道，在Java中，数组是一段连续的内存空间，如果无法找到足够的连续内存空间，就无法完成数组的申请。

因此，在扩容数组时，需要重新申请一块连续的内存空间，并将原数组元素拷贝到新申请的内存空间中。

那么问题来了，为什么要将数组长度翻倍扩容？

我们知道，在内存空间中，相邻的内存单元之间有着一定的关联性，相邻的内存单元通常在物理存储空间上也是连续的。

如果原数组长度为n，则其已经占用了n个连续的内存单元，而如果需要将其扩容至2n个元素，那么新数组需要占用的内存单元至少是2n个。

因此，为了保证新数组占用连续的内存单元，新数组的长度需要是原数组长度的两倍。

四、数组扩容的时间复杂度

在Java中，数组扩容的时间复杂度是O(n)，其中n为数组长度。因为数组扩容需要重新创建新数组，并将原数组中的元素拷贝到新数组中，这个过程的时间复杂度是O(n)。

在实际应用中，可以通过设置初始容量来减少数组扩容的次数，从而提高效率。

五、完整代码示例

import java.util.Arrays;

public class ArrayResizeDemo {

    public static void main(String[] args) {
        int[] array = new int[10];

        // 初始化数组
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
        }

        // 扩容数组
        array = Arrays.copyOf(array, array.length * 2);

        // 输出扩容后的数组
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }
}

该示例代码中，首先初始化一个长度为10的数组，然后将其扩容至20，最终输出扩容后的数组。

从代码中可以看出，数组扩容的本质就是创建一个新的更大的数组，并将原数组的元素拷贝到新数组中。

六、小结

本篇文章主要介绍了Java数组的扩容原理，分别介绍了数组扩容的概念、实现、为什么数组长度翻倍扩容、数组扩容的时间复杂度以及完整的代码示例。

在实际应用中，需要注意数组的扩容次数，通过设置初始容量可以减少数组扩容的次数，从而提高效率。