数组是如何随机访问元素？数组下标为什么从0开始，而不是1？
数组是如何随机访问元素？数组下标为什么从0开始，而不是1？
数组如何实现随机访问元素
什么是数组？
数组（Array）是一种线性表数据结构，它用一组连续的内存空间，来存储相同类型的数据。
什么是线性表（Linear List）？
线性表就是数据排成一条线一样的结构，每个线性表的数据最多只有前后两个方向。
例如：数组，链表，队列，栈 等都是线性表结构。
什么是非线性表？
例如：二叉树，堆，图，等，是非线性表，是因为，在非线性表中，数据之间并不是简单的前后关系。
数组是如何随机访问数组元素？
数组是如何实现根据下标随机访问数组元素的吗？
例如： int[]a=newint[10]
1，计算机给数组a[10]，分配了一组连续的内存空间。 2，比如内存块的首地址为 base_address=1000。 3，当计算给每个内存单元分配一个地址，计算机通过地址来访问数据。当计算机需要访问数组的某个元素的时候，会通过一个寻址公式来计算存储的内存地址。
公式如下：
a[i]_address = base_address + i * data_type_sizearr[i] 首地址 = 数组内存块首地址 + 数据类型大小 * i ，其中i为偏移量。
baseaddress：内存块的首地址。datatype_size：数组中每个元素的大小，比如每个元素大小是4个字节。
1，数组使用二分法查找元素，时间复杂度是O(logn)。 2，根据下标随机访问的时间复杂度是O(1)。
低效的“插入”和“删除”
插入
插入：从最好O(1) 最坏O(n) 平均O(n)
什么时候会是O(1)？
数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把新的元素，插入到第k个位置，此处复杂度为O(1)。
例如：a[10] 数组存储了5个元素： A B C D E
我们现在需要将元素 x 插入到第 3 个位置。我们只需要将 c 放入到 a[5]，将 a[2] 赋值为 x 即可。
最后，数组中的元素如下： A，C，X，D，E，C。
什么时候会是最坏O(n)？
从数组开头插入数据，所有的数据往后移一位，情况最差，时间复杂度为O(n) 。 每一位插入的概率一样，所以平均时间复杂度为 (1+2+...+n)/n=(1+n)/2=O(n)。
删除
删除：从最好O(1) 最坏O(n) 平均O(n)
和插入数据类似，如果我们要删除 K 个位置的数据，要保证内存的连续性，我们需要搬移 K 位置后的所有数据往前移动一位。
什么时候会是O(1)？
删除开头的数据
什么时候会是最坏O(n)？
同数组插入的原理类似
数组如何提高效率？
将多次删除操作中集中在一起执行，可以先记录已经删除的数据，但是不进行数据迁移，而仅仅是记录，当发现没有更多空间存储时，再执行真正的删除操作，这样减少数据搬移次数节省耗时。
这也是跟 JVM 标记清除垃圾回收算法的核心思想相似。
标记-整理垃圾回收算法。
在垃圾收集时此算法分为“标记”、“清除”两个阶段，先标记出需要回收的对象，再统一清除标记的对象。清除之后会产生大量不连续的内存碎片。
标记-整理垃圾回收算法
在标记完成之后让所有存活的对象都向一端移动，然后直接清理掉边界以外的内存。
用数组还是容器？
数组先指定容器大小，容器ArrayList可以动态扩容，并且封装了好多方法，一旦超过存储容量，扩容时比较耗时，因为涉及内存申请和数据复制搬移到扩容后的数组。
1，如果已知数据大小，且涉及的数据操作比较简单，可以用数组。 2，比如已知 1 万条数据要存入 ArrayList，我们就可以事先指定容器大小。
例如下代码，就可以，省掉多次的，内存申请，和数据搬移操作
ArrayList<User> users = new ArrayList(10000);for (int i = 0; i < 10000; ++i) { users.add(xxx);}3，容器无法存储基本类型，比如 int long 需要转换成包装类型，类型的转换有性能消耗。 4，业务开发，使用容器足够，追求性能，首先用数组。
为什么数组要从 0 开始编号，而不是1？
从偏移角度理解a[0] 0为偏移量，如果从1计数，会多出K-1。增加cpu负担。为什么循环要写成 for(inti=0;i<3;i++)而不是 for(inti=0;i<=2;i++)。第一个直接就可以算出3-0 = 3 有三个数据，而后者 2-0+1个数据，多出1个加法运算，很恼火。
参考：《数据结构与算法之美》
更多技术干货