【数据结构】之数组详解

数组是数据结构中最基础的概念之一，它在编程中被广泛应用。理解数组的工作原理、操作方式以及底层实现，对于我们构建更复杂的数据结构和算法至关重要。本文将从多个角度深入剖析数组，并以Java语言示例进行讲解，帮助你建立对数组的深刻理解。

一、什么是数组？

数组是一种线性数据结构，用于存储相同数据类型的元素序列。我们可以把数组想象成一排连续的储物柜，每个柜子都有一个唯一的编号（索引），用于存放物品。

书面解释：数组是由一组元素（值或变量）组成的数据结构，每个元素有至少一个索引或键来标识

二、数组的特点

1. 元素类型相同: 数组中所有元素必须是相同数据类型，例如int、double、String等。

2. 内存空间连续: 数组的所有元素在内存中是连续存储的，这使得访问元素非常高效。

3. 索引访问: 每个元素都有一个唯一的索引，从0开始，可以通过索引快速访问元素。

4. 固定大小: 数组一旦创建，其大小就固定了，不能动态扩展。

三、数组的底层实现

Java 中数组结构为

• 8 字节 markword

• 4 字节 class 指针（压缩 class 指针的情况）

• 4 字节 数组大小（决定了数组最大容量是 $2^{32}$）

• 数组元素 + 对齐字节（java 中所有对象大小都是 8 字节的整数倍12，不足的要用对齐字节补足）

例如

int[] array = {1, 2, 3, 4, 5};

的大小为 40 个字节，组成如下

8 + 4 + 4 + 5*4 + 4(alignment)   =  40
                         |
                    表示补全的

四、Java中创建和初始化数组

在Java中，可以使用以下语法创建数组：

// 创建一个长度为5的int数组
int[] numbers = new int[5];

// 创建一个长度为3的String数组并初始化
String[] names = {"Alice", "Bob", "Charlie"};

五、数组的基本操作

访问元素: 通过索引访问数组元素。

int firstNumber = numbers[0]; 
System.out.println("第一个元素是：" + firstNumber);

修改元素: 通过索引修改数组元素。

names[1] = "David"; 
System.out.println("第二个名字现在是：" + names[1]);

遍历数组: 使用循环结构遍历数组中的所有元素。

for (int i = 0; i < numbers.length; i++) {
  System.out.println("元素 " + i + ": " + numbers[i]);
}

获取数组长度: 使用length属性获取数组的长度。

int arrayLength = names.length;
System.out.println("数组长度：" + arrayLength);

六、数组的常见应用

1. 存储数据: 存储一组相关的数据，例如学生成绩、商品价格等。

2. 实现其他数据结构: 作为其他数据结构的底层实现，例如栈、队列等。

3. 算法: 很多算法都依赖于数组，例如排序算法、查找算法等。

七、数组的局限性

1. 插入和删除元素效率低: 在数组中间插入或删除元素需要移动后续元素，效率较低。

2. 大小固定: 数组的大小在创建时就固定了，不能动态调整。

八、动态数组实现

为了克服数组大小固定的限制，我们可以实现动态数组，即在需要时自动扩容的数组。以下是用Java实现的动态数组类：

public class DynamicArray<T> {
    private static final int DEFAULT_CAPACITY = 10; // 默认容量
    private T[] data; // 存储元素的数组
    private int size; // 当前元素数量

    // 无参构造函数，使用默认容量
    public DynamicArray() {
        this(DEFAULT_CAPACITY);
    }

    // 有参构造函数，指定容量
    public DynamicArray(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("Capacity cannot be negative: " + capacity);
        }
        data = (T[]) new Object[capacity]; // 创建指定容量的数组
        size = 0; // 初始化元素数量为0
    }

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

    // 判断数组是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 通过索引获取元素
    public T get(int index) {
        checkIndex(index); // 检查索引是否合法
        return data[index]; // 返回指定索引的元素
    }

    // 通过索引设置元素
    public void set(int index, T value) {
        checkIndex(index); // 检查索引是否合法
        data[index] = value; // 将指定索引的元素设置为新的值
    }

    // 在数组末尾添加元素
    public void add(T value) {
        if (size == data.length) { // 如果数组已满
            resize(data.length * 2); // 扩容至两倍
        }
        data[size++] = value; // 在数组末尾添加元素，并更新元素数量
    }

    // 扩容
    private void resize(int newCapacity) {
        T[] newData = (T[]) new Object[newCapacity]; // 创建新的数组
        System.arraycopy(data, 0, newData, 0, size); // 将旧数组元素复制到新数组
        data = newData; // 将新数组赋值给data
    }

    // 检查索引是否合法
    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    // 使用for循环遍历数组
    public void printAll() {
        for (int i = 0; i < size; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }

    // 使用foreach循环遍历数组
    public void forEachPrint() {
        for (T element : data) {
            if (element != null) { // 避免打印空元素
                System.out.print(element + " ");
            }
        }
        System.out.println();
    }
}

九、数组操作的时间复杂度

十、二维数组详解

二维数组本质上是一个数组，其中每个元素又是一个数组。可以将二维数组想象成一个表格，每个元素都有对应的行索引和列索引。

// 创建一个3行5列的二维数组
int[][] matrix = {
    {1, 2, 3, 4, 5},
    {3, 2, 1, 2, 1},
    {3, 4, 5, 8, 8},
};

// 遍历二维数组
for (int i = 0; i < matrix.length; i++) {
  for (int j = 0; j < matrix[i].length; j++) {
    System.out.print(matrix[i][j] + " ");
  }
  System.out.println();
}

图解如下 ： 

十一、利用局部性原理和代码解释二维数组的ij遍历为什么比ji遍历快

在实际应用中，我们通常需要遍历二维数组的所有元素。遍历方式对性能的影响很大，其中 i 行 j 列遍历（先遍历行，再遍历列）的效率通常高于 j 列 i 行遍历（先遍历列，再遍历行）。

这是因为 CPU 会将频繁访问的数据加载到缓存中，以便更快地访问。ij 遍历方式访问内存地址是连续的，更符合局部性原理，CPU 缓存命中率更高，从而提高了访问效率。（缓存的最小缓存单元是缓存行，从而解释了ij遍历方式更快）

扩展：空间局部性的概念

• cpu 读取内存（速度慢）数据后，会将其放入高速缓存（速度快）当中，如果后来的计算再用到此数据，在缓存中能读到的话，就不必读内存了

• 缓存的最小存储单位是缓存行（cache line），一般是 64 bytes，一次读的数据少了不划算啊，因此最少读 64 bytes 填满一个缓存行，因此读入某个数据时也会读取其临近的数据，这就是所谓空间局部性

以下代码演示了两种遍历方式的性能差异：

public class ArrayTraversal {
    public static void main(String[] args) {
        int[][] matrix = new int[10000][10000];
        long startTime, endTime;

        // ij 遍历
        startTime = System.nanoTime();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                matrix[i][j]++;
            }
        }
        endTime = System.nanoTime();
        System.out.println("ij遍历时间：" + (endTime - startTime) / 1000000 + "ms");

        // ji 遍历
        startTime = System.nanoTime();
        for (int j = 0; j < matrix[0].length; j++) {
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][j]++;
            }
        }
        endTime = System.nanoTime();
        System.out.println("ji遍历时间：" + (endTime - startTime) / 1000000 + "ms");
    }
}

运行结果会显示 ij 遍历的时间明显少于 ji 遍历。

@@利用局部性原理解释如下@@

外i内j：缓存一次读取一行，先命中1，然后2，然后3......这样按行命中，速度极快

外j内i：缓存也是每次读取一行，但是只命中一个，又读取新的一行，还是命中一个，按列命中，依次类推，效率极低，如果不能充分利用缓存的数据，就会造成效率低下

十二、什么是数组的越界？

数组越界是指访问数组时，索引超出了数组的有效范围。在Java中，如果访问数组时索引小于0或者大于等于数组长度，就会抛出 IndexOutOfBoundsException 异常。

int[] numbers = {1, 2, 3};

// 索引越界
int error = numbers[3]; // 抛出 ArrayIndexOutOfBoundsException

为了避免数组越界，需要在访问数组时，始终检查索引是否在有效范围内。

总结

数组是数据结构的重要组成部分，理解其原理和操作特性对于学习更复杂的数据结构和算法至关重要。本文从多个维度深入解析了数组，并结合Java代码示例进行讲解，希望能帮助各位看官更好地掌握数组。下期见，谢谢~