1 / 4概念
Linear Structures
线性结构把元素排成一条序列,区别在于元素在内存里是否连续、插入删除是否移动、查找靠不靠哈希。判断标准不是“数组还是链表高级”,而是访问模式、更新位置、内存布局和是否需要顺序。
1 概念
1.1 一句话定义
线性结构是元素之间只有前驱/后继关系的容器:数组用连续内存和下标寻址,链表用节点指针串起来,栈/队列/双端队列约束访问端点,哈希表用哈希函数把键映射到桶以实现平均 O(1) 查找。
1.2 它解决什么问题
- 随机访问:数组用下标 O(1) 定位,是缓存、缓冲区、矩阵的基础。
- 频繁插删:链表在已知节点处 O(1) 接入/摘除,不需要搬移后续元素。
- 顺序约束:栈保证后进先出,队列保证先进先出,双端队列两端都可进出。
- 键值查找:哈希表把“按键找值”从 O(n) 降到平均 O(1),是字典、缓存、去重的默认结构。
1.3 不属于本页的内容
| 主题 | 去哪 |
|---|---|
| 二叉树、平衡树、B+ 树、堆 | Trees & Heaps |
| 邻接表、邻接矩阵、并查集 | Graph Structures |
| 排序与二分查找 | Sorting & Searching |
| 渐进记号与摊还分析 | Complexity Analysis |
| 并发容器、锁与无锁队列 | 并发与操作系统相关页面 |
1.4 关键术语
| 术语 | 含义 | 容易混淆的点 |
|---|---|---|
| 连续存储 | 元素在内存中相邻 | 不是“逻辑上连续” |
| 动态数组 | 容量可增长的连续数组 | 扩容不是免费的 |
| 摊还 O(1) | 一串操作的平均代价 | 单次仍可能 O(n) |
| 负载因子 | 元素数 / 桶数 | 链式可大于 1,开放寻址必须小于 1 |
| 冲突 | 不同键落到同一桶 | 冲突不可避免,只能管理 |
| 开放寻址 | 冲突时在表内找下一个空位 | 删除要墓碑或重排 |
| 链地址法 | 每个桶挂一条链表/红黑树 | 额外指针和分配开销 |
| 哨兵 | 不存数据的边界节点 | 简化边界判断,不是业务数据 |
| 迭代器失效 | 修改容器后旧迭代器不可用 | 不同容器规则不同 |
| 环形缓冲区 | 头尾下标取模复用数组 | 满/空判断要额外计数 |
2 机制
2.1 心智模型
数组是“一排连续格子”,链表是“散落的格子 + 箭头”。数组的代价花在搬移,链表的代价花在跳转;哈希表则把“比较”换成“计算地址”。三者不是替代关系,而是分别优化随机访问、局部更新、按键查找。
2.2 机制拆解
- 动态数组:容量满时申请更大的连续块(常见 2 倍),复制旧元素,再释放旧块。单次扩容 O(n),n 次追加总代价 O(n),摊还 O(1)。
- 链表:节点保存值和 next(双向再保存 prev)。已知节点处插入/删除 O(1);按下标访问要 O(n) 走链。哨兵节点可以消掉头尾特判。
- 栈:只允许在一端 push/pop,LIFO;可用数组或链表实现。函数调用栈、括号匹配、DFS 都用它。
- 队列:只允许一端入、另一端出,FIFO;数组实现要用头下标或环形缓冲区,否则每次出队都搬移。
- 双端队列:两端都能 push/pop;可用环形缓冲区或双向链表。
- 哈希表:
hash(key) % m得到桶;冲突用链地址法或开放寻址;负载因子超过阈值时扩容并重新哈希。扩容是 O(n),但摊还到每次插入仍是 O(1)。
2.3 完整枚举
| 结构 | 内存布局 | 随机访问 | 查找 | 头部插入/删除 | 尾部插入/删除 | 中间插入/删除 | 额外空间 |
|---|---|---|---|---|---|---|---|
| 静态数组 | 连续 | O(1) | O(n) | O(n) | O(1) | O(n) | O(n) |
| 动态数组 | 连续,可扩容 | O(1) | O(n) | O(n) | 摊还 O(1) | O(n) | O(n),扩容时约 2n |
| 单链表 | 节点 + next | O(n) | O(n) | O(1) | O(n)(无尾指针) | O(1)(已知前驱) | O(n) + 指针 |
| 双链表 | 节点 + next/prev | O(n) | O(n) | O(1) | O(1)(有尾指针) | O(1)(已知节点) | O(n) + 双指针 |
| 循环链表 | 首尾相连 | O(n) | O(n) | O(1) | O(1)(有尾指针) | O(1)(已知节点) | O(n) + 指针 |
| 栈 | 数组或链表 | 仅栈顶 | O(n) | O(1) | O(1) | 不允许 | O(n) |
| 队列 | 环形数组或链表 | 仅队首/队尾 | O(n) | O(1)(队尾入) | O(1)(队首出) | 不允许 | O(n) |
| 双端队列 | 环形数组或双链表 | 两端 | O(n) | O(1) | O(1) | O(n) | O(n) |
| 哈希表(链地址) | 桶数组 + 链表 | 不支持有序 | 平均 O(1),最坏 O(n) | 平均 O(1) | 平均 O(1) | 平均 O(1) | O(n + m) |
| 哈希表(开放寻址) | 连续桶数组 | 不支持有序 | 平均 O(1),最坏 O(n) | 平均 O(1) | 平均 O(1) | 平均 O(1)(墓碑) | O(m),m > n |
哈希冲突策略:
| 策略 | 做法 | 优势 | 代价 |
|---|---|---|---|
| 链地址法 | 每个桶挂链表/红黑树 | 负载因子可大于 1,删除简单 | 指针、分配、缓存不友好 |
| 线性探测 | 冲突后看下一个槽 | 连续访问、实现简单 | 一次聚集,删除要墓碑 |
| 二次探测 | 按平方步长找空位 | 缓解一次聚集 | 不一定覆盖全表 |
| 双重哈希 | 用第二个哈希定步长 | 分布更均匀 | 计算成本更高 |
| 布谷鸟哈希 | 两个位置,踢来踢去 | 最坏查找常数 | 插入可能失败,需重哈希 |
2.4 关键数字与复杂度
| 指标 | 量级 | 说明 |
|---|---|---|
| 缓存行 | 64 字节 | 连续访问一次可带回多个元素 |
| 动态数组增长因子 | 2 倍(常见) | 太小会频繁扩容,太大浪费内存 |
| 哈希表负载因子阈值 | 0.75(常见) | 开放寻址通常更低 |
| 哈希表扩容 | O(n) | 摊还到每次插入 O(1) |
| 数组中间插入 | O(n) | 需要搬移后半段 |
| 链表按下标访问 | O(n) | 无法跳转,缓存也不友好 |
3 实践
3.1 最小示例
# 动态数组:扩容后复制;n 次 push 的总代价是 O(n)。
PUSH(a, x):
if a.size == a.capacity:
b = ALLOC(2 * a.capacity) # 容量为 0 时取 1
COPY(a.data, b, a.size)
a.data = b; a.capacity = 2 * a.capacity
a.data[a.size] = x; a.size += 1
# 链地址法哈希表:插入、查找、扩容。
HASH_INSERT(T, k, v):
i = HASH(k) mod T.m
for (key, val) in T.buckets[i]:
if key == k: T.buckets[i].update(k, v); return
T.buckets[i].append((k, v)); T.n += 1
if T.n / T.m > 0.75: RESIZE(T, 2 * T.m)
# 环形缓冲区队列:用 head + size 区分满和空,避免搬移。
ENQUEUE(q, x):
if q.size == q.cap: GROW(q)
q.data[(q.head + q.size) mod q.cap] = x
q.size += 1
DEQUEUE(q):
if q.size == 0: error("empty")
x = q.data[q.head]
q.head = (q.head + 1) mod q.cap
q.size -= 1
return x
3.2 常用操作与参数
| 操作 | 典型 API | 说明 |
|---|---|---|
| 尾部追加 | push / append | 动态数组摊还 O(1) |
| 尾部删除 | pop | 栈语义;空容器要报错 |
| 头部插入 | unshift / push_front | 数组 O(n),链表 O(1) |
| 按下标访问 | a[i] / get(i) | 数组 O(1),链表 O(n) |
| 按键查找 | map.get(k) | 哈希平均 O(1) |
| 顺序遍历 | for ... of | 数组缓存友好;哈希无序 |
| 去重 | new Set(xs) | 依赖哈希与相等语义 |
| 双端操作 | deque.push_back/pop_front | 环形缓冲区或双链表 |
3.3 标准流程
- 列出操作组合:随机访问、头部/尾部/中间插删、按键查找、顺序遍历,各占多少比例。
- 先排除不满足语义的结构:需要顺序就用数组/链表;需要按键 O(1) 就用哈希。
- 估算 n 和内存:链表指针开销、哈希桶数组、扩容峰值。
- 选冲突策略:链地址法适合删除频繁、负载因子高;开放寻址适合缓存友好、负载因子低。
- 处理边界并用真实数据分布压测:空容器、重复键、扩容/删除后迭代、哈希冲突、顺序/随机访问。
3.4 与相邻技术的组合
- 排序:数组是排序的主场;链表排序通常用归并,避免随机访问。
- 树与堆:堆用数组存完全二叉树;平衡树提供有序操作,弥补哈希表无序的短板。
- 图结构:邻接表是“数组 + 链表/动态数组”的组合;CSR 是压缩后的连续数组。
- 缓存:LRU 常把哈希表与双向链表组合,哈希负责定位,链表负责淘汰顺序。
3.5 选型维度
| 维度 | 取值 | 影响 |
|---|---|---|
| 访问模式 | 随机下标 / 顺序 / 按键 | 数组 / 链表 / 哈希 |
| 更新位置 | 头部 / 尾部 / 中间 | 决定是否搬移 |
| 是否需要顺序 | 是 / 否 | 哈希不保序,树/数组可保序 |
| 内存 | 紧张 / 充足 | 链表指针和哈希桶都有开销 |
| 缓存局部性 | 敏感 / 不敏感 | 数组通常优于链表 |
| 并发 | 单线程 / 多线程 | 普通容器需要外部同步 |
3.6 决策规则
- 随机访问多、遍历多:数组/动态数组。
- 已知节点处频繁插删、不需要下标:链表。
- 按键点查、不要求顺序:哈希表。
- 需要按 key 有序遍历/范围查询:平衡树,不是哈希表。
- 只在两端操作:栈/队列/双端队列,不要用通用数组模拟。
- 删除频繁且用开放寻址:用墓碑并定期 rehash,或改链地址法。
- 内存敏感且 n 可预估:预分配容量,避免扩容峰值。
3.7 替代方案对比
| 方案 | 优势 | 代价 | 适用 |
|---|---|---|---|
| 动态数组 | 随机访问 O(1)、缓存友好 | 中间插删 O(n)、扩容峰值 | 列表、缓冲区、栈 |
| 链表 | 已知节点插删 O(1) | 随机访问 O(n)、指针开销 | LRU、邻接表、频繁 splice |
| 哈希表 | 平均 O(1) 查找 | 无序、最坏 O(n)、扩容 | 字典、去重、缓存 |
| 平衡树 | 有序、范围查询、最坏 O(log n) | 实现复杂、常数大 | 有序映射、区间 |
| 栈/队列 | 语义清晰、O(1) 端点操作 | 只能按约定访问 | 解析、调度、BFS |
| 环形缓冲区 | 复用内存、无搬移 | 容量固定或需扩容 | 流式队列、日志 |
3.8 何时不该用
- 需要范围查询却用哈希表:只能全表扫描,改用平衡树或有序数组。
- 小规模数据却上哈希表:常数和分配开销可能超过线性扫描。
- 频繁中间插入却用数组:每次 O(n) 搬移,改用链表或分块结构。
- 哈希函数可被外部控制却不做随机化:冲突攻击可以让查找退化成 O(n)。
4 边界
4.1 典型故障
| 症状 | 根因 | 处理 |
|---|---|---|
| 哈希表查找越来越慢 | 负载因子过高或哈希分布差 | 扩容、换哈希、限制输入 |
| 哈希表被构造冲突打满 | 攻击者控制 key,哈希可预测 | 随机化种子、限流、上限 |
| 删除后查找失败 | 开放寻址直接置空,探测链断裂 | 用墓碑,定期 rehash |
| 扩容后旧迭代器崩溃 | 迭代器失效 | 修改后重新获取迭代器 |
| 队列越用越慢 | 数组出队后整体搬移 | 用 head 下标或环形缓冲区 |
| 链表遍历比数组慢很多 | 指针跳转、缓存未命中 | 改连续数组或分块 |
| 栈溢出 | 递归过深或栈容量不足 | 改迭代、增大栈、限制深度 |
| 内存持续上涨 | 容器只增不减、墓碑未清理 | 缩容、清理、定期重建 |
| 并发修改导致数据错乱 | 普通容器无同步 | 加锁或换并发容器 |
4.2 反模式
| 做法 | 后果 | 替代 |
|---|---|---|
用数组 shift() 实现队列 | 每次出队 O(n) | 头下标/环形缓冲区 |
| 用链表做随机访问 | 每次 O(n),缓存差 | 动态数组 |
| 哈希表存可变对象且改哈希字段 | 找不回原键 | 用不可变键或稳定哈希 |
| 依赖哈希表遍历顺序 | 顺序随扩容/实现变化 | 显式排序或换有序结构 |
4.3 可观测信号
哈希冲突率、平均探测长度、负载因子、扩容次数、容器容量与元素数、迭代器失效报错、队列的 head/tail 距离、P99 查找延迟。内存看分配次数和峰值,缓存看 miss rate。
4.4 安全 / 性能 / 一致性边界
- 安全:哈希冲突可被对抗构造,公开接口要随机化哈希并限制单键冲突。
- 性能:摊还 O(1) 不是单次保证;扩容那次可能造成长停顿,实时系统要预分配。
- 一致性:哈希表不保序;需要稳定输出时必须显式排序。