去摊还化

摊还证明说明未来一段操作“总有足够的钱”偿还一次大工作，去摊还化则把这笔工作提前拆成有截止期的小任务。每个公开操作领取固定迁移预算；只要任务产生率低于处理率，并且旧、新状态在过渡期都有明确权威关系，昂贵峰值就能被铺平成逐操作最坏界。

去摊还化的目标是把总工作平滑到每次操作，给出逐操作最坏界；全局重建公理库全局重建Global rebuilding在坏度量越界时从活动元素重建结构，并把线性成本收费给足够多次更新。本身只说明何时批量恢复结构，stop-the-world 实现仍可能产生一次 $\mathrm{\Theta }(n)$ 停顿。只有把重建增量化并证明迁移追得上更新，二者才会结合。

增量扩容的账 ​

容量 $n$ 的动态数组装满后申请 $2n$ 新区，不一次复制 $n$ 项，而让随后每次插入搬两项。未来至少还能插入 $n$ 项才再次装满，因此搬迁在 $n/2$ 次操作内结束，早于下一次扩容；一次插入承担常数写入，得到最坏 $O(1)$ 延迟。

覆盖尚未迁移的下标后，旧副本必须更新或记录新值，否则稍后复制会让旧值复活。若每步只搬一项而每次更新制造两个待迁移项，积压持续增长，“每步做一点”并未给最坏界。

边界 ​

去摊还化不是从任意摊还证明自动生成。工作必须能切成保持可查询状态的微步，旧版与新版能在受控空间内并存，迁移处理率还要追上新任务的到达率。下一次重建若在旧迁移结束前触发，双结构会叠成三结构，原空间与延迟界都需重新证明。

确定性每步预算才能给 deterministic worst-case；重建规模或迁移进度只以高概率受控时，只能声称 high-probability worst-case。后台线程若可能被调度器长期饿死，抽象工作量界也不能直接解释为 wall-clock 截止期。

写入并发时的版本协议 ​

迁移期间把每个逻辑槽分成“尚未复制、正在复制、已经复制”三态。写操作先读取状态：尚未复制时同时更新旧值和一条 redo 记录；正在复制时用短锁或版本号防止复制线程读到撕裂值；已经复制时只写新结构。复制步骤在发布新值前再次检查版本，若期间发生写入就重放最新记录。这样可在线性化点上解释每次读写，而不只是最终集合相等。

删除也不能简单清空旧槽。若复制线程已经读出元素、尚未写入新区，删除须留下 tombstone 并让复制提交前检查；否则被删元素会复活。使用双写则省日志读取，却把每次更新常数和缓存写流量增大，属于实现权衡。

成本与空间全账 ​

若普通操作成本 $T(n)$，每步迁移预算 $c$，公开最坏成本为 $T(n)+O(c)$。启动复制需分配新区，若内存初始化本身线性，就必须依赖惰性页映射或把初始化也拆成任务。空间在旧区、新区与日志并存时为两份结构加积压，不能只报告稳态空间。

对动态数组例子，复制 $n$ 项、每次搬 2 项，最多 $\lceil n/2\rceil$ 次插入完成。即使插入同时增加一个新元素，复制工作总到达率仍为 0，只有固定初始 $n$；对增量 rehash，每次插入还可能制造桶工作，必须重新计算到达率。

与实时和摊还保证的分界 ​

摊还 $O(1)$ 允许一次 $\mathrm{\Theta }(n)$，去摊还后的确定性最坏 $O(1)$ 排除这种算法级尾延迟；“以高概率每次 $O(1)$”仍允许小概率超时，不能替代硬实时保证。