java - 为什么不能调整数组的大小？

Question

数组（原始数组或其他数组）无法动态调整大小的原因是什么？

我知道你可以使用ArrayList，但它背后的实现仍然是一个初始大小的数组（我认为它默认为 50），当它超过 50 时，将创建一个新数组来包含这些元素。

因此，我试图了解使其无法调整大小的数组的系统规范。

Answer 1

这是一个有效的问题，答案与计算机的实际工作方式有关。

例如，当您创建一个数组时，int[] array = new int[5]计算机会在内存中为要包含在该数组中的数据保留五个连续的空间。但是，之后内存中的空间可以立即用于存储其他信息。如果稍后要调整数组的大小，则必须将其他信息移动到其他地方才能使数组变得更大。这是我们不想处理的大量改组，因此计算机架构师不允许调整数组大小以使事情变得更简单。

Answer 2

数组实际上是一个连续的内存块。根据您将其初始化为的内容，它可以相对较小或相对较大。

例如，假设我有一个包含十个元素的数组。

int[] arr = new int[10];

JVM 的底层实现现在必须向操作系统请求 40 个连续字节以分配给程序。操作系统要求，现在您有 40 个字节，您可以使用熟悉的名称arr。

请注意，这个数组可能在它的任一侧共享空间——它附近还有其他引用或信息位，它不能只是走到自己的第十一个位置并“认领”它。

假设我们认为 10 太短了。我们需要把它放大十倍。

int arr2 = new int[100];

现在操作系统必须在内存中找到彼此相邻的 400 字节空间，考虑到对象的生命周期、垃圾收集的运行时间等等，这可能是微不足道的，也可能不是微不足道的。

调整数组大小不仅仅是将引用移动到几个内存位置 - 它是关于找到新的连续内存块来存储数据。

---

您提到ArrayList- 它的奇怪之处在于它由一个“自动”调整大小的数组支持。好吧，调整大小操作有一个问题——它很昂贵。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

这ensureCapacityInternal做了一些有趣的事情......最终调用ensureExplicitCapacity......最终调用grow：

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

本质上，每次需要调整大小时，它分配的空间等于原始后备数组的 1.5 倍。如果它相当大，这很快就会变得昂贵ArrayList- 系统必须找到越来越多的连续内存来分配，这意味着 JVM 必须找到更多的连续空间，这意味着垃圾收集花费了更多时间，最终意味着更少表现。

以上甚至不包括将数据复制回来。

Answer 3

假设您定义了一个 16 字节、一个整数和另一个整数的数组。

现在你想调整它的大小......

======================================================
|| || || || || || || || || || || || || || || || || ||   --->  (Memory)
======================================================
\________________/\____/\____/  
 ----------------  ----  ----
      Array(16)     Int  Int

上面的数组看起来很容易调整大小吗？

必须为下一个可用的空闲内存块分配一个新数组，因为程序已经为整数保留了紧随其后的块。

Answer 4

为了解决这个问题，有向量。

您应该使用向量就像动态分配内存一样。