illegalCreed

中文

English

中文

English

Appearance

入门：连续内存、随机访问与动态扩容 ​

基于通用数据结构概念 · 核于 2026-07

速查 ​

  • 定义：数组是一段连续内存里顺序存放同类型元素的线性结构，靠**下标（从 0 开始）**在 O(1) 时间随机访问。
  • 地址公式：元素地址 = 基地址 + 下标 × 单元素大小——这是 O(1) 访问的物理根源，也决定了内存必须连续。
  • 核心复杂度：访问/按下标改 O(1)；查找（无序）O(n)、（有序）O(log n) 二分；插入/删除 O(n)（中间位置要搬移后续元素）；尾部插入/删除 O(1)（动态数组摊还）。
  • 静态 vs 动态：静态数组容量编译期固定（C int a[10]）；动态数组（C++ vector / Java ArrayList / JS Array / Python list）满则几何扩容（通常 ×2），单次扩容 O(n) 但摊还 O(1)。
  • 容量 vs 长度：动态数组有 capacity（已申请空间）和 size/length（实际元素数）两个量——扩容发生在 size == capacity 时，capacity 通常对用户透明。
  • 几何扩容的摊还分析：插入 n 个元素总搬移次数 1+2+4+...+n ≈ 2n，摊还每次 O(1)；扩容因子越小（如 1.5）内存浪费越少但扩容更频繁，因子越大（如 2）反之。
  • JS Array / Python list 不是「真」数组：JS Array 是动态数组（引擎内部多为连续 + 哈希混合，稀疏数组退化）；Python list 是对象指针数组（元素是引用，指针连续，对象本身在堆上分散）——仍保留 O(1) 随机访问与连续缓存优势。
  • 与链表的核心差异：数组 O(1) 访问 / O(n) 增删；链表反过来 O(n) 访问 / O(1) 增删（已知节点）——选型看「访问多还是增删多」+「是否要随机访问」。
  • 数组是万物的底层：栈/队列（两端）、堆（完全二叉树下标映射 2i+1/2i+2）、哈希表（开放寻址法）、字符串（字符数组）都以数组为物理载体。
  • 进阶顺序：双指针与滑动窗口 → 前缀和与差分 → 矩阵遍历 → 参考。

一、物理模型：为什么是 O(1) 随机访问 ​

数组的本质是「一段连续内存 + 一个基地址」。CPU 访问第 i 个元素时，硬件直接算地址：

addr(a[i]) = base + i × sizeof(element)

这个计算是常数时间的算术运算，不依赖 n——这就是 O(1) 随机访问的物理根源。它也派生出三个推论：

  1. 内存必须连续：不连续就没法用单一基地址 + 偏移定位，所以申请大数组可能因内存碎片化失败。
  2. 元素必须等长（或等长指针）：定长数组要求元素类型大小固定；Python list 通过「存指针」让变长对象也能进「数组」（指针等长，对象在堆上）。
  3. 缓存友好：连续内存会整块载入 CPU 缓存行（通常 64 字节），顺序遍历时后续元素已在缓存里——这是数组顺序遍历比链表快一个数量级的原因，即使两者大 O 相同。

二、核心复杂度 ​

操作数组链表（单链表）
按下标访问 a[i]O(1)O(n)
头部插入/删除O(n)O(1)
尾部插入/删除O(1)（动态摊还）/ O(1)（静态已知容量）O(1)（带尾指针）/ O(n)（无尾指针）
中间插入/删除O(n)（搬移后续）O(1)（已知节点，只改指针）
查找（无序）O(n)O(n)
查找（有序，二分）O(log n)O(n)（不能二分，不能随机访问）

记住一句话：「访问多、要二分、要随机访问 → 数组；增删多、尤其头部增删 → 链表」。

三、静态数组与动态数组 ​

静态数组 ​

容量在编译期/声明时固定，不能改：

c
int a[10];        // C：固定 10 个 int，越界写是未定义行为
int b[] = {1,2,3}; // 容量由初始化确定为 3

静态数组的好处是零分配开销、内存紧凑；坏处是容量写死后超容没法办——要么预估过大浪费内存，要么预估不够直接溢出。

动态数组 ​

动态数组在「满则扩容」策略下兼具可变长度，是各语言的主力数组类型：

语言动态数组类型扩容策略（典型）
C++std::vector×2（GCC）/ ×1.5（MSVC）
JavaArrayList×1.5（oldCapacity + oldCapacity >> 1）
JavaScriptArray引擎实现（V8 通常约 ×1.5~2，与元素类型相关）
Pythonlist≈ ×1.125（含预留，公式 new = (n + (n >> 3) + 6) & ~3）
Goslice（底层为 runtime.growslice）<1024 时 ×2，≥1024 时 ×1.25

动态数组内部维护两个量：capacity（已申请的总槽位数）和 size/length（实际填了多少）。当 size == capacity 还要插入时，触发扩容：

js
// 动态数组扩容的伪代码
function pushBack(arr, x) {
  if (arr.size === arr.capacity) {
    // 几何扩容：申请新块（×2），拷贝旧元素，释放旧块
    const newCap = arr.capacity === 0 ? 1 : arr.capacity * 2;
    const newArr = allocate(newCap);
    copy(newArr, arr.data, arr.size);
    arr.data = newArr;
    arr.capacity = newCap;
  }
  arr.data[arr.size++] = x;
}

四、摊还分析：为什么尾插是 O(1) ​

单次扩容要拷贝全部元素，是 O(n)；但摊到「连续插入 n 个元素」上，总搬移次数是几何级数：

插入第 1,2,3,5,9,... 个时各触发一次扩容，搬移 1,2,4,8,... 次
总搬移 ≈ 1 + 2 + 4 + ... + n/2 + n ≈ 2n

n 次插入总共约 2n 次元素搬移，摊还每次 2n / n = O(1)。这就是「动态数组尾插摊还 O(1)」的证明依据。注意：最坏单次仍是 O(n)（恰好触发扩容那次），所以对单次延迟敏感的场景（实时系统）要注意。

扩容因子的取舍 ​

  • ×2（C++ GCC、V8 常见）：扩容稀疏，单次拷贝多，但峰值内存 ~2 倍元素数。
  • ×1.5（MSVC、Java ArrayList）：峰值内存 ~1.5 倍，扩容更频繁。
  • 折中点是让「释放的旧块」有机会被下次扩容复用——×1.5 时，前两次释放的块加起来恰好够下一次用（1.5n + 0.5n 之前的 = ...），内存碎片更少，这是 MSVC 选 1.5 的工程理由。

五、与链表怎么选 ​

维度数组（动态）链表
随机访问 a[i]O(1) ✅O(n) ❌
头部增删O(n) ❌O(1) ✅
尾部增删O(1)（摊还）✅O(1)（带尾指针）✅
中间增删（已知位置）O(n)O(1) ✅
顺序遍历缓存友好（连续内存）✅差（节点分散）❌
内存开销仅数据每节点多一个/两个指针
二分查找支持 ✅不支持 ❌

选型口诀：「读多写少 / 要随机访问 / 要二分 / 要排序 → 数组；写多读少 / 频繁头插 / 大小不确定且频繁中间插删 → 链表」。实际工程里动态数组（vector/ArrayList/JS Array）是绝对主力，链表多用于特定场景（LRU 缓存、链式哈希桶、多项式）。

六、JS/Python 的「数组」是真数组吗 ​

  • JavaScript Array：规范上是动态数组（对象的一种特例），引擎（V8）对连续同质元素用真连续数组（PACKED_SMI_ELEMENTS/PACKED_DOUBLE_ELEMENTS）优化；一旦塞入异质类型或稀疏下标就退化（HOLEY_ELEMENTS/字典模式）。日常用法下它是 O(1) 访问的连续数组，稀疏时退化——所以别 a[1000000] = 1 当稀疏数组用。
  • Python list：本质是对象指针数组——存的是指向 PyObject 的指针（指针等长、连续），对象本身在堆上分散。所以「list 是动态数组」对（指针层面连续、O(1) 访问），但元素本身不连续（缓存命只到指针层）。这也解释了 Python list 比 numpy array 慢——numpy 用真连续定长数组。
  • Go slice：底层是真连续数组，slice 是「指针 + 长度 + 容量」的三元组，扩容由 runtime.growslice 处理。

下一步 ​

理解了数组的物理模型与扩容后，下一步是数组上最高频的两类算法套路——双指针与滑动窗口，它们把 O(n²) 的暴力优化到 O(n)，见双指针与滑动窗口。