数组：面试中的疑难点

小憩第54篇原创文章

只要你是程序员就注定离不开算法。

现实一点的说，就是面试，进大厂，升职加薪。

只此一点就不得不使我们将算法列为重点成长对象。

从基础到进阶，有关职场算法进阶都能够在这里找到，欢迎加入一起成长。

算法之旅:复杂度分析

主要内容

1. 本质

2. 在内存中的存储逻辑

3. 随机访问与查找的区别

4. 插入优化

5. 删除优化

6. 越界问题

7. 对比

本质

数组相信大家都不陌生，我们几乎每天都有用到数组，不管是直接由我们自己创建的，还是间接使用 sdk 内部提供的数据结构，底层都或多或少的离不开数据的使用。

那么数据到底是什么呢？

比较官方的定义是：它使用一块 连续的存储空间 来存储 相同类型 的数据，它是一个 线性的数据结构 。

关键点有三

1. 连续的存储空间

2. 相同的类型

3. 线性数据结构

连续的存储空间，它这个限制是什么意思呢？

假如我们可用内存只有 100KB ，但它并不是连续的，它们零散在内存的各个地方；如果现在我要申请内存 100KB 大小的数组，这个时候虽然机器可用内存有 100KB 剩余，但这个数组并不能申请成功，原因就是当前机器剩余的内存并不是一个连续的内存。

相同类型就很好理解了，因为同一个数组只能存储一种数据类型的数据。

线性数据结构，简单的理解就是将数据依次排成一列，每个线性表上的数据都最多只要两个方向，前与后。有这特性的还有链表、栈、队列等。

当然与线性结构相反的就是非线性结构，对应的就是图、二叉树、堆等。因为他们数据之间的并非只有前后两个方向。

内存表现

了解完本质，再来了解数组在内存中的表现。

我们都知道数组具有随机访问的特性。那么这一特性具体是如何而来的呢？

假设我们有一个数组 a ，它存储的类型为 int ，数组大小为 5 。

那么它在内存中的表现大概会是这样的。

所以数组中的元素存储在内存中都是在一块连续的地址中。对应不同位置的数据有相关的计算公式

a[index] = base_address + data_type_size  * index

这里的 base_address 为 1000 ，由于是 int 类型的数据，所以 data_type_size 为 4 。

我们访问不同的数组下标就能快速定位到当前数组下标对应的内存地址。这也是数组能够支持快速随机访问的原因。

那么我们想一个问题，数组为什么要以 0 为起始下标呢？

我们不妨假设数组以 1 作为起始下标，那么上面的公式就变成这样

a[index] = base_address + data_type_size  * (index - 1)

相比于之前的公式，多了一个减法运算。大家不要小瞧这个减法运算，虽然单次耗时很少，但在内存中，如果每一次计算数组的内存地址时都需要加上一个额外的减法运算，那么这个耗时将不可被忽略，严重影响其性能。

回到快速随机访问，让我想到一个普遍误区。

有的人可能在面试中会说，数组适合查找，链表适合插入与删除；数组查找的时间复杂度为 O(1) 。

其实数组查找的复杂度并不是 O(1) ，即使一个有序数组，使用二分查找它的时间复杂度也只是 O(logn) 。

所以正确的表达应该是数组适合随机访问，它的时间复杂度为 O(1) 。

插入与删除

为什么数组不适合插入与删除操作？

这就跟它的结构密切相关，由于数组是一块连续的内存地址，如果我们要向其中插入一块数组，将必须改变当前插入点的数据与插入点之后的所用数据。

这个改变会发生什么呢？

第一点需要替换插入点的数据；第二点需要移动插入点之后的所有数据在内存中的地址位置。

为了达到这个效果就不得不将后面的数据重新找的对应的位置再进行赋值。

例如一个长度为 n 的数组，现在我们需要将一个数据插入到第 k 个位置上，那么我们需要将 k~n 个数据依次往后移动一位。那么这个时间复杂度为 O(n-k) 。

如果插入到最后一个位置，则不需要移动数据，时间复杂度为 O(1) 。

如果是第一个位置，那么需要移动所用的数据，时间复杂度为 O(n) 。

由于插入的位置概率是相同的，所以插入的平均复杂度为

(1 + 2 + .. + (n-k) + .. + n) / n = O(n)

值得一提的是，如果数据不需要有序，我们可以优化这个插入的时间复杂度。

简单的理解就是，如果我们需要在第 k 个位置上插入数据，并不需要移动后续的数据，因为不需要保证数据的顺序，我们只需将第 k 个位置的数据替换成插入的数据，然后再将第 k 个位置的原有数据添加到数组的最末尾。

间接相当于插入到最后一个位置，所以时间复杂度缩小为 O(1) 。

数组的删除与插入类似，如果你需要删除第 k 个位置的数据，需要将 k~n 个数据向前移动一位。所以删除的平均时间复杂度也是为 O(n) .

如果删除的过程中并不需要立即清除数据，我们也可以对删除操作进行优化。

每当我们进行删除数据的时候，并不立即删除当前位置的数据，而是对当前位置进行标记，等到标记的数量达到一定的程度之后，我们再对标记的数据进行统一的删除操作。这样就减少在删除操作过程中移动数据的次数。

不知道大家有没有听说过 JVM 的标记清除法。这就是数据算法的一种应用。

那么标记的数据对于数组的插入与查找会有什么影响呢？

针对插入，遇到有标记的数据直接插入替换就好了，也不需要再移动数据。

针对查找，遇到有标记的数据直接跳过或者认为数据不存在即可。

越界

数组越界应该都有遇到过，有了上面的基础，再来看数组越界就很简单了。

由于我们访问数据对应下标的数据都是通过下面的公式来获取对应内存地址中的数据。

a[index] = base_address + data_type_size  * index

所以一旦访问的 index 不在数组的内存地址块访问的范围内。就会导致访问的数据出错，将结果映射到其它对象的内存地址上。

为了防止这个问题，对于 Java 来说，就会抛出异常

java.lang.ArrayIndexOutOfBoundsException

这也是保证程序正常运行的一种措施。一旦没有这种检测措施，你可能并不知道你的数据为什么异常。

对比

针对于数据的封装有很多种，比如 ArrayList 。

而对于这种容器类的封装，它们的优势在于

1. 支持动态扩容，不需要手动进行移动数据

2. 对数组的操作进行了细节封装，方便统一使用

那么我们是不是就不需要使用数组了呢？

其实并不是，如果你能够确定你的数据量大小，就可以直接使用数组来固定数组的大小，从而减少内存的消耗。当然 ArrayList 也支持固定初始化的容器大小。

另一方面，对于 ArrayList 无法存储 Java 的基本类型数据，它需要封装成 Interge、Long 等类型的数据。而这种数据在使用的过程中需要额外的装箱与解箱，会造成一定的性能问题。

如果你经验丰富，对于多维问题，可能多维数组更适合使用。因为它对于表示多维数据之间的关系非常友好。

好了，以上就是关于数组的全部内容，总的来说，数组是一个轻量的数据结构，如果你在使用的过程中不需要复杂的操作，推荐考虑使用数组，它能够帮你减少不必要的内存消耗。

我在Github上建了一个仓库，之后有关算法的内容都会汇总到这里，大家可以关注一下。

https://github.com/idisfkj/daily_algorithm

推荐

Android init 启动

Kotlin协程实现原理:Suspend&CoroutineContext

Android Hilt实战初体验: Dagger替换成Hilt