数组

# 数组如何实现随机访问

## 什么是数组？

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

## 什么是线性表（Linear List）？

线性表就是数据排成一条线一样的结构，每个线性表的数据最多只有前后两个方向。

例如：数组，链表，队列，栈 等都是线性表结构

## 什么是非线性表？

例如：二叉树，堆，图，等，是非线性表，是因为，在非线性表中，数据之间并不是简单的前后关系

## 数组是如何实现根据下标随机访问数组元素的吗？

例如：`int[] a = new int[10]`

1，计算机给数组a[10]，分配了一组连续的内存空间

2，比如内存块的首地址为 `base_address = 1000`

3，当计算给每个内存单元分配一个地址，计算机通过地址来访问数据。当计算机需要访问数组的某个元素的时候，会通过一个**寻址公式**来计算存储的内存地址。

公式如下：

```java

a[i]_address = base_address + i * data_type_size

```

arr[i] 首地址 = 数组内存块首地址 + 数据类型大小 * i ，其中i为偏移量。

**base_address**：内存块的首地址

**data_type_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，我们就可以事先指定容器大小，就可以，省掉多次的，内存申请，和数据搬移操作

3，容器无法存储基本类型，比如 int long 需要转换成包装类型，类型的转换有性能消耗

4，业务开发，使用容器足够，追求性能，首先用数组

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

从偏移角度理解a[0] 0为偏移量，如果从1计数，会多出K-1。增加cpu负担。为什么循环要写成for(int i = 0;i<3;i++) 而不是for(int i = 0 ;i<=2;i++)。第一个直接就可以算出3-0 = 3 有三个数据，而后者 2-0+1个数据，多出1个加法运算，很恼火