Java 如何动态增加二维数组的大小

How to dynamically increase size of a 2D array

提问by

I already know how to make a fixed array, if I know how many elements I have. For instance, for 7 elements I do something like int array[2][4].

如果我知道我有多少个元素，我已经知道如何制作固定数组。例如，对于 7 个元素，我执行类似 int array[2][4] 的操作。

But what if I have 0 elements at start(which means the array will be empty at start) and want to increase the array size as the program runs?

但是如果我在开始时有 0 个元素（这意味着数组在开始时将为空）并且想要在程序运行时增加数组大小呢？

Basicly, how to add a new row or column?

基本上，如何添加新行或新列？

采纳答案by Ted Hopp

Note that new int[2][4]is an array of int[]; the int[]arrays in the int[][]array are all initially the same length, but there's no requirement that they remain the same length. Any element of the int[][]array can be reassigned an int[]with a different length without affecting the other elements at all. The concept of "rows" and "columns" is a higher-level idea that is not supported by Java arrays.

请注意，这new int[2][4]是一个数组int[]；所述int[]的以阵列int[][]排列都是最初相同的长度，但没有要求，即它们保持相同的长度。int[][]数组的任何元素都可以重新分配int[]不同的长度，而不会影响其他元素。“行”和“列”的概念是 Java 数组不支持的更高级别的想法。

Using an ArrayListas other answers suggest isn't going to change this. Furthermore, Depending on how you use ArrayList, you may end up with considerable overhead due to autoboxing of intvalues as Integerobjects.

使用ArrayList其他答案建议不会改变这一点。此外，根据您的使用方式ArrayList，由于将int值自动装箱为Integer对象，您最终可能会产生相当大的开销。

If you want to preserve the rectangular shape of your data, I suggest that you define a Matrixclass that keeps all the dimensions consistent. (Or, perhaps better, linearizes the two-dimensional array into a one-dimensional array and does the appropriate subscripting calculations using internally stored row and column sizes. Or, perhaps best, use a well-written matrix library such as JAMAor a primitive collections library like Trove.)

如果您想保留数据的矩形形状，我建议您定义一个Matrix使所有维度保持一致的类。（或者，也许更好的是，将二维数组线性化为一维数组，并使用内部存储的行和列大小进行适当的下标计算。或者，也许最好使用编写良好的矩阵库，例如JAMA或原语收藏库，如Trove。）

EDITHere's the start of a simple matrix class that uses a linear storage scheme internally and allows matrix resizing. The data are stored in row-major orderand indexing is based at 0.

编辑这是一个简单的矩阵类的开始，它在内部使用线性存储方案并允许调整矩阵大小。数据按行优先顺序存储，索引从 0 开始。

public class IntMatrix {
    private int rows;
    private int cols;
    private int[] data;

    /**
     * Allocate a matrix with the indicated initial dimensions.
     * @param cols The column (horizontal or x) dimension for the matrix
     * @param rows The row (vertical or y) dimension for the matrix
     */
    public IntMatrix(int cols, int rows) {
        this.rows = rows;
        this.cols = cols;
        data = new int[cols * rows];
    }

    /**
     * Calculates the index of the indicated row and column for
     * a matrix with the indicated width. This uses row-major ordering
     * of the matrix elements.
     * <p>
     * Note that this is a static method so that it can be used independent
     * of any particular data instance.
     * @param col The column index of the desired element
     * @param row The row index of the desired element
     * @param width The width of the matrix
     */
    private static int getIndex(int col, int row, int width) {
        return row * width + col;
    }

    public int get(int col, int row) {
        return data[getIndex(col, row, cols)];
    }

    public void set(int col, int row, int value) {
        data[getIndex(col, row, cols)] = value;
    }

    /**
     * Resizes the matrix. The values in the current matrix are placed
     * at the top-left corner of the new matrix. In each dimension, if
     * the new size is smaller than the current size, the data are
     * truncated; if the new size is larger, the remainder of the values
     * are set to 0.
     * @param cols The new column (horizontal) dimension for the matrix
     * @param rows The new row (vertical) dimension for the matrix
     */
    public void resize(int cols, int rows) {
        int [] newData = new int[cols * rows];
        int colsToCopy = Math.min(cols, this.cols);
        int rowsToCopy = Math.min(rows, this.rows);
        for (int i = 0; i < rowsToCopy; ++i) {
            int oldRowStart = getIndex(0, i, this.cols);
            int newRowStart = getIndex(0, i, cols);
            System.arraycopy(data, oldRowStart, newData, newRowStart,
                colsToCopy
            );
        }
        data = newData;
    }

    . . .
}

回答by Peter Lawrey

Create a new array which is bigger, copy the existing elements and add the element you want to add. You can use something like ArrayList but this is expensive and will use about 4x the memory. I would consider using TDoubleArrayListif you don't want to resize the array yourself.

创建一个更大的新数组，复制现有元素并添加要添加的元素。您可以使用 ArrayList 之类的东西，但这很昂贵，并且会使用大约 4 倍的内存。TDoubleArrayList如果您不想自己调整数组大小，我会考虑使用。

回答by kjhf

ArrayListdocumentation, and Examples. Enjoy!

ArrayList文档和示例。享受！

Specifically:

具体来说：

ArrayList<Integer> list = new ArrayList<Integer>();
list.add(1); // Add 1 to the list.

回答by Raffaele Rossi

Java arrays can be dynamically created but cannot dynamically extended. You may want to look at Vectoror ArrayListas other suggested.

Java 数组可以动态创建，但不能动态扩展。您可能希望按照其他建议查看Vector或ArrayList。

However, bear in mind that in your example you've created a matrix which is a slightly different thing.

但是，请记住，在您的示例中，您创建了一个稍微不同的矩阵。

回答by Ted Hopp

Here's whyresizing isn't possible. Whether you have 1 or 20 dimensions, every dimension of the array is allocated as a contiguous row of data somewhere, and the storage space immediately afterany such sequence is fair game for other variables and data to use. For example, an ary = new int[4] might be represented in memory like so:

这就是无法调整大小的原因。无论您有 1 维还是 20 维，数组的每个维都被分配为某处的连续数据行，并且紧接在任何此类序列之后的存储空间对于其他变量和数据使用来说都是公平的游戏。例如， ary = new int[4] 可能在内存中表示如下：

| ary[0] | ary[1] | ary[2] | ary[3] | otherNearbyData1 | otherData2 | ...

Because of the possibility of other variables immediately after the array data, you have to allocate a new array with the desired size and copy all the elements from the old array to the new one. One strategy is to double the allocation size every time you reach 100% capacity to obtain constant amortized time complexity. This is more or less what ArrayList does, but as Peter Lawrey noted this wastes a TON of space.

由于数组数据之后可能有其他变量，因此您必须分配一个具有所需大小的新数组，并将旧数组中的所有元素复制到新数组中。一种策略是每次达到 100% 的容量时将分配大小增加一倍，以获得恒定的摊销时间复杂度。这或多或少是 ArrayList 所做的，但正如 Peter Lawrey 指出的那样，这浪费了大量空间。

One alternative depending on your needs might be a LinkedList, in which every element of data is separately allocated and contains a pointer to the next/previous element. Despite being perfectly compact (no wasted space) and able to grow to any size, linked lists have two major disadvantages:

根据您的需要，另一种选择可能是 LinkedList，其中数据的每个元素都单独分配并包含指向下一个/上一个元素的指针。尽管非常紧凑（没有浪费空间）并且能够增长到任何大小，但链表有两个主要缺点：

• no random access (you can only traverse from one element to the next/previous one).
• terribly inefficient time-wise -- leaping across the address space just to get to each next element totally knocks the wind out of CPU caches.

• 没有随机访问（您只能从一个元素遍历到下一个/上一个元素）。
• 非常低效的时间 - 跨越地址空间只是为了到达每个下一个元素，完全将 CPU 缓存中的风吹走。

Edit:On second thought...even though 2D linked lists are possible, the fact that you need multiple dimensions probablymeans sequential traversal isn't enough for you. My bad.

编辑：再想一想......即使二维链表是可能的，你需要多个维度的事实可能意味着顺序遍历对你来说还不够。我的错。

回答by Ashot Karakhanyan

Of course you can use Collections(ArrayList for example), but if you want to use 2D Matrix, you can create rows with different size "on the fly". For example the following example create "triangle" matrix :

当然，您可以使用 Collections（例如 ArrayList），但是如果您想使用 2D 矩阵，您可以“即时”创建不同大小的行。例如以下示例创建“三角形”矩阵：

int[][] matrix = new int[3][];
int count = 0;
for (int i = 0; i < 3; i++) {
    matrix[i] = new int[i];
    for (int j = 0; j < i; j++) {
        matrix[i][j] = ++count;
    }
}