1、如何实现随机访问？

---

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

 线性表：数组，链表，队列，栈。每个线性表的数据最多只要前后两个方向

非线性表：树，图，堆。之所以叫非线性，是因为数据并不是简单的前后关系

2） 连续的内存空间、相同类型的数据，所以数组可以随机访问，但对数组进行删除插入，为了保证数组的连续性，就要做大量的数据搬移工作

 

2、数组是如何实现根据下标随机访问数组元素的?

---

计算机给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据     a[i]_address = base_address + i * data_type_size

纠正数组和链表的错误认识。数组的查找操作时间复杂度并不是O(1)。即便是排好的数组，用二分查找，时间复杂度也是O（logn）。
正确表述：数组支持随机访问，根据下标随机访问的时间复杂度为O（1）

 

3、低效的插入和删除

---

1） 插入：从最好O(1) 最坏O(n) 平均O(n) 

     如果在数组末尾插入元素，就不需要移动数据，最好时间复杂度是O(1)

     如果在数组开头插入元素，就需要依次往后移动数据，最坏时间复杂度是O(n)

     因为在每个位置插入元素的概率是一样的，所以平均时间复杂度就是(1+2+…n)/n=O(n)

     数组若无序，插入新的元素时，为了避免大规模移动数据，可以将第K个位置元素移动到数组末尾，把新的元素，插入到第  k  个位置，此处复杂度为O(1)

2 ) 删除：从最好O(1) 最坏O(n) 平均O(n)

 多次删除集中在一起，提高删除效率记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没有更多的存储空间时，再触发一次真正的删除操作。即JVM标记清除垃圾回收算法

 

4、警惕数组越界

---

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

 这段代码由于书写错误，i<=3，当i=3时，数组arr[3]访问越界。在c语言中，只要不是访问受限的内存，所有的内存空间都是可以*访问的。根据前面的寻址公式，arr[3]会被定位到不属于数组的内存地址上，而这个地址正好是存储变量i的内存地址，那么arr[3]=0相当于i=0，所以就会导致代码无限循环。在java中就会抛出java.lang.ArrayIndexOutOfBoundsException异常

 4、容器能否完全替代数组

---

相比于数组，java中的ArrayList封装了数组的很多操作，并支持动态扩容。一旦超过初始容量，扩容时比较耗内存，因为涉及到内存申请和数据搬移。
数组适合的场景：
1） Java ArrayList ，基本类型的使用涉及装箱拆箱，有一定的性能损耗，如果特别关注性能，可以考虑数组

2） 若数据大小事先已知，并且涉及的数据操作非常简单，可以使用数组

3） 表示多维数组时，数组往往更加直观。

4） 业务开发容器即可，底层开发，如网络框架，性能优化。选择数组

 

5、题目

1、为什么数组要从0开始编号，而不是从1开始的问题？

 a[k]_address = base_address + k * type_size   从0计算

 a[k]_address = base_address + (k-1)*type_size  从1计算
1） 从偏移角度理解a[0] 0为偏移量，如果从1计数，会多出K-1。增加cpu负担。

2） 也有一定的历史原因

2、二维数组内存寻址：
对于 m * n 的数组，a [ i ][ j ] (i < m,j < n)的地址为：

address = base_address + ( i * n + j) * type_size

address=base_addresss+（j * m + i）*type_size