动态表

概述

动态表（Dynamic Table）是一种能够自动调整大小的数组实现，支持高效的插入和删除操作。当表满时进行扩张（通常倍增），当表过于稀疏时进行缩容。通过摊还分析可以证明，在合理的扩张/缩容策略下，每次操作的摊还代价为 $O(1)$。

定义

动态表

动态表 $T$ 是一个支持动态调整大小的数组，维护以下状态：

• $\text{num}(T)$：当前存储的元素个数
• $\text{size}(T)$：当前分配的总槽位数
• $\alpha (T)=\text{num}(T)/\text{size}(T)$：负载因子（load factor）

支持两种基本操作：

• TABLE-INSERT(T, x)：插入元素 $x$
• TABLE-DELETE(T, x)：删除元素 $x$

核心性质

1. 负载因子：$\alpha (T)=\text{num}/\text{size}$ 是衡量表利用率的指标。理想情况下 $\alpha$ 接近 $1$，但需要为插入留出空间。
2. 几何扩张策略：当表满（$\alpha =1$）时，分配一个更大的表（通常为原来的 $2$ 倍），将所有元素复制到新表中。单次扩张代价为 $O(\text{num})$，但摊还代价为 $O(1)$。
3. 防抖动设计：缩容阈值设为 $\alpha <1/4$（而非 $1/2$），避免在插入和删除交替进行时出现反复扩张和缩容的”抖动”（thrashing）现象。这确保了连续扩张和缩容之间有足够的”缓冲区”。
4. 摊还 $O(1)$ 保证：通过合理的势能函数设计，可以证明在仅插入或插入+删除场景下，每次操作的摊还代价均为 $O(1)$。

表扩张机制

当执行 TABLE-INSERT 且当前表已满时：

1. 分配新表，大小为 ${\text{size}}_{\text{new}}=2\cdot {\text{size}}_{\text{old}}$
2. 将旧表中所有 $\text{num}$ 个元素复制到新表
3. 插入新元素
4. 释放旧表

代价分析：扩张操作的代价为 $O(\text{num})$（复制所有元素），但通过摊还分析，每次插入的摊还代价仅为 $O(1)$。

表缩容机制

当执行 TABLE-DELETE 且负载因子降至 $\alpha <1/4$ 时：

1. 分配新表，大小为 ${\text{size}}_{\text{new}}={\text{size}}_{\text{old}}/2$（但至少为 $1$）
2. 将剩余元素复制到新表
3. 释放旧表

防抖动原理：缩容阈值为 $1/4$ 而非 $1/2$。假设刚缩容后 $\alpha =1/2$（因为 $\text{num}=\text{size}/4$，缩半后 $\text{num}/(\text{size}/2)=1/2$）。要触发下一次扩张需要将表填满（$\alpha =1$），即需要再插入 $\text{size}/2$ 个元素；要触发下一次缩容需要删除到 $\alpha =1/4$，即需要再删除 $\text{size}/4$ 个元素。这保证了在两次调整之间有 $\Omega (\text{size})$ 次操作。

势能函数设计

仅插入场景

定义势能函数：

$\Phi (T)=2\cdot \text{num}(T)-\text{size}(T)$

验证：

• 初始状态：$\text{num}=0,\text{size}=0$，$\Phi =0$ ✓
• 非负性：$\text{num}\le \text{size}$ 时 $\Phi \ge 0$；$\text{num}>\text{size}$ 时（刚扩张后）$\Phi =2\text{num}-\text{size}\ge 2\text{size}-\text{size}=\text{size}\ge 0$ ✓

分析：

• 无扩张时：$\hat{c}=1+(2(\text{num}+1)-\text{size})-(2\text{num}-\text{size})=3$
• 有扩张时：$\hat{c}=(\text{num}+1)+(2(\text{num}+1)-2\text{num})-(2\text{num}-\text{num})=3$

每次插入摊还代价为 $O(1)$。

插入+删除场景（分段势能函数）

定义分段势能函数：

$\Phi (T)=\{\begin{array}{ll}2\cdot \text{num}(T)-\text{size}(T)& \text{若 }\alpha (T)\ge 1/2\\ \text{size}(T)/2-\text{num}(T)& \text{若 }\alpha (T)<1/2\end{array}$

该函数在 $\alpha =1/2$ 处连续（值为 $0$），且始终非负。可以证明插入和删除的摊还代价均为 $O(1)$。

实际编程语言实现

语言/数据结构	初始容量	扩张因子	缩容策略
Python list	0（动态分配）	$9/8$（约 $1.125\times$）	按比例缩容
Java ArrayList	10	$1.5\times$	缩至当前 $1/2$
C++ std::vector	0	$2\times$	C++11 起 shrink_to_fit
Go slice	0	$2\times$	无自动缩容

实现差异

Python 使用 $9/8$ 而非 $2\times$ 的扩张因子，牺牲了摊还常数因子以换取更小的内存开销。C++ 的 $2\times$ 扩张在理论上给出最优的摊还常数，但实际内存利用率可能较低。

参见

• 摊还分析 — 动态表分析的理论基础
• 16.1 聚合分析 — 可用于分析仅插入场景
• 16.2 记账方法 — 可用于分析动态表的摊还代价
• 16.3 势能方法 — 分析动态表最常用的方法