数组

数组：最基本的数据结构

专业解释

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

线性表

线性表就是数据排成像一条线一样的结构

连续的内存空间和相同类型的数据

元素存储的内存地址计算公式

1
a[i]_address = base_address + i * data_type_size

数组和链表的区别

数组支持随机访问，根据下标随机访问的时间复杂度为 O(1);链表适合插入、删除，时间复杂度 O(1)

优化插入数据

我们在某个位置插入一个新的元素时，就必须按照刚才的方法搬移 k 之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数据插入到第 k 个位置，为了避免大规模的数据搬移，我们还有一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置

优化删除操作

先对要删除的数据进行记录，当数组空间不足时统一执行删除操作，与JVM垃圾回收类似。

容器

优势：支持数组常规操作，支持动态扩容

选择场景：对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选

数组为何要使用“0”作为起始索引

索引正确定义为“偏移量”，且如果使用“1”作为起始下标，内存地址计算公式变为：

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

此时会使cpu多进行一次减法运算。

内容小结

数组用一块连续的内存空间，来存储相同类型的一组数据，最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为 O(n)。在平时的业务开发中，我们可以直接使用编程语言提供的容器类，但是，如果是特别底层的开发，直接使用数组可能会更合适。

思考

前面我基于数组的原理引出 JVM 的标记清除垃圾回收算法的核心理念。我不知道你是否使用 Java 语言，理解 JVM，如果你熟悉，可以在评论区回顾下你理解的标记清除垃圾回收算法。

大多数主流虚拟机采用可达性分析算法来判断对象是否存活，在标记阶段，会遍历所有 GC ROOTS，将所有 GC ROOTS 可达的对象标记为存活。只有当标记工作完成后，清理工作才会开始。

不足：1.效率问题。标记和清理效率都不高，但是当知道只有少量垃圾产生时会很高效。2.空间问题。会产生不连续的内存空间碎片。

前面我们讲到一维数组的内存寻址公式，那你可以思考一下，类比一下，二维数组的内存寻址公式是怎样的呢？

对于 m * n 的数组，a [ i ][ j ] (i < m,j < n)的地址为：

1
address = base_address + ( i * n + j) * type_size