01.数组深入浅出分析

01.数组深入浅出分析

目录介绍

• 01.数组的设计介绍
  • 1.1 数组内存设计
  • 1.2 一维和二维数组
  • 1.3 数组复杂度思考
• 02.数组的优缺点
  • 2.1 数组的优点
  • 2.2 数组的缺点
• 03.数组使用场景
  • 3.1 那些使用场景
  • 3.2 那些集合用数组
• 04.线性表和非线性表
  • 4.1 什么是线性表
  • 4.2 什么是非线性表
• 05.数组的访问
  • 5.1 设计访问元素
  • 5.2 数组地址值设计
  • 5.3 用例子来理解
• 06.数组低效插入
  • 6.1 插入操作复杂度
  • 6.2 分析插入效率低
  • 6.3 如何提高插入效率
• 07.数组低效删除
  • 7.1 普通删除元素
  • 7.2 集中删除多个元素
• 08.容器和数组
  • 8.1 问题思考分析
  • 8.2 集合的优势
  • 8.3 两者特性比较
  • 8.4 数组和集合总结
  • 8.5 使用场景
• 09.为何数组从0开始
  • 9.1 下标的设计
  • 9.2 从0开始访问
  • 9.3 历史原因导致
• 10.总结和概括
  • 10.1 整体总结一下
  • 10.2 更多内容推荐

01.什么是数组

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

数组的初始化。Java中的数组必须先初始化，然后才能使用。所谓初始化：就是为数组中的数组元素分配内存空间，并为每个数组元素赋值。

image

1.1 数组内存设计

数据存储中的连续空间是指数据在物理存储介质（如硬盘、内存等）上被连续地存储。这意味着数据在存储介质上的存储位置是相邻的，没有间隔或间隔很小。

连续空间的使用有以下几个原因：

1. 读写效率：在连续空间中存储数据可以提高读写操作的效率。
2. 内存分配：在内存中，连续空间的使用可以简化内存分配和管理。当数据在内存中连续存储时，可以通过指针和偏移量等方式轻松访问和操作数据。
3. 缓存利用：现代计算机系统通常具有缓存层次结构，连续存储可以提高缓存的利用率，因为连续的数据通常会更好地利用缓存行。

image

1.2 一维和二维数组

一维数组表示代码如下

//数组一定要确定长度，连续内存空间
int[] arr1 = new int[5];
int[] arr2 = {1,2,3,4,5};

image

二维数组定义格式

• 数据类型 变量名 = new 数据类型m;
• m表示这个二维数组有多少个一维数组
• n表示每一个一维数组的元素个数

举例:

int[][] arr = new int[3][2];
定义了一个二维数组arr
这个二维数组有3个一维数组，名称是arr[0],arr[1],arr[2]
每个一维数组有2个元素，可以通过arr[m][n]来获取,表示获取第m+1个一维数组的第n+1个元素

image

1.3 数组复杂度思考

数组和链表的复杂度，很多人都回答说，“链表适合插入、删除，时间复杂度O(1)；数组适合查找，查找时间复杂度为 O(1)”。

实际上，这种表述是不准确的。数组是适合查找操作，但是查找的时间复杂度并不为O(1)。即便是排好序的数组，你用二分查找，时间复杂度也是O(logn)。

所以，正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

02.数组的优缺点

2.1 数组的优点

1. 随机访问：数组通过索引可以快速访问和修改元素，时间复杂度为O(1)。这使得数组在需要频繁访问元素的场景中非常高效。
2. 连续存储：数组的元素在内存中是连续存储的，这有利于缓存的利用，提高访问效率。
3. 简单：数组的操作相对简单，可以快速进行插入、删除和搜索等操作。
4. 有序性：数组中的元素按照索引顺序排列，这使得数组在需要有序数据的场景中非常有用。

2.2 数组的缺点

1. 固定大小：数组的大小在创建时就确定，无法动态调整。如果需要存储的元素数量超过数组的初始大小，就需要重新分配更大的数组并进行数据复制，这可能会导致性能损失。
2. 插入和删除效率低：在数组中插入或删除元素时，需要移动其他元素来保持连续性，这可能导致较高的时间复杂度，尤其是在大规模数据的情况下。
3. 内存浪费：如果数组的大小远远超过实际存储的元素数量，会造成内存的浪费。
4. 不适用于关联性数据：数组适用于按索引访问元素的场景，但对于需要关联性数据的情况，使用其他数据结构（如字典或哈希表）可能更合适。

详细一点来说：数组作为数据存储结构有一定的缺陷。在无序数组中，搜索性能差，在有序数组中，插入效率又很低，而且这两种数组的删除效率都很低，并且数组在创建后，其大小是固定了，设置的过大会造成内存的浪费，过小又不能满足数据量的存储。

连续的内存空间和相同类型的数据。正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

03.数组使用场景

3.1 那些使用场景

1.数组适用于需要按照索引顺序存储和访问元素的场景。例如，存储学生成绩、员工工资等有序数据时，可以使用数组。

2.由于数组的元素在内存中是连续存储的，这有利于缓存的利用。在需要频繁访问数组元素的场景中，数组可以提供更好的性能。

3.数组是一种通用的数据结构，能用来实现栈、队列等很多数据结构。

3.2 那些集合用数组

许多集合类的底层实现都使用了数组，例如 ArrayList、Vector、ArrayDeque、PriorityQueue 等。数组提供了高效的随机访问能力，而集合类在此基础上增加了动态扩容、线程安全、排序等功能。

1. ArrayList。底层实现：动态数组。需要频繁访问元素，但插入和删除操作较少的场景。
2. Stack。底层实现：基于 数组 实现。需要实现栈操作的场景。
3. ArrayDeque。底层实现：循环数组。需要高效的双端队列操作。
4. CopyOnWriteArrayList。底层实现：动态数组。
5. String 的字符数组。底层实现：char[] 数组。字符串操作。

04.线性表和非线性表

4.1 什么是线性表

用于存储一组有序的元素。在线性表中，元素之间存在顺序关系，每个元素都有唯一的前驱和后继元素（除了第一个元素和最后一个元素）。线性表中的元素通常按照其插入顺序排列。

数据排成像一条线一样的结构。每个线性表上的数据最多只有前后两个方向。除了数组，链表、队列、栈也是线性表结构。

4.2 什么是非线性表

在非线性表中，元素之间的关系不是简单的前后顺序，而是以其他方式相互连接或组织的。非线性表中的元素之间可以存在多种关系，如父子关系、兄弟关系等，不受严格的顺序限制。

非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。

05.数组的访问

5.1 设计访问元素

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

1. 使用方括号[]来访问数组元素，后面跟上要访问的元素的下标。例如，array5表示访问数组array中的第六个元素。
2. 数组会根据给定的下标计算出元素在内存中的地址，这个是元素的地址值。
3. 最后通过元素地址值直接精确找到元素值。

通过下标访问数组元素的时间复杂度是O(1)，你可以通过简单的地址计算来直接访问。

5.2 数组地址值设计

在数组中，元素的地址值是根据数组的起始地址和元素的下标计算得出的。数组的起始地址是数组在内存中的首地址，而元素的下标表示元素在数组中的位置。

当访问数组元素时，计算元素的地址值的一般公式如下：元素地址 = 数组起始地址 + (元素下标 * 单个元素的大小)

单个元素的大小是指数组中每个元素所占用的字节数。通过将元素的下标乘以单个元素的大小，可以得到元素在数组中的偏移量。然后，将数组的起始地址与偏移量相加，即可得到元素的地址值。

这种设计使得数组中的元素在内存中是连续存储的，因为每个元素的地址都是根据前一个元素的地址计算得出的。

5.3 用例子来理解

我们拿一个长度为 10 的 int 类型的数组 int a = new int10 来举例。在我画的这个图中，计算机给数组 a10，分配了一块连续内存空间 1000～1039，其中，内存块的首地址为 base_address = 1000。

计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址，最后找到元素。

int 类型的数据，字节的大小是4
a[0] = 4，那么，地址值 = 1000 + 1 * 4
a[1] = 5，那么，地址值 = 1000 + 2 * 4
a[2] = 7，那么，地址值 = 1000 + 3 * 4

06.数组低效插入

6.1 插入操作复杂度

假设数组的长度为 n，现在，如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来，给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一位。那插入操作的时间复杂度是多少呢？

1. 如果在数组的末尾插入元素，那就不需要移动数据了，这时的时间复杂度为 O(1)。
2. 如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是 O(n)。
3. 如果在数组中间插入元素也需要将插入位置后的元素向后移动，以便为新元素腾出空间。在这种情况下，时间复杂度也是 O(n)，因为需要移动 n/2 个元素（平均情况）。

因为我们在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为 (1+2+…n)/n=O(n)。建议：因此，在频繁执行插入操作的情况下，可能需要考虑使用其他数据结构，如链表，以避免频繁的元素移动。

6.2 分析插入效率低

数组插入数据效率低的原因主要是由于数组的内部实现方式。在大多数编程语言中，数组是一种连续的内存块，插入数据需要做：

1. 移动元素：由于数组是连续的内存块，插入数据会导致插入位置之后的元素都需要向后移动，以腾出空间给新插入的元素。
2. 空间开销：如果数组已经满了，无法容纳更多的元素，那么需要重新分配更大的内存空间，并将原有的元素复制到新的内存空间中。
3. 内存拷贝：元素移动实际上是一种内存拷贝操作，需要将一部分元素复制到新的位置。这种内存拷贝操作会消耗额外的时间，尤其是在数组规模较大时，影响插入操作的效率。

这三个操作都需要耗费时间，特别是在大型数组中插入数据时，效率会更低。因此，频繁地在数组中插入数据可能会导致性能下降。如果需要频繁地进行插入操作，可以考虑使用其他数据结构来提高性能。

6.3 如何提高插入效率

如果数组中的数据是有序的，我们在某个位置插入一个新的元素时，就必须按照刚才的方法搬移+k+之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。

如果要将某个数组插入到第 k 个位置，为了避免大规模的数据搬移，我们还有一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。

为了更好地理解，我们举一个例子。假设数组 a10中存储了如下 5 个元素：a，b，c，d，e。

我们现在需要将元素 x 插入到第 3 个位置。我们只需要将 c 放入到 a5，将 a2赋值为 x 即可。最后，数组中的元素如下： a，b，x，d，e，c。

利用这种处理技巧，在特定场景下，在第 k 个位置插入一个元素的时间复杂度就会降为 O(1)。这个处理思想在快排中也会用到。

07.数组低效删除

7.1 普通删除元素

跟插入数据类似，如果我们要删除第k个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。

和插入类似，如果删除数组末尾的数据，则最好情况时间复杂度为 O(1)；如果删除开头的数据，则最坏情况时间复杂度为 O(n)；平均情况时间复杂度也为 O(n)。

7.2 集中删除多个元素

实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率是不是会提高很多呢？

我们继续来看例子。数组 a10中存储了 8 个元素：a，b，c，d，e，f，g，h。现在，我们要依次删除 a，b，c 三个元素。

为了避免 d，e，f，g，h+这几个数据会被搬移三次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。

核心思想是，使用缓冲区：在删除操作频繁的情况下，可以考虑使用缓冲区，将多个删除操作合并为一次性的批量删除，减少元素移动次数，提高效率。

如果你了解 JVM，你会发现，这不就是JVM标记清除垃圾回收算法的核心思想吗？没错，数据结构和算法的魅力就在于此，很多时候我们并不是要去死记硬背某个数据结构或者算法，而是要学习它背后的思想和处理技巧，这些东西才是最有价值的。

如果你细心留意，不管是在软件开发还是架构设计中，总能找到某些算法和数据结构的影子。

08.容器和数组

8.1 问题思考分析

针对数组类型，很多语言都提供了容器类，比如 Java 中的 ArrayList、C++ 中的 vector。在项目开发中，什么时候适合用数组，什么时候适合用容器呢？

这里我拿 Java 语言来举例。如果你是 Java 工程师，几乎天天都在用 ArrayList，对它应该非常熟悉。那它与数组相比，到底有哪些优势呢？

8.2 集合的优势

个人觉得，ArrayList 最大的优势就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外，它还有一个优势，就是支持动态扩容。

数组本身在定义的时候需要预先指定大小，因为需要分配连续的内存空间。如果我们申请了大小为 10 的数组，当第 11 个数据需要存储到数组中时，我们就需要重新分配一块更大的空间，将原来的数据复制过去，然后再将新的数据插入。

如果使用 ArrayList，我们就完全不需要关心底层的扩容逻辑，ArrayList 已经帮我们实现好了。每次存储空间不够的时候，它都会将空间自动扩容为 1.5+倍大小。

不过，这里需要注意一点，因为扩容操作涉及内存申请和数据搬移，是比较耗时的。所以，如果事先能确定需要存储的数据大小，最好在创建 ArrayList 的时候事先指定数据大小。比如我们要从数据库中取出 10000 条数据放入 ArrayList。

8.3 两者特性比较

8.4 数组和集合总结

数组：

• 数据量固定且已知。
• 需要高效的随机访问。
• 对内存占用有严格要求（如嵌入式系统）。
• 示例：存储一周的天数、图像像素数据等。

容器：

• 数据量动态变化。
• 需要频繁插入、删除或修改数据。
• 需要高级功能（如排序、查找、遍历等）。
• 示例：存储用户输入、管理动态列表、实现复杂数据结构等。

作为高级语言编程者，是不是数组就无用武之地了呢？当然不是，有些时候，用数组会更合适些，我总结了几点自己的经验。

• 1.Java+ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。
• 2.如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。
• 3.还有一个是个人的喜好，当要表示多维数组时，用数组往往会更加直观。比如 Object array；而用容器的话则需要这样定义：ArrayList<ArrayList >+array。

对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

09.为何数组从0开始

9.1 下标的设计

数组下标是编程中非常重要的概念，它们可以用于访问和修改数组中的元素。通过操作数组下标，可以对数组进行排序、搜索、删除和插入等操作，使得我们可以灵活地处理数据。

9.2 从0开始访问

为什么大多数编程语言中，数组要从 0 开始编号，而不是从 1 开始呢？+从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。

前面也讲到，如果用 a 来表示数组的首地址，a0 就是偏移为 0 的位置，也就是首地址，ak 就表示偏移 k 个 type_size 的位置，所以计算 ak 的内存地址只需要用这个公式：ak_address = base_address + k * type_size

但是，如果数组从+1+开始计数，那我们计算数组元素+a%5Bk%5D+的内存地址就会变为：ak_address = base_address + (k-1)*type_size

对比两个公式，我们不难发现，从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。

数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。

9.3 历史原因导致

上面解释得再多其实都算不上压倒性的证明，说数组起始编号非 0 开始不可。

所以我觉得最主要的原因可能是历史原因。 C 语言设计者用 0 开始计数数组下标，之后的 Java、JavaScript 等高级语言都效仿了 C 语言，或者说，为了在一定程度上减少 C 语言程序员学习 Java 的学习成本，因此继续沿用了从 0 开始计数的习惯。甚至还有一些语言支持负数下标，比如 Python。

在编程中，容器（Container） 和 数组（Array） 都是用于存储和管理数据的结构，但它们在功能、灵活性、性能和使用场景上有显著的区别。

10.总结和概括

10.1 整体总结一下

• 1.0 什么是数组：数组是线性表结构，存储相同类型的数据。然后数据必须先初始化，存储数组是一段连续的内存空间。
• 1.1 为何数组存储要设计连续内存空间：1.连续内存空间可以提高读写效率；2.连续存储可以通过指针和偏移量轻松访问和操作数据；3.连续数据可以提高缓存的利用率。
• 1.3 数组和链表的区别：数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。
• 2.1 数组的优点：1.可以随机访问，通过索引访问元素时间复杂度O(1)；2.连续存储有利于缓存利用；3.操作简单；4.元素按照索引顺序排序
• 2.2 数组的缺点：1.数组创建是大小就确定无法动态调整；2.插入和删除效率低；3.数组很大存储实际元素少会导致内存浪费；4.无法存储关联性数据
• 3.1 数组有那些使用场景：适用于需要按照索引顺序存储和访问元素的场景。
• 3.2 哪些集合用到了数组：例如 ArrayList、Vector、ArrayDeque、PriorityQueue 等。数组提供了高效的随机访问能力，而集合类在此基础上增加了动态扩容、线程安全、排序等功能。
• 4.1 什么是线性表：在线性表中，元素之间存在顺序关系，每个元素都有唯一的前驱和后继元素。线性表中的元素通常按照其插入顺序排列。
• 4.2 什么是非线性表：元素之间的关系不是简单的前后顺序，而是以其他方式相互连接或组织的。可以存在多种关系，如父子关系、兄弟关系等，不受严格的顺序限制。
• 5.1 数组是如何实现根据下标随机访问元素：数组会根据给定的下标计算出元素在内存中的地址，这个是元素的地址值，最后通过元素地址值直接精确找到元素值。
• 5.2 地址值是如何设计的：当访问数组元素时，计算元素的地址值的一般公式如下：元素地址 = 数组起始地址 + (元素下标 * 单个元素的大小)
• 6.1 如何理解数组插入数据时间复杂度：如果在末尾插入数据则时间复杂度O(1)，如果在首位插入数据则时间复杂度O(n)，在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为 (1+2+…n)/n=O(n)。
• 6.2 数组插入效率低的原因：1.插入元素后，插入位置之后的元素都要挨个往后挪动；2.如果数组满了则需要创建新的空间，并且复制数据到新的存储空间。这两点是效率低原因
• 7.1 删除元素效率分析：要删除第k个位置的数据，为了内存的连续性，也需要搬移数据。
• 7.2 如何提高数组删除元素效率：使用缓冲区，在删除操作频繁的情况下，可以考虑使用缓冲区，将多个删除操作合并为一次性的批量删除，减少元素移动次数，提高效率。
• 8.1 思考一下数组和集合：在项目开发中，什么时候适合用数组，什么时候适合用容器呢？
• 8.2 集合相比数组的优势：最大的优势就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外，它还有一个优势，就是支持动态扩容。
• 9.1 数组下标的设计：它们可以用于访问和修改数组中的元素。通过操作数组下标，可以对数组进行排序、搜索、删除和插入等操作，使得我们可以灵活地处理数据。
• 9.2 如何理解数组从0开始编号：数组从0开始编号的概念最早出现在C语言中。在C语言中，数组的元素是通过偏移量来访问的，数组名本身就是数组首元素的地址。

10.2 更多内容推荐