数据结构与算法之美（四）数组

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

如何实现随机访问？

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

线性表（Linear List）：最基本、最简单、应用最广泛的一种数据结构，一个线性表是 n (n >= 0) 个具有相同特性的数据元素的有限序列，这些数据元素也可称为结点、记录或表目。除了数组，链表、队列、栈等也是线性表结构。

线性表.jpg

与线性表对立的是非线性表，比如二叉树、堆、图等。

非线性表.jpg
连续的内存空间和相同类型的数据
正是因为这两个限制，数组才有一个堪称“杀手锏”的特性：随机访问。然鹅，这两个限制也使得在数组中插入、删除数据的操作变得低效。

数组是如何实现根据下标随机访问数组元素的？
以长度为 10 的 int 类型的数组 int[] a = new int[10]为例。如下图，计算机给数组 a[10]分配了一块连续内存空间 1000~1039 ，其中，内存块首地址 base_address 为 1000

图.jpg

当计算机需要随机访问数组中的某个元素时，会首先通过下面的寻址公式👇 ，计算出该元素存储的内存地址。

a[i]_address = base_address + i * data_type_size

其中，data_type_size 表示数组中每个元素的大小。上例中，数组中存储的是 int 类型数据，所以 data_type_size 为 4 个字节。

在面试中，被问到数组和链表的区别，很多人回答是：“链表适合插入、删除，时间复杂度为 O(1) ，数组适合查找，查找时间复杂度为 O(1) ”。
实际上，这种表述是不准确的。数组是适合查找操作，但是查找的时间复杂度并不是 O(1) ，根据不同的查找算法，查找的时间复杂度也不同，比如二分查找法，时间复杂度是 O(logn) 。所以，正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1) 。

低效的“插入”和删除

插入操作

假设数组的长度为 n ，现在我们需要将一个数据元素插入数组中第 k 个位置，分析时间复杂度：

最好情况时间复杂度：k = n ，往数组的末尾插入元素，无需移动其他数据元素，此时时间复杂度为 O(1)
最坏情况时间复杂度：k = 0 ，往数组的开头插入元素，其他数据元素都需要依次后移一位，此时时间复杂度为 O(n)
平均情况时间复杂度：由于往数组中每个位置插入元素的概率相同，所以平均情况时间复杂度为：(1 + 2 + 3 + ... + (n - 1) + n) / n = n(n + 1) / 2n = (n + 1) / 2 = 1/2 + n/2 ，去掉常数和系数，结果为 O(n)

以上是有序数组的插入操作。如果数组中存储的数据元素没有任何规律，此数组只是被当作一个存储数据的集合，这种情况下，将一个数据元素插入数组中第 k 个位置，为了避免大规模的数据迁移，可直接将第 k 位的数据移到数组元素的最尾端元素的后面，把新元素放入第 k 个位置。

删除操作

跟插入数据的操作类似，数组的长度为 n ，我们要删除数组中第 k 个位置的数据元素，为了内存的连续性，也需要迁移数据，时间复杂度分析如下：

最好情况时间复杂度：k = n ，从数组的末尾删除元素，无需移动其他数据元素，此时时间复杂度为 O(1)
最坏情况时间复杂度：k = 0 ，将数组的开头元素删除，其他数据元素都需前移一位，此时时间复杂度为 O(n)
平均情况时间复杂度：跟插入数据的操作同理，为 O(n)

实际上，某些特殊场景下，我们并不一定非得追求数组中内存的连续性，那么，我们将多次删除操作集中在一起执行，删除的效率会高很多。比如：数组 a[10] 中存储了 8 个元素 a, b, c, d, e, f, g, h ，我们需要依次删除 a, b, c 这三个元素，为了避免 d, e, f, g, h 这些元素被迁移三次，可以先记录下每次要删除的元素。就是说，每次的删除操作并不是真正的剔除元素并迁移，而只是标记数据已经被删除。当数组没有更多空间存储数据是，再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据迁移。

这类似于 JVM 标记清除垃圾回收算法的核心思想。

警惕数组的访问越界问题

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

由于数组的长度为 3 ，而我们 for 循环的结束条件是 i <= 3 ，所以当 i = 3 时，数组 arr[3] 访问越界。在 C 语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的根据前面的数组寻址公式，arr[3] 也会被定义到某块不属于数组的内存地址上，而这个地址正好是存储变量 i 的内存地址，那么 arr[3] = 0 相当于 i = 0 ，会导致代码无限循环。

很多计算机病毒正是利用了代码中的数组越界可以访问非法地址的漏洞来攻击系统。所以编程时一定要警惕数组越界。

但并非所有语言都像 C 一样，数组越界检查工作需要有程序员来完成。Java 语言本身就会做越界检查，比如：

int[] a = new int[3];
a[3] = 10;

这段 Java 代码，就会抛出 java.lang.ArrayIndexOutOfBoundsException

容器能否完全替代数组？

针对数组类型，很多语言都提供了容器类，比如 Java 中的 ArrayList、 C++ STL 中的 vector。在项目开发中，该如何选择使用呢？

以 Java 语言为例。ArrayList 有以下优势：

封装了很多操作数组的方法
支持动态扩容

数组本身在定义的时候需要预先指定大小，如果申请了大小为 10 的数组，当第 11 个数据需要存储到数组中时，就需要重新申请一块更大的空间，将原来数组数据复制过去，然后再将新的数据插入。

如果使用 ArrayList，就无需关心底层的扩容逻辑了，ArrayList 已经实现好了。每次存储空间不够的时候，它都会将空间扩容为 1.5 倍大小。不过需要注意的是，扩容操作涉及到内存申请和数据迁移，比较耗时。所以，如果能事先确定需要存储的数据大小，最好在创建 ArrayList 的时候事先指定数据大小。

比如：需要从数据库中取出 10000 条数据放入 ArrayList 。以下代码事先指定了数据大小，可以省去很多次内存申请和数据迁移操作：

ArrayList<User> users = new ArrayList(10000);
for (int i = 0; i < 10000; ++i) {
  users.add(xxx);
}

以下情况，用数组会更合适：

Java ArrayList 无法存储基本类型，比如 int、long ，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，就应该使用数组
如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，就应该使用数组

为什么大多数编程语言中，数组要从 0 开始编号，而不是更符合人类习惯的从 1 开始？

从数组存储的内存模型上看，“下标”最确切的定义是偏移（offset）。如果用 a 来表示数组的首地址，a[0] 就是偏移为 0 的位置、数组第一个元素的位置，也就是首地址；a[k] 就表示偏移 k 个 type_size 的位置，所以计算 a[k] 的内存地址可以代入寻址公式：

a[k]_address = base_address + k * type_size

如果数组从 1 开始编号，那么每次随机访问数组元素都要多执行一次减法运算指令：

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

数组作为非常基础的数据结构，通过下标随机访问元素又是非常基础且常用的操作，效率的优化应当尽可能做到极致。所以数组会是从 0 开始编号。

课后思考 🤔

回顾 JVM 的标记清除垃圾回收算法
思考二维数组的内存寻址公式