数组

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

咱们晓得，计算机会给每个内存单元调配一个地址，计算机通过地址来拜访内存中的数据。当计算机须要随机拜访数组中的某个元素时，它会首先通过上面的寻址公式，计算出该元素存储的内存地址：

a[i]_address = base_address + i * data_type_size

其中 data_type_size 示意数组中每个元素的大小。

很多人都答复说，“链表适宜插入、删除，工夫复杂度 O(1)；数组适宜查找，查找时间复杂度为 O(1)”。实际上，这种表述是不精确的。数组是适宜查找操作，然而查找的工夫复杂度并不为 O(1)。即使是排好序的数组，你用二分查找，工夫复杂度也是 O(logn)。所以，正确的表述应该是，数组反对随机拜访，依据下标随机拜访的工夫复杂度为 O(1)。

容器可能代替数组

1. Java ArrayList 无奈存储根本类型，比方 int、long，须要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有肯定的性能耗费，所以如果特地关注性能，或者心愿应用根本类型，就能够选用数组。
2. 如果数据大小当时已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分办法，也能够间接应用数组。
3. 还有一个是我集体的爱好，当要示意多维数组时，用数组往往会更加直观。比方 Object[][] array；而用容器的话则须要这样定义：ArrayList<ArrayList<object> > array。

总结，对于业务开发，间接应用容器就足够了，省时省力。毕竟损耗一丢丢性能，齐全不会影响到零碎整体的性能。但如果你是做一些十分底层的开发，比方开发网络框架，性能的优化须要做到极致，这个时候数组就会优于容器，成为首选。

数组为什么是从 0 开始编号，而不是 1 呢？

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。后面也讲到，如果用 a 来示意数组的首地址，a[0] 就是偏移为 0 的地位，也就是首地址，a[k] 就示意偏移 k 个 type_size 的地位。然而，如果数组从 1 开始计数，那咱们计算数组元素 a[k] 的内存地址就会变为：

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

比照两个公式，咱们不难发现，从 1 开始编号，每次随机拜访数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。

下面解释得再多其实都算不上压倒性的证实，说数组起始编号非 0 开始不可。最次要的起因可能是历史起因。

C 语言设计者用 0 开始计数数组下标，之后的 Java、JavaScript 等高级语言都效仿了 C 语言，或者说，为了在肯定水平上缩小 C 语言程序员学习 Java 的学习老本，因而持续沿用了从 0 开始计数的习惯。实际上，很多语言中数组也并不是从 0 开始计数的，比方 Matlab。甚至还有一些语言反对正数下标，比方 Python。