数组概述

数组（Array）是一种线性数据结构，它由相同类型的元素按顺序排列组成。每个元素在数组中占据一个固定的位置，这些位置由索引（也称为下标）标识。数组的索引通常从零开始，这意味着第一个元素的索引是 $0$，第二个元素的索引是 $1$，以此类推。

数组的特点

1. 固定大小：数组在创建时需要指定大小，一旦确定，数组的大小就不能更改。这意味着在使用数组时，必须提前确定需要存储的最大元素数量。
2. 相同类型元素： 数组中的所有元素必须是相同类型的。这种约束有助于数组在内存中进行高效的存储和访问。在大部分语言中。
3. 随机访问： 由于数组是按顺序存储的，每个元素的位置（索引）都是固定的，因此可以通过索引直接访问任意元素。这种特性称为随机访问，它使数组的读取操作非常高效，时间复杂度为 $O(1)$。

提示

其中第二条并不绝对，只是大部分情况下是这样的。如 JavaScript 中的数组就可以存放多种类型的数据。而在 Java 中，如果数组定义成 Object[] 也是可以存放多种类型的。如果定义成了 Object[] 数组中存放的元素将不是某个数据的具体的值，而是引用。后文中会进行详细讲解。

但是严格来说 Object[] 数组的类型也是相同的，数组中的元素存储的是其具体值的一个引用。

数组的使用

以 Java 为例，使用以下方式定义一个数组

public static void main(String[] args) {
    // 指定数组长度，先定义后初始化
    String[] strArr = new String[10];
    strArr[0] = "a";
    // ...

    // 不指定数组长度，定义并初始化，数组长度为初始化个数
    int[] nums1 = {1, 2, 3, 4, 5};
    
    // 数组中存放多种类型
    Object[] objs = new Object[10];
    objs[0] = "abc";
    objs[1] = 2;
    objs[2] = 3.14;
    objs[3] = true;
}

java

数组通过下标访问，下标从 $0$ 开始。如果访问的下标超过数组定义的长度，会报下标越界 (java.lang.ArrayIndexOutOfBoundsException) 的错误。

nums1[0] = 10;
int a = nums1[1];

可以通过 Arrays.stream() 将数组转为流 (java.util.stream.Stream)，这样就可以使用流式 API 处理数组了。

public static void main(String[] args) {
    Object[] objs = new Object[10];
    objs[0] = "abc";
    objs[1] = 2;
    objs[2] = 3.14;
    objs[3] = true;
    Arrays.stream(objs)
            .filter(Objects::nonNull)
            .forEach(System.out::println);
}

java

数组的维度

数组根据维度可分为：一维数组、二维数组、三维数据、...、$n$ 维数组。其定义方式如下：

int[] nums1 = new int[10]; // 一维数组
int[][] nums2 = new int[2][3]; // 二维数组，2 × 3。即两行三列的一个矩阵。

// 下面这种方式定义也是可以的
int[][] nums2 = {
    {1, 2 , 3},
    {3, 4, 5}
};

二维数组在数学中对应矩阵的概念。如上面定义的二维数据，在数学矩阵中的表现为

$$\text{nums2} = \begin{bmatrix} 1 & 2 & 3 \\ 3 & 4 & 5 \end{bmatrix}_{2 \times 3}$$

数组的内存结构

数组在内存中占据一块连续的内存空间，这意味着数组的所有元素都在相邻的位置存储。这个特性使得数组的随机访问非常高效，因为可以通过简单的数学运算直接定位到任何一个元素的内存地址。

基本类型的数组和对象类型的数组略有区别。基本类型的数组其元素为数据的值，而对象类型呢的数组其元素为到具体对象的指针，也即内存地址。

对于基本类型的数组，获取元素只需要经过一次访存操作（通过 变址寻址 进行一次访存）。对于一个长度为 $n$ 的整数数组 int array[n]，如果数组的起始地址是 base_address，那么索引为 $i$ 的元素的地址可以通过以下公式计算得到：

$$\text{element\_address} = \text{base\_address} + i \times \text{type\_size}$$

其中 type_size 为数组元素类型的长度。

以上图为例，假设数组的起始内存地址为 1000，元素类型为 int 类型，占 4 个字节。要访问索引为 3 的元素，其地址应为 $1000 + 3 \times 4 = 1012$。

对于对象类型的数组，则需要通过两次或两次以上访存才能获取到数据的值。一次变址寻址，一次直接寻址；或变址寻址与间接寻址结合使用，这两种方式实际都进行了两次访存操作。如上图。

汇编语言示例

MOV BX, [arrayBase] ; 将数组基地址加载到BX寄存器
MOV SI, [index]     ; 将索引加载到SI寄存器
MOV AX, [BX + SI]   ; 访问数组元素，将其值加载到AX寄存器

armasm

为什么说要两次或两次以上？因为如果是对象类型，可能对象中的某个字段才是我们要取的数据，这样就还需要进行更多次数的访存操作。

Java 中数组的内存结构

[J object internals:
OFF  SZ   TYPE DESCRIPTION               VALUE
  0   8        (object header: mark)     0x0000000000000001 (non-biasable; age: 0)
  8   4        (object header: class)    0x00002a80
 12   4        (array length)            3
 16  24   long [J.<elements>             N/A
Instance size: 40 bytes
Space losses: 0 bytes internal + 0 bytes external = 0 bytes total

text

数组的内存空间并不是绝对连续的

数组通常在进程的逻辑内存空间上是连续的，但是在实际的物理内存空间中一定是连续的吗？

数组在进程的逻辑内存空间上通常是连续的，但在实际的物理内存空间中不一定是连续的。这涉及到操作系统如何管理内存和虚拟内存的概念。如下图，数组的内存空间正好被分配在了两页中，这部分内存空间在逻辑上是连续的，但是实际上对应的物理内存是不连续的。