为什么很多编程语言中数组都是从0开始编号？

首先给出答案。
因为数组中的数据是存储在连续的内存中。
如果我们从0开始编号，那么第n个数据的编号就是n-1，此时我们就可以通过如下公式来获取其位置。其中unitsize为单位数据所占用的内存大小。
$f(n) = f(0) + n * unitsize$
然而如果我们从1开始编号的话，第n个数据的编号就是n，计算公式为:
$f(n) = f(1) + (n-1) * unitsize$
可以明显看出下式比上式多进行了n-1这个计算，而数据的各种计算在计算机底层被大量应用，一点点改进都能带来巨大的性能提高，所以我们采用0作为第一个编号。

如何实现随机访问

首先给出数组的定义:

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

要理解数组，上面加黑的重点词是我们首先要攻克的难题。

线性表
线性表是数据排成一条线一样的结构。每个线性表上的数据最多只有前后两个方向，除了数组，队列、栈、链表等也是线性表结构。

线性表.jpg

与线性表对应的就是非线性表，如二叉树、堆、图等，其特点是数据并不是简单地前后关系，以树为例，A结点除了下面的C结点为相邻结点，还有左边的B结点以及右边的D结点为相邻结点。

非线性表.jpg
连续的内存空间存储相同的数据类型的数据
正是因为这个特征，数组才有随机访问的特性。相同的数据类型保证了每个元素在内存空间所占据的空间大小是一样的。而连续的内存空间则保证了我们可以通过数组中任一个元素的内存位置推算到其他元素的位置。

我们拿一个长度为10的数组为例：

数组地址示意图.jpg

如图所示，计算机给这个数组分配了地址为1000~1039内存空间，a[0]的地址为1000，而该数组中存储的是int类型的数据，每个int占用4byte，所以我们可以通过公式：
$f(n) = f(0) + n * unitsize$ 来计算任一元素的存储位置。在该数组情况下，unitsize的值为4。
还有一个很多人经常犯错的误区。

链表适合插入、删除，其时间复杂度为 $O(1)$ ，数组适合查找，时间复杂度为 $O(1)$ 。这个说法是错误的，查找的时间复杂度不是 $O(1)$ ，而是数组的随机访问的复杂度为 $O(1)$ 。

低效的插入删除

插入操作
如果我们给一个数量为n的数组插入数据，当在数组末尾插入数据的时候，有最好时间复杂度 $O(1)$ ，当在数据头部插入数据时，有最坏时间复杂度 $O(n)$ 。平均时间复杂度为 $\frac{(1 + n) * n}{n} = O(n)$
删除操作
与插入操作类似，在数组末尾删除数据的时候为最好时间复杂度 $O(1)$ ，在数组头部删除数据的时候，有最坏时间复杂度 $O(n)$ ，平均时间复杂度也为 $O(n)$ 。
但是在一些情况下我们并不要求数组中的数据具有连续性，如果我们把需要删除的数据先进行标记，然后达到一定的数量之后再进行删除，那么删除的效率就能够提高很多。

删除操作.jpg

如图所示，在达到一定数量之前，我们进行的删除操作只是进行标记，等达到数量之后再一次性删除移动数据。Jvm的标记整理垃圾回收算法就是使用了这种思想。

警惕数组的访问越界问题

首先看如下C语言代码：

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。原因是在C语言中，只要不是访问受限的内存，所有的内存地址都是能够访问的。根据我们之前的公式，a[3]也是会被定位到某个内存地址上，栈是从高位到低位的，所以i和数组的数据从高位到低位地址依次是：i，a[2]，a[1]，a[0]，那么a[3]定位的内存地址就是i所在的内存地址，所以导致代码的无限循环。
数组越界在C语言中是一种未决问题，并没有规定数组访问越界时编译器应该如何处理。因为访问数组的本质就是访问一段连续的内存地址，只要通过寻址公式得到的内存地址是可用的，数据就可能不会报任何错误。

容器能否完全替代数组

以Java为例，ArrayList将很多数组的细节封装起来，比如插入删除等。此外它还支持动态扩容，当存储空间不够的时候，就会扩容到原来的1.5倍。
但是扩容操作涉及到内存申请和数据搬移，是比较耗时的，所以我们尽量在新建数组之前确定其大小。
即使容器类有这些优点，在以下情况的时候仍然是使用数组更好：

ArrayList不能够存储基本类型数据，需要进行装箱拆箱等操作，会对性能造成一定的损耗。
如果数据大小事先直到，并且对数据的操作比较简单，可以使用数组。
表现多维数组的时候，使用数组更为直观。比如Object[][] array；使用容器类需要这样定义：ArrayList<ArrayList> array。

总结：如果是做业务处理，那么使用容器类就可以，但是如果涉及到对性能特别在意的工作，比如网络框架等，还是数组更优于容器。

课后思考

二维数组的内存寻址公式是怎样的？
例如example[a][b]，其内存寻址公式为：
$f(a)(b) = f(0)(0) * (a * n + b) * unitsize$
其中n为第一维中数组的大小。