9.jpg
为什么很多编程语言中数组都从0编号？
在大多数编程语言中，数组都是从0开始编号，为什么数组要从0开始编号，而不是1呢？

数组如何实现随机访问(Random Acess)（应该翻译为任意访问）：

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

定义中的几个关键词
1）线性表：数组、链表、队列、栈 数据排成像一条线的结构，只有前后两个方向。
非线性表：二叉树，堆，图 非线性表中，数据之间并不是简单的前后关系
image.pngimage.png
2）连续的内存空间和相同类型的数据。
正是因为两个限制，数组才有一个堪称杀手锏的特性：“随机访问”。但这两个限制也让数组的很多操作变得很低效，比如数组中删除，插入数据，为了保证连续性都需要大量的数据搬移工作。

  1. 那么数组如何实现根据下标随机访问数组元素的呢？

image.png以一个int[] a=new int [10]来举例，内存块首地址base_address=1000
计算机会通过地址访问内存数据。当计算机需要随机访问数组中某一个元素，会首先通过下面寻址方式，计算出元素存储的内存地址。
a[i]_address = base_address + i * data_type_size
其中data_type_size表示数组每个元素大小。 该例子数组存储int类型，data+type_size为4字节。
纠正一个常见错误：数组链表区别。不应该回答“链表适合插入、删除，时间复杂度O(1);数组适合查找，查找时间复杂度O(1)” 实际上这种表述不准确。数组适合查找但查找的时间复杂度并不为O(!) ,即使排好序的数组，二分查找时间复杂度也是(logn)，正确表述应该是：数组支持随机访问，根据下标访问的时间复杂度为O(1)。

低效的“插入”和“删除”

  1. 插入

假设数组长度为n，将一个数据插入第k位置，需要将第k~n的这部分元素都顺序的往后挪一位。
最好O(1)(尾部插入) 最坏O(n)(开头插入) 平均O(n)(每个位置插入元素概率一样，所以平均时间复杂度为(1+2+..n)/n=O(n))。
image.png

  1. 删除

和插入类似，删除第k个位置，为保证内存连续性，需要搬移数据。
最好O(1)(尾部删除) 最坏O(n)(开头删除) 平均O(n)(每个位置删除元素概率一样，所以平均时间复杂度为(1+2+..n)/n=O(n))。
但很多时候，不一定追求数组中数据的连续性。如果我们将多次删除操作操作一起，删除效率会提高很多。
image.png
我们可以记录下已经删除的数据，每次删除操作并不是真正的搬移数据，只是记录数据被删除。当数组没有更多空间存储数据时，我们再触发一次真正的删除操作，这样大大减少了对删除导致的数据搬移。
这也是JVM标记清楚垃圾回收算法的核心思想。

警惕数组越界

数组越界会出现莫名其妙的逻辑错误。debug难度很大。

容器能否完全代替数组？

类似JAVA中的Arraylist，C++STL中的vector。如何选择呢？
以JAVA为例，ArrayList优势是可以将很多数组操作细节封装起来，并支持动态扩容。

  1. Java ArrayList 的使用涉及装箱拆箱，有一定的性能损耗，如果特别管柱性能，可以考虑数组
  2. 若数据大小事先已知，并且涉及的数据操作非常简单，可以使用数组
  3. 表示多维数组时，数组往往更加直观。如 Object[][] array; 容器则需要这样 ArrayList>array。

  4. 业务开发容器即可，省时省力。非常底层开发性能需要优化，如网络框架，性能优化，选择数组。

    解答开篇

  5. 从数组存储的内存模型上看，“下标”最确切的定义应该时“偏移量”。如果a来表示数组的首地址，a[0]就是偏移量为0的位置，也就是首地址，a[k]就是表示k个type_size的位置，所以公式为

a[k]_address = base_address + k * type_size
但如果数组从1开始，我们计算a[k]地址会变为：
a[k]_address = base_address + (k-1)*type_size
对于CPU来说需要多做1次减法指令。

  1. 当然更有可能是历史原因。 可能C语言设计者设计从0开始，之后的JAVA,JavaScript进行了效仿。

    内容小结

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

    思考

  2. JVM标记清除算法

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

不足：1.效率问题。标记和清理效率都不高，但是当知道只有少量垃圾产生时会很高效。2.空间问题。会产生不连续的内存空间碎片。
类似将垃圾扔入垃圾桶，只是标记了它是垃圾，并不代表被扔掉，当垃圾桶满了之后，才代表垃圾被扔掉。

  1. 二维寻址公式类比

二维数组内存寻址：
对于 m n 的数组，a [ i ][ j ] (i < m,j < n)的地址为：
address =base_address + ( i n + j) * type_size
另外，对于数组访问越界造成无限循环，我理解是编译器的问题，对于不同的编译器，在内存分配时，会按照内存地址递增或递减的方式进行分配。老师的程序，如果是内存地址递减的方式，就会造成无限循环。

  1. 多维寻址公式

虽然我们可以把二维数组中成员看作行和列两个方向构成的格子中的数据，三维数组成员看作长宽高构成的立体格子中的数据，但这只是有助于理解的形象表示，实质上数组在内存中是连续线性的。
那么对于二维数组 x[]来说，求x[i][j]的时候（不会考虑i j越界的情况），要到i的时候，一定走完了ia2的长度，在x[i][0]往后找j个长度就是x[i][j]，所以会从初始地址增加 （ia2+j）个单位长度。
对于三维数组， x[][]来说，求x[i][j][k]的时候，要到i的时候，一定走完了ia2a3的长度，在x[i][0][0]往后找ja3个长度就是x[i][j][0]，再往后找k个长度就是x[i][j][k]，所以会从初始地址增加 （ia2a3+ja3+k）个单位长度。以此类推如下：
数组 为x ,an为某一维度长度
一维数组：（a1）x[i]_address = base_address + i type_size
二维数组：（a1a2）x[i][j]_address = base_address + ( i a2 + j ) type_size
三位数组：（a1a2a3）x[i][j][k]_address = base_address + ( i a2a3 + j a3 + k ) type_size
四位数组：（a1a2a3a4）x[i][j][k][l]_address = base_address + ( i a2a3a4 + j a3a4 + k a4 + l ) type_size
。。。。。。
n维数组：（a1a2a3…an）x[i1][i2][i3]…[in] = base_address + ( i1 a2a3…an + i2 a3a4…an + i3 a4a5…an +……i(n-1) an + in) * type_size9.jpg