数组

什么是数组

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

数组的几个特点
1、它是线性表。
线性表就是数据排成一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。（链表，队列，栈等也是线性表结构）
2、连续的内存空间和相同类型的数据
因为他的这两个限制，所以他有了随机访问的特性。但是，想要在数组中删除，插入一个数据，就必须得做大量的数据搬移工作来确保数组的连续性。

数组与链表（面试题）

1、数组中的元素存在一个连续的内存空间中，而链表中的元素可以不存在于连续的内存空间。
2、数组支持随机访问，根据下标随机访问的时间复杂度是O(1)；链表适合插入、删除操作，时间复杂度为O(1）。

容器能否替代数组

容器的优势：对于Java语言，容器封装了数组插入、删除等操作的细节，并且支持动态扩容。
对于Java，一些更适合用数组的场景：
1、Java的ArrayList无法存储基本类型，需要进行装箱操作，而装箱与拆箱操作都会有一定的性能消耗，如果特别注意性能，或者希望使用基本类型，就可以选用数组。
2、若数组大小事先已知，并且对数组只有非常简单的操作，不需要使用到ArrayList提供的大部分方法，则可以直接使用数组。
3、多维数组时，使用数组会更加直观。

JVM标记清除算法？

GC最基础的收集算法就是标记-清除算法，如同他们的名字一样，此算法分为“标记”、“清除”两个阶段，先标记出需要回收的对象，再统一回收标记的对象。不足有二，一是效率不高，二是产生碎片内存空间。

数组的内存寻址公式？

一维数组：a[i]_address=base_address+itype_size
二维数组：二维数组假设是mn， a[i][j]_address=base_address + (in+j)type_size
三维数组：三维数组假设是mnq， a[i][j][k]_address=base_address + (inq + jq + k)type_size

最后解决引子问题：

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

1、从数组存储的内存模型上来看，“下标”确切的说法就是一种“偏移”，相比从1开始编号，从0开始编号会少一次减法运算，数组作为非常基础的数组结构，通过下标随机访问元素又是非常基础的操作，效率的优化就要尽可能的做到极致。
2、主要的原因是历史原因，C语言的设计者是从0开始计数数组下标的，之后的Java、JS等语言都进行了效仿，或者说是为了减少从C转向Java、JS等的学习成本。