从零开始编号的数组

1. 如何实现随机访问

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

数组

两个关键点：线性表、连续的内存空间和相同类型的数据

线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。除了数组，链表、队列、栈等也是线性表结构。而与它相对立的是非线性表，比如二叉树、堆、图等。在非线性表中，数据之间并不是简单的前后关系。

连续的内存空间和相同类型的数据。正是因为这两个限制，数组才有了一个堪称「杀手锏」的特性：「随机访问」。但是，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

根据下标随机访问数组元素的时间复杂度为 O(1)。随机访问和查找不一样，即便是排好序的数组，用二分查找，时间复杂度也是 O(logn)。随机访问有个寻址公式：

a[i]_address = base_address + i * data_type_size

其中 data_type_size 表示数组中每个元素的大小，base_address 是内存块的首地址。

从数组存储的内存模型上来看，「下标」最确切的定义应该是「偏移量」，a[0] 就是偏移为 0 的位置，也就是首地址。

2. 低效的插入和删除

插入和删除需要移动数据，时间复杂度都是 O(n)。

例外情况：

1. 当数组中存储的元素不要求有序时，如果要插入到第 k 个位置，那么把该位置的数据放到数组末尾，新元素放到第 k 位。比如原数组：[a, b, c, d]，把 x 插入到第 2 位，数组变为 [a, x, c, d, b]。
2. 删除元素时，标记被删除的数据，并不会真正地搬移数据，当数组没有更多的空间时，触发一次真正删除操作，这样就大大减少了数据移动。这其实就是 JVM 标记清除垃圾回收算法的核心思想。

3. 警惕数组访问越界

Java 语言会做数据越界检查，而 C 语言不会。数组越界时一般都会出现莫名其妙的逻辑错误，debug 的难度非常的大。所以写代码的时候一定要警惕数组越界。

4. 容器能否完全代替数组

ArrayList 最大的优势就是可以将很多数组操作的细节封装起来，支持动态扩容。

每次存储空间不够的时候，ArrayList 会将空间自动扩容为原来的 1.5 倍大小。扩容操作比较耗时，涉及内存申请和数据搬移。所以，如果事先能确定需要存储的数据大小，最好在创建 ArrayList 的时候事先指定数据大小。

        ArrayList<String> a = new ArrayList<>(666); // 推荐
        ArrayList<String> b = new ArrayList<>(); // 不推荐

更适合用数组的场景：

1. ArrayList 无法存储基本类型，比如 int，需要封装为 Integer 类，而装箱、拆箱则有一定的性能消耗，所以如果特别关注性能，或者想使用基本类型，就可以选用数组。

2. 如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。

3. 当表示多维数组时，用数组往往会更加直观。比如 Object[][] array；而用容器的话则需要这样定义：ArrayList<ArrayList> array。

思考题：

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