定义： 数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
特性：可实现随机访问，但是插入删除操作比较慢
注意：数组访问越界、容器与数组如何抉择？
一、数组如何实现随机访问？
计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：
a[i]_address = base_address + i * data_type_size
data_type_size 表示数组中每个元素的大小
二、为何数组的插入删除操作比较慢？如何优化呢？
2.1 插入
- 数组末尾插入元素：无需移动数据，时间复杂度：O(1)
- 数组开头插入元素：所有数据都要移动一遍，时间复杂度：O(n)
平均时间复杂度：(1 + 2 + …n) / n == O(n)
特殊场景下，可以用如下图方式来插入元素，可将时间复杂度降为 O(1)
时间复杂度: O(1)
2.2 删除
删了某条数据，为了内存的连续性，也要搬移数据。
- 数组删除末尾元素：时间复杂度：O(1)
- 数组删除开头元素：时间复杂度：O(n)
平均时间复杂度：O(n)
特殊场景下 不一定非得追求数组中数据的连续性，可进行如下处理
每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作。
先记录 a,b,c 已被删除，等到数组存储空间不够的时候一块移除，后续数据只需迁移一次
如此可以大大减少了删除操作导致的数据搬移。（JVM 标记清除垃圾回收算法的核心思想）👍
三、数组访问越界
数组越界在 C 语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。但是会造成莫名其妙的逻辑错误！
在 Java 当中，编译器会做数组越界检测。数组越界会抛出：java.lang.ArrayIndexOutOfBoundsException
四、容器能否完全替代数组？
针对数组类型，许多语言提供了封装的容器类，如 Java 的 ArrayList、C++ STL 中的 vector，在实际开发中何时使用容器类，何时使用数组呢？
容器类（以 Java 的 ArrayList 为例）
- 优势：自动扩容，每次空间不够都会将空间自动扩容 1.5 倍大小。
- 劣势：扩容涉及内存申请和数据迁移，比较耗时。而且无法存储基本数据类型，需要拆装箱操作，有一定的性能损耗
数组
- 优势：性能好，可存储基本数据类型。多维数组看起来比较直观...
- 劣势：手动扩容，许多基本的操作方法需要自己实现
综上所述，数组适用于追求性能的底层框架开发，容器类适用于一般的业务开发
*五、为何数组不从 1 开始作为下标？
下标从 0 开始的寻址公式
a[i]_address = base_address + i * data_type_size
下标从 1 开始的寻址公式
a[i]_address = base_address + （i - 1) * data_type_size
由上述寻址公式可见，从 1 开始编号，每次随机访问数组都会多一次减法运算，对于 CPU 就多了一次减法指令。
*六、一些思考
- 本篇关于数组的原理，引出了 JVM 的标记清除垃圾回收算法的核心原理，回顾理解下 JVM 的标记清除垃圾回收算法。
- 思考下二维数组的寻址公式是怎样的呢？
【极客时间，数据结构与算法之美】
网友评论