数组

数组如何实现随机访问

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

• 线性表：数组、链表、队列、栈 ；非线性表：树 图
• 连续的内存空间、相同的数据，所以数组可以随机访问，效率高但对数组进行删除插入，为了保证数组的连续性，就要做大量的数据搬移工作

数组如何实现下标随机访问。

引入数组再内存种的分配图，得出寻址公式
比如一个长度为 10 的 int 类型的数组 int[] a = new int[10] ，其内存分配图为：

image.png

如图所示，计算机给数组 a[10]，分配了一块连续内存空间 1000～1039，其中，内存块的首地址为 base_address = 1000；然后呢，算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：

a[i]_address = base_address + i * data_type_size
其中 data_type_size 表示数组中每个元素的大小

纠正数组和链表的错误认识。

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

低效的插入和删除

1. 插入：从最好O(1)；最坏O(n)； 平均O(n)
2. 删除：从最好O(1) 最坏O(n) 平均O(n)
3. 多次删除集中在一起，提高删除效率

如何提升数组插入和删除的效率

• 插入：数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把心的元素，插入到第k个位置，此处复杂度为O(1)，如图：
  

  image.png

• 删除：记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没有更多的存储空间时，再触发一次真正的删除操作。这也是 JVM 标记清除垃圾回收算法的核心思想。

警惕数组的访问越界问题

用C语言循环越界访问的例子说明访问越界的bug

容器能否完全替代数组

相比于数字，java中的ArrayList封装了数组的很多操作，并支持动态扩容。一旦超过数组容量，扩容时比较耗内存，因为涉及到内存申请和数据搬移。
数组适合的场景：

1. Java的ArrayList 的使用涉及装箱拆箱，有一定的性能损耗，如果特别关注性能，可以考虑数组
2. 若数据大小事先已知，并且涉及的数据操作非常简单，可以使用数组
3. 表示多维数组时，数组往往更加直观。
4. 业务开发容器即可，底层开发，如网络框架，性能优化。选择数组。

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

1. 从偏移角度理解；a[0] 的话0为偏移量，计算 a[k] 的内存地址的公式：

a[k]_address = base_address + k * type_size

如果数组从 1 开始计数，那我们计算数组元素 a[k] 的内存地址就会变为:

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

可见从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。
比如：为什么循环要写成 for(int i = 0;i<3;i++) 而不是 for(int i = 0 ;i<=2;i++)；第一个直接就可以算出3-0 = 3 有三个数据，而后者 2-0+1个数据，多出1个加法运算，很恼火。

2. 也有一定的历史原因

数组相关练习题

1. 数组为什么从0开始编号？
2. 如何提升数组插入和删除的效率？
3. 数组是如何支持下标随机访问的？
4. 说说一维数组和二维数组的内存寻址公式是怎样的呢？

• 一维数组：a[i]_address=base_address+i*type_size
• 二维数组：二维数组假设是mn， a[i][j]_address=base_address + (in+j)*type_size
• 三维数组：三维数组假设是mnq， a[i][j][k]_address=base_address + (inq + jq + k)type_size