数组

数组：一种线性表数据结构，用一组连续的内存空间，来存储一组具有相同类型的数据

如何实现数组随机访问

线性表特性

数据像排成一条线，每个线性表上的数据最多只有两个方向；数组、链表、队列、栈都是线性表。相对立就是非线性表，比如二叉树、堆、图等

连续的存储空间和相同的数据类型

数组的连续存储使得地址空间可以根据第几个元素和每个元素的空间大小算出地址，从而可以实现随机访问，但是随即访问也使得删除和插入变得低效，需要迁移很多数据。寻址公式：

1
a[i] = base_address + i * data_type_size

对于一个 m*n 的二维数组，寻址公式：

1
a[i][j] = base_address + (i * n + j) * data_type_size

数组的插入删除

插入

在一个长度为 n 的数组中在 k 位置插入一个元素，则需要把后面 n - k 个元素向后移一位，如果刚好是最后一个元素，则时间复杂度是 $O(1)$，如果是第一个元素则是 $O(n)$，平均时间复杂度是 $(1+2+3+…+n) / n = O(n)$。

当插入的数列本身是无序的时候，可以把插入的位置的元素直接放到数组的最后，避免大规模移动数据

删除

删除的场景类似于出入，如果数组无序，可以把最后一个元素放到要删除的位置，也可以避免大规模移动数据。

也可以利用 JVM 标记清除的思想，将元素标记为删除，当空间不足或者达到一定量时，统一做删除操作

容器和数组

数组需要提前划分好连续的地址空间大小，无法动态扩容；容器可以支持动态扩容

数组越界问题

访问超过划分的地址空间就会出现异常。但对于一些语言和编译器有可能会出现无限循环的情况。例如这段 C 语言，在有的编译器下可能出现循环访问的情况。

1
2
3
4
5
6
7
8
9
int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

C 语言中除受限内存空间所有内存可以自由访问。数组大小为 3，a[0]、a[1]、a[2]，当数组大于3时才结束循环，此时会造成访问越界，但这个地址刚好是变量 i 的地址，就会导致无限循环。这里的循环问题也是特例，这个还和编译器分配内存和字节对齐相关。

数组下标从 0 开始

数组下标为 0 时寻址公式：

1
a[i] = base_address + i * data_type_size

下标为 1 时寻址公式：

1
a[i] = base_address + (i - 1) * data_type_size

对 CPU 来说需要多做一次减法操作，在以前机器性能不高时可能有一定作用。现在来看应该作用不大。保留下来应该也有历史原因，现在有些语言数组不一定从 0 开始，甚至可以有负数，例如 python。