数组是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
如何实现随机访问？
因为数组是线性表，连续的内存和相同的数据类型使得随机访问成为了可能，我们只需知道初始地址和数据类型就可以计算出任意索引的地址，a[i]_address = base_address + i * data_type_size。
面试常问，数组和链表的区别。很多人都回答说，“链表适合插入、删除，时间复杂度是O(1)；数组适合查找，查找的时间复杂度为O(1)”。这样的说法是不准确的，因为即便是大小排列好的数组，用二分查找法，时间复杂度也是O(logn)。正确的表述是，数组支持随机访问，根据下标随机访问的时间复杂度是O(1)。
低效的“插入”和“删除”
ArrayList底层是数组实现，为了保持内存数据的连续性，会导致插入和删除两个操作比较低效。ArrayList在位置k添加和删除数据时，需要将k位置之后的元素做相应的操作，如果操作在数组末尾，时间复杂度是O(1)。如果操作在数组开头，时间复杂度是O(n)。平均时间复杂度为O(n)。如果数组中的数据是有序的，需要按照上面的描述操作。如果数据没有任何规律的话，可以优化一下，为了避免大规模的数据搬移，可以将k位置的数据直接搬移到数组末尾位置，再把新数据放到k位置。删除操作的时候也可以优化一下，可以将要删除的数据标记下来，当数组没有足够的空间时，将标记的数据统一删除，就可以提高很大的性能。也就是JVM标记清除垃圾回收的思想。
数组访问越界问题
Java语言会做数组越界检查，异常为ArrayIndexOutOfBoundsException。
容器能否完全代替数组？
Java中数组和ArrayList相比，ArrayList最大的优势是将很多数组操作的细节封装了起来，另外，还支持动态扩容。初始申请了大小为10的数组，每次扩容1.5倍。不过，因为扩容操作及内存的申请和数据搬移都比较耗时，所以，如果事先能确定数据大小，最好在ArrayList创建是指定数据大小。
数组也有很多优势，ArrayList无法存储基本类型，只能存储封装类型，而装箱和拆箱需要消耗性能。多维数组时，用数组会直观一些。
解答开篇
为什么很多编程语言中，数组要从0开始编号？从数组存储的内存模型上看，下标最确切的定义是偏移量，在计算a[i]的内存地址时，公式为a[i]_address = base_address + i * data_type_size，如果数组从1开始编号，公式为a[i]_address = base_address + (i -1) * data_type_size。对CPU而言，就多了一次减法指令。最主要的原因应该是历史问题，C语言的设计者使用了0开始编号，后续的很多语言也就沿用了这个规矩。
