Alt text
为什么数组要从 0 开始编号，而不是从 1 开始？


一、什么是数组

数组 (Array) 是一种线性表数据结构，它用一组连续的内存空间，来存储一组相同类型的数据

上面这句话中说到了数组的两个特性，第一个是 「线性表」，第二个是 「连续的内存空间」。

「线性表」指的是数据排成一条线一样的数据结构，且上面的数据最多只有前和后两个方向，除了数组，链表、队列、栈 等都是线性表结构。
Alt text
与线性表相对应的是非线性表结构，也就是结构里的数据之间不只有简单的前后关系，如图、二叉树、堆等。
Alt text

「连续的内存空间和相同类型的数据」指的是数组中的数据在内存中的存储是连续的，因为这个特性所以数组能够实现「随机访问」，但也因此数组的插入删除等操作变得低效。


二、数组是如何实现随机访问的

拿一个长度为 10 的 int 类型数组 int a[] 举例，在计算机中，计算机会给 a 数组 分配一块连续的内存空间 (如下图)，其中，计算机会给每个内存单元分配一个地址，需要访问到数组中的元素的时候，计算机会通过「寻址公式」来计算出数据存储的内存地址，再通过地址来访问内存中的数据。

寻址公式：a[i]_address = base_address + i * data_type_size

其中，base_address 为数组内存块的首地址，data_type_size 为数组的数据类型长度，如 int 的数据类型长度为 4 。

Alt text


三、低效的插入和删除操作

数组为了保持内存的连续性，因此它的插入和删除操作变得十分低效。

假设有一个长度为 n 的数组，我们要在第 k 位中插入一个数据，为了保持内存的连续性，就必须将第 k 为后的 k-n 个数据往后移动一位。

如果在数组的末尾插入元素，数据无需移动，最好情况时间复杂度为 O(1)，若在数组首位插入元素，则所有元素都必须往后移动一位，最坏情况时间复杂度为 O(n)，由于每个位置插入元素的概率是一样的，因此平均时间时间复杂度为 (1+2+…+n)/n = O(n) 。

而数组的删除操作与插入操作类似，删除数组末尾元素最好时间复杂度为 O(1)，删除数组的首元素最坏时间复杂度为 O(n)，平均时间复杂度也为 O(n)。

实际上，在某些场景中，我们并不需要一定追求数据的连续性。

例如删除操作，假如数组 a[10] 中存储了 a~h 一共 8 个元素，我们要依次删除 a、b、c 三个元素，为了避免 d~h 这几个数据被搬运三次，我们可以先记录下已经删除的数据，每次删除数据并不是真正地搬移数据，只是记录数据已经被删除，当数组中没有更多空间存储数据时，如果我们将这三次删除操作集中在一起执行，触发一次真正的删除操作，这样删除的效率就会高效很多。这也是 JVM 中的 标记清除垃圾回收算法 的核心思想。


四、警惕数组越界

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;
}

这段代码的运行结果不是打印三次 hello world ，而是打印无限次 hello world。因为数组大小为 3 ，而由于 for 循环中的条件为 i <= 3 ，当 i = 3 时，数组 a[3] 访问越界。

在 C 语言中，只要不是访问受限的内存，所有的内存空间都是可以访问的，根据前面的寻址公式，a[3] 也会被定位到某块不属于数组的内存地址上，而这个地址刚好是存储变量 i 的内存地址，因此 a[3]=0 就相当于 i = 0，计算机访问到了数组首元素的地址，导致了代码的无限循环。

因为访问数组本身就是在访问一段连续的内存，只要通过寻址公式的得到的内存地址是可用的，程序就不会报错误，所以经常会出现一些奇怪的逻辑错误问题。数组越界在 C 语言中是一种未决行为，编译器也没有规定在数组越界时该如何处理。但也并非所有语言都会把数组越界检查交给程序员来做，像 java 就会做越界检查并抛出错误。


五、容器能否完全替代数组？

很多语言为数组类型提供了容器，用 java 的 ArrayList 举例，它封装了很多数组的操作细节，如插入删除及搬运数据等；还有就是支持动态扩容，每当存储空间不够的时候，都会自动将空间扩容到 1.5 倍大小。而数组在定义前就要先指定好大小，为它分配一段连续的内存空间，而当数组的内存空间不够时，就需要申请一块更大的内存空间，再将原来的数据复制过去。这样比较起来，使用容器效率比用数组要高得多。

数组比较适用的场景：

  • 若数据大小已知，且涉及的数据操作比较简单，可以用数组。
  • 对于平常的业务开发，使用容器便足够，虽然只损耗一点点性能。对于非常底层的开发，性能的优化需要做到极致，这时数组会优于容器。
  • 表示多维数组时，数组往往比容器更加客观。
  • 若特别关注性能，可以选用数组


思考：

为什么数组从 0 开始编号？

解答：

如果用 a 来表示数组的首地址，a[0] 就是偏移为 0 的位置，a[k]表示偏移 k 个 data_type_size 的位置，a[k]的地址计算就是这样的

a[k]_address = base_address + k * data_type_size

而如果从 1 开始计数，则为：

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

从 1 开始计数多了一次减法操作，对 CPU 来说就多了一次减法指令，数组作为最基础的数据结构，为了使效率优化达到极致，所以选择从 0 开始编号 (也有一定的历史因素)


二维数组的寻址公式是怎么样的？

解答：

对于一个 m*n 的二维数组，a[i][j]的寻址公式为：
address = base_address + ( i*n + j ) * data_type_size