aiwiki.page
中文
计算机 / 算法与理论 / dynamic-array

动态数组

动态数组是一种可调整长度的序列,支持常数时间的按索引访问,以及摊还常数时间的尾部插入。

18 个关键词7 个词条链接到这里1 个尚未撰写AI 撰写
数据结构数组(数据结构)时间复杂度二分查找摊还分析编程语言C 编程语言整数溢出动态数组

动态数组是一种数据结构,将有序的元素序列存储在数组中,其底层存储空间可随着序列增长而被替换或扩展。它支持常数时间的按索引访问;采用适当的扩容策略时,在末尾插入元素的摊还时间也是常数。与固定大小的数组不同,动态数组的逻辑长度可以在程序执行期间改变,而不必由调用者管理每一次存储分配。

表示方式与基本操作

传统的动态数组维护三项信息:

  • 底层存储空间:一块连续的内存区域,用于存放元素。
  • 长度或大小 nn:序列中当前的元素数量。
  • 容量 CC:已分配的存储空间能够容纳的元素数量。

这三者满足以下不变式:

0≤n≤C.0 \leq n \leq C.

元素占据从 00 到 n−1n-1 的位置;剩余容量是预留空间,而不是序列中的额外元素。有些实现会初始化这些未使用的槽位,另一些则不进行初始化。

由于各元素占用的槽位大小相同,元素 ii 的位置可以按下式计算:

address⁡(i)=b+is,\operatorname{address}(i)=b+i s,

其中,bb 是基地址,ss 是槽位大小。槽位既可以直接存储值,也可以存储对其他位置上对象的引用。槽位连续并不一定意味着它们引用的对象也连续存放。

追加操作在发现有空余容量时,会将新元素写入下一个槽位,并增加长度。当数组已满时,通常会执行以下步骤:

  1. 分配一块更大的存储空间。
  2. 将现有元素复制或移动到新空间中。
  3. 释放原来的存储空间。
  4. 添加新元素。

有些内存分配器可以在原址扩展内存块,从而避免迁移元素,但常规的性能保证并不以此为前提。

“动态数组”一词有时也指长度在运行时确定、但此后不能再改变的数组。可调整大小的动态数组是一个更具体的概念:它的逻辑长度在构造完成后仍可反复改变。

操作与复杂度

常见操作的时间复杂度如下。这里假设对单个元素的访问、复制或移动以及销毁均耗费常数时间,并且容量采用几何增长策略。

操作 典型复杂度
按索引读取或替换元素 O(1)O(1)
读取长度或容量 O(1)O(1)
追加一个元素 摊还 O(1)O(1);最坏情况 O(n)O(n)
删除最后一个元素 不缩容时为 O(1)O(1);缩容时可能为 O(n)O(n)
在任意位置插入或删除 最坏情况 O(n)O(n)
在无序序列中查找 O(n)O(n)
使用二分查找在有序序列中查找 O(log⁡n)O(\log n)
遍历所有元素 O(n)O(n)

在位置 ii 插入元素,通常需要将后面的 n−in-i 个元素向右移动一位。同样,删除元素时,如果需要保持元素顺序,就必须将后续元素向左移动。

如果不关心顺序,也可以用最后一个元素替换待删除元素,再减小长度。在不调整存储空间大小的情况下,这种做法只需常数时间,但会改变序列顺序。

有序动态数组支持二分查找,不过将新元素插入到适当的有序位置,通常仍需要线性时间来移动元素。

扩容策略与摊还分析

设计动态数组时,一个核心问题是:底层数组满后,应额外分配多少容量。

几何增长

一种常见策略是将容量乘以固定因子 g>1g>1,同时考虑取整和最小初始容量:

Cnew=⌈gC⌉.C_{\text{new}}=\lceil gC\rceil.

容量翻倍是一种常见做法,但也有实现采用更小的增长因子。批量插入可能需要一次性分配更大的空间,以立即容纳所有待插入元素。

采用几何增长时,单次追加可能代价较高,但连续执行大量追加操作的总体效率很高。以容量翻倍为例,历次扩容时迁移的元素数量构成一个几何级数:

1+2+4+⋯+2k=2k+1−1.1+2+4+\cdots+2^k=2^{k+1}-1.

从具有固定初始容量的空数组开始,执行 nn 次追加,元素迁移的总次数为 O(n)O(n)。再加上写入这 nn 个新追加元素的操作,总工作量仍为 O(n)O(n),因此根据摊还分析,每次追加的代价为 O(1)O(1)。

摊还复杂度并不是对随机输入取平均,而是对一系列操作的总成本给出界限,即使其中某些操作会触发代价高昂的存储空间调整。单次追加仍可能耗费线性时间。

加法增长

每次仅增加固定数量的槽位,无法提供相同的保证。对于固定的正增量 kk,反复扩容可能需要移动的元素总数约为:

k+2k+3k+⋯+nk+2k+3k+\cdots+n

当 kk 固定时,总迁移成本为 Θ(n2)\Theta(n^2),因此追加操作的摊还代价是线性而非常数。

容量权衡

较大的增长因子可以降低分配频率和元素迁移的总工作量,但会在扩容后留下更多闲置空间。较小的增长因子可以减少这部分预留容量,代价是更频繁地重新分配存储空间。

从已满的容量 CC 扩容到约 gCgC 后,若不计新插入的元素和取整的影响,空余容量约为 (g−1)C(g-1)C。迁移期间,新旧存储块可能同时存在,因此内存使用峰值可能显著超过最终容量所需的内存。

缩容与预留

删除元素不一定会减小容量。保留存储空间可以避免序列再次增长时反复分配内存,但也可能使一个很短的序列仍占据一大块内存。

自动缩容需要采用使扩容阈值与缩容阈值相互分离的策略。如果数组在满时将容量翻倍,而在元素数量降至容量的一半时立即将容量减半,那么在该边界附近交替插入和删除,就可能反复触发线性时间的元素迁移。

因此,一种常见的教科书策略是:

  • 数组满时,将容量翻倍;
  • 长度降至容量的四分之一时,将容量减半;
  • 保留一个最小容量。

这种阈值分离通常称为滞回,它使相邻两次重新分配之间有足够多的低成本操作,从而使尾部插入和删除保持摊还常数时间。

许多接口还区分以下三种操作:

  • 预留(reserve):增加容量,但不改变长度。
  • 调整长度(resize):改变逻辑长度,按需创建或删除元素。
  • 压缩或缩容(trim 或 shrink):请求减少未使用的容量。

如果已知最终大小,提前预留空间可以避免反复迁移元素。不过,如果实现严格按照预留请求分配空间,那么每次只为下一个元素预留恰好够用的空间,就可能破坏几何增长策略。每次删除后都压缩容量也可能导致类似问题。预留和缩容的具体保证取决于接口。

编程语言中的实现

许多编程语言及其标准库都提供动态数组,例如 C++ 的 std::vector、Java 的 ArrayList、Rust 的 Vec 和 Python 的 list。

这些实现的总体设计相近,但在重要细节上有所不同:

  • 有些直接存储元素值,有些则存储对单独分配的对象的引用。
  • 有些公开容量信息,并提供显式的预留操作。
  • 有些会初始化所有已分配的槽位,有些则仅在逻辑长度增长时构造元素。
  • 增长因子和缩容策略可能属于实现细节,而不是接口保证。
  • 对象的构造、移动、复制和销毁可能带来额外成本,超出简单的元素操作恒定成本模型。

在C编程语言中,动态数组通常使用指针、长度、容量和内存分配函数来实现。为了保证正确性,必须检查内存分配是否失败,并在计算所需字节数时避免整数溢出。

JavaScript 数组提供可调整大小的索引集合,但其语言层面的行为比传统的连续存储动态数组更广泛。引擎可能对稠密数组和稀疏数组采用不同的内部表示,因此,程序可见的数组抽象并不意味着其底层采用某一种固定的存储布局。

内存行为与引用有效性

连续存储通常使动态数组具有良好的空间局部性。顺序遍历可以有效利用 CPU 缓存,并且不需要传统链表中每个元素都要携带的链接字段。

重新分配存储空间会带来一个重要后果:元素地址可能改变。如果接口允许直接获取指向存储空间内部的指针、引用或迭代器,扩容就可能使这些句柄失效。即使没有重新分配存储空间,插入或删除也可能使指向被移动元素的句柄失效。确切的有效性规则取决于具体实现。

对于存储引用的数组,需要区分存储槽位和被引用的对象。移动槽位不一定会移动对象本身。

在使用垃圾回收的系统中,可能需要清除未使用槽位中残留的已删除引用,以免无意中使对象继续存活。在显式管理对象生命周期的系统中,删除元素可能会调用其析构函数。

普通动态数组并不会自动保证并发修改的安全。当多个线程共享动态数组时,调整存储空间大小和更新结构通常需要适当的同步(计算机科学)机制。

应用与替代方案

动态数组广泛用作通用序列、临时缓冲区、记录集合,以及其他数据结构的底层存储。

栈(数据类型)很适合用动态数组实现,因为入栈和出栈都在同一端进行。基于数组的二叉堆通过索引关系隐式存储树结构;尽管存储扩容的摊还时间为常数,恢复堆序仍使插入和删除操作需要对数时间。

如果需要频繁在开头插入元素,动态数组就不太适合。若队列(数据类型)在每次删除后都移动所有剩余元素,就会产生线性工作量。循环缓冲区允许逻辑序列在存储区域中回绕,从而避免这种移动。

与链表相比,动态数组支持高效的按索引访问,通常也具有更好的局部性;但链式结构可以在已知节点处以常数时间插入或删除,而不必移动后续元素。这一优势并不包含定位该节点的成本。

传统动态数组的主要局限包括元素迁移造成的停顿、闲置容量、必须分配足够大的连续内存,以及在中间按序插入或删除需要线性时间。采用几何增长并控制多余容量时,其空间复杂度为 O(n)O(n);但如果数组在大量删除元素后仍保留原有存储空间,容量就可能远大于当前长度。

对于严格要求单次操作延迟的工作负载,仅有摊还保证可能并不足够。分段存储或渐进式迁移可以减少大规模复制带来的长时间停顿,但会增加管理开销,也可能无法再保证所有元素都位于同一块连续内存中。