【数据结构与算法】之数组详解
【数据结构与算法】之数组详解
数组是数据结构中最基础的概念之一，它在编程中被广泛应用。理解数组的工作原理、操作方式以及底层实现，对于我们构建更复杂的数据结构和算法至关重要。本文将从多个角度深入剖析数组，并以Java语言示例进行讲解，帮助你建立对数组的深刻理解。
一、什么是数组？
数组是一种线性数据结构，用于存储相同数据类型的元素序列。我们可以把数组想象成一排连续的储物柜，每个柜子都有一个唯一的编号（索引），用于存放物品。
书面解释：数组是由一组元素（值或变量）组成的数据结构，每个元素有至少一个索引或键来标识
二、数组的特点
- 元素类型相同: 数组中所有元素必须是相同数据类型，例如int、double、String等。
- 内存空间连续: 数组的所有元素在内存中是连续存储的，这使得访问元素非常高效。
- 索引访问: 每个元素都有一个唯一的索引，从0开始，可以通过索引快速访问元素。
- 固定大小: 数组一旦创建，其大小就固定了，不能动态扩展。
三、数组的底层实现
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);六、数组的常见应用
- 存储数据: 存储一组相关的数据，例如学生成绩、商品价格等。
- 实现其他数据结构: 作为其他数据结构的底层实现，例如栈、队列等。
- 算法: 很多算法都依赖于数组，例如排序算法、查找算法等。
七、数组的局限性
- 插入和删除元素效率低: 在数组中间插入或删除元素需要移动后续元素，效率较低。
- 大小固定: 数组的大小在创建时就固定了，不能动态调整。
八、动态数组实现
为了克服数组大小固定的限制，我们可以实现动态数组，即在需要时自动扩容的数组。以下是用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();
}
}九、数组操作的时间复杂度
操作 | 时间复杂度 | 说明 |
|---|---|---|
访问元素 | O(1) | 通过索引直接访问，时间复杂度为常数级。 |
修改元素 | O(1) | 通过索引直接修改，时间复杂度为常数级。 |
在末尾添加元素 | O(1) | 在数组末尾添加元素，时间复杂度为常数级。 |
在中间插入元素 | O(n) | 需要移动后续元素，时间复杂度为线性级，n为数组长度。 |
删除元素 | O(n) | 需要移动后续元素，时间复杂度为线性级，n为数组长度。 |
数组扩容 | O(n) | 需要复制所有元素到新的数组，时间复杂度为线性级，n为数组长度。 |
十、二维数组详解
二维数组本质上是一个数组，其中每个元素又是一个数组。可以将二维数组想象成一个表格，每个元素都有对应的行索引和列索引。
// 创建一个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代码示例进行讲解，希望能帮助各位看官更好地掌握数组。下期见，谢谢~
腾讯云开发者
