同一张字典的两种表示，以及一次不中断读写的搬迁 ​

这个实验要交出两样能重新算出的证据。第一样是一条共同的字典历史：两种表示每一步都给出相同的抽象映射，却走过不同的存储位置。第二样是一条数组迁移历史：写操作有时改旧区，有时改新区，最终仍保留每个下标的最新值。最后分别说明，这些具体轨迹支持了什么，以及哪些复杂度结论还需要证明。

下载 Python 标准库检查器 和 本例完整状态与费用输出。使用 Python 3.10 或更新版本，在本地运行：

python foundations-dictionary-contract-checker.py
python -O foundations-dictionary-contract-checker.py

脚本不访问网络、不依赖第三方包。两种运行输出相同的 JSON；所有判错都用显式异常，不依赖优化模式会删除的 assert。输出包括十八步字典状态、两种复制预算、两类最短故障、原五步迁移任务、非法输入和失败边界。改坏代码之后得到反例，和正常运行输出 PASS，是两个不同的检查结果。

1. 先选最短阅读链 ​

主线只需字典契约理路字典、映射与集合 ADTDictionary ADT · Map ADT · Set ADT以有限偏函数统一刻画按键查询、更新和删除的字典、映射与集合接口。 → 哈希表理路哈希表Hash table用哈希函数把键映射到桶并处理冲突的字典结构。 → 开放定址理路开放定址哈希open addressing · closed hashing把键直接存放在表数组槽位中的哈希表示；经典探测序列法与允许重定位的变体使用不同的查找不变量。 → 线性探测理路线性探测Linear probing · 线性探查哈希从哈希首页开始逐槽循环扫描的开放定址结构，以连续内存换取良好局部性，同时必须控制聚簇、墓碑和哈希独立性。，然后完成本页第2至4节。还不熟悉表示与抽象的读者，可按需补抽象数据类型理路抽象数据类型Abstract data type · ADT由值集合与操作语义定义、独立于具体表示的数据接口。、数组理路数组Array以连续整数下标支持随机访问的有限序列结构。与循环不变量理路循环不变式Loop invariant在循环初始化后成立，并在每次循环迭代后继续成立的断言。，不必先学概率。

数组分支沿原路线动态数组理路动态数组Dynamic array · Resizable array以预留容量和偶发整体搬迁支持可变长度的连续序列结构。 → 摊还分析理路摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。 → 全局重建理路全局重建Global rebuilding在坏度量越界时从活动元素重建结构，并把线性成本收费给足够多次更新。 → 去摊还化理路去摊还化Deamortization把批量工作拆成有截止期的微步，以顺序动态数组的读、写、追加证明权威槽不变量、迁移期限和逐操作最坏界。，完成第6至7节。想解释期望性能，再读通用哈希理路通用哈希Universal hashing · Universal hash family从函数族随机选择哈希函数，使任意预先固定的不同键对以至多 1/m 的概率碰撞。与期望理路期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分，概括加权平均与总体质量平衡。。这里的测试不替代表示独立性理路表示独立性Representation independence · Representation independence theorem以自然数和单位列表计数器为例，逐项证明接口关系，再对纯传值客户端的全部构造归纳，覆盖高阶调用与抽象状态递归。对任意客户端的证明。

2. 固定规格，再分开观察两种表示 ​

键为整数，示例值为短字符串，补充测试也允许值 None。put(k,v) 覆盖已有值，返回空结果；get(k) 返回 found 与 value；delete(k) 返回删除前的这两个字段，缺失时不改映射；rebuild(m) 只改存储布局。缺失与存在但值为 None 可以区分。操作名、参数个数和键类型在改变状态之前检查，容量必须是正的非布尔整数。线性表的 rebuild(m) 还要求 $m\ge max(1,n)$，因为每个活动键必须有自己的槽；目标太小会在改变状态之前被拒绝。链地址表允许一个桶存多条记录，重建容量只需 $m\ge 1$。

两张表都从容量5的空状态开始，首页函数固定为 $h(k)=kmodm$。链地址表保持每桶内的插入次序；线性探测表依次访问 $(h(k)+r)modm$，其中 $0\le r<m$。我们用 · 表示从未用过的空槽，用 † 表示墓碑。二者在本轮表示中的含义不同；重建后会重新产生真空槽。

抽象标准答案由另一份 Python dict 按规格更新，只知道键和值。每次公开操作结束，都检查以下事实：

• 返回值与独立抽象转移一致；物理记录中的每个键恰出现一次，所有记录解释出的映射与标准答案相等
• 链表记录位于正确的桶，物理记录总数等于活动计数 $n$
• 线性表满足 $0\le n\le used\le m$，used 恰为活动槽与墓碑之和
• 对槽 $j$ 中的键 $x$，从首页到 $j$ 之前的循环路径没有真空槽；检查器直接按循环距离查看这些槽，不调用被测查找函数

最后一项是停止规则的结构依据；唯一性检查则必须在 dict(records) 合并记录之前进行，否则两个相同键会被无声折叠。检查器在每步都做这些检查，并不只比较最终答案。

3. 执行十八步共同历史 ​

先复算前十四步。下表的槽按物理下标 0,1,2,3,4 排列；14:C2 表示键14当前值为C2。每行的活动记录就是这一步的抽象映射，表内没有第二份同键记录。

第三步已发生环绕：键14的路径为 4→0→1。第五步经过墓碑0后命中槽1，必须更新原记录，不能增加 $n$。第六步记住墓碑0，仍继续探测到真空槽2，确认不存在键19后才回填0。

第十步之后没有真空槽。第十一步查询24按 4→0→1→2→3 扫满五槽，返回缺失；第十二步仍能在三次探测后更新14。第十四步也扫描五槽，但它保留了首墓碑4的位置，确认没有同键后在4写入24。不能只写一个“遇空槽才结束”的无界循环。

对应的链地址表示也可逐步复算。第1至3步都在桶4尾部加入记录。第4步移去9，桶4变成 [4:A,14:C]；第5步原位更新14；第6步追加19。第7步遍历桶4后报告99缺失。第8步新增桶0中的 [0:Z]，第9步从桶4删4。第10步新增桶3中的 [3:E]，第11步在桶4中找不到24。第12步把桶4首记录改为14:C3，第13步清空桶0，第14步将24:F加入桶4尾部。因此第14步非空桶恰为 3:[3:E] 与 4:[14:C3,19:D,24:F]，它和线性表表示同一映射。

接下来按旧槽下标从小到大扫描，重建至容量10：

第十五步按旧槽扫描的重插顺序是19、14、3、24，探测数为1、1、1、2。链地址表重建后是 3:[3:E]、4:[14:C3,24:F]、9:[19:D]；第十七步清空桶3，最后一次重建不再含它。完整JSON另列每一步的抽象映射、两张表的物理状态与所有费用，读者可以在任意一步停止核对。

主历史始终满足 $n<m$，但第10至14步的 $used=m$ 超出了 Open Data Structures §5.2 正常实现的 $m\ge 2used$ 约束。本例有意测试有界探测接口的终止性，不对这个高占用状态使用教材的期望常数结论。补充边界还覆盖全活动、全墓碑和空表：全活动表允许同键更新，缺失查询扫描有限全表，新键插入报容量不足且不改变状态；全墓碑表仍可在完整查重后复用墓碑。

4. 让两个错误确实失败 ​

把查询的停止条件错改为“遇墓碑就报告缺失”。容量3、首页 $kmod3$ 时，检查器找到：

put(0,a)  → [0:a, ·, ·]
put(3,b)  → [0:a, 3:b, ·]
delete(0) → [†,   3:b, ·]
get(3)   → 错误返回缺失；正确值为b

这是从空表开始、以公开返回值观察该错误的四步最短反例。必须先插入前方键和受遮挡的不同键，再产生墓碑，最后查询后方键。若把不变量检查本身作为观察，删除错误地写成真空槽会在第三步就被发现；那是另一种故障和另一种观察口径。

第二种错误是在插入时遇墓碑就直接占用。把上例最后一步改成 put(3,b)，会得到 [3:b,3:b,·]。两份物理记录甚至值也相同，抽象化为Python字典后可能看不出差别；“先查重复再解释映射”的检查会立即失败。

脚本按长度1、2、3、4枚举六种调用：插入0、插入3、读取0、读取3、删除0、删除3。前三层共检查 $6+36+216=258$ 条历史，都未触发这两种变异；第四层给出上述反例。有限枚举证明的是这个操作字母表中的最短性，前面的准备动作论证解释了为什么四步已足够。正常实现还检查了八种调用组成的全部 $8^4=4096$ 条长度四历史，加入同键换值和重建。

5. 三份成本账 ​

一条固定历史的实际费用 ​

以下 P 是线性表普通操作检查的槽数，C线 是其中真正执行的键比较，C链 是链地址表的键比较。遇墓碑会增加P，不会增加键比较。

链地址实现用 Python 列表保存桶，所以本例第4步删除9会搬动后面的一条记录，第9步删除4会搬动后面两条记录。脚本将这三次后缀搬动计入 moved_records；理论链节点实现的改指针费用与此不同。列表扩容、解释器和对象分配也不由这个记录计数完整描述。这里在核对算法工作量，不以运行秒数比较两种实现。

两次重建的线性表账分别为：第15步扫描5槽、初始化10槽、搬4条、重插探测5次；第18步扫描10槽、初始化10槽、搬3条、重插探测4次。合计扫描15、初始化20、搬7、重插探测9。链地址重建同样扫描15、初始化20、搬7条；加上先前的3次桶内搬动，输出的总 moved_records 为10。初始空表创建在历史开始之前，双方各有5个初始桶或槽，不重复记到某次公开操作中。

随机查找与维护摊还分别需要什么 ​

本例首页固定，没抽样也没重复选种子，43次探测不是期望值。链地址的随机界应在固定键集和查询键之后，对满足碰撞概率界的随机哈希函数取期望；线性探测则需要其自身的随机模型与聚簇分析。二通用碰撞界不能自动替代线性探测的概率前提，带墓碑压力态也不直接满足无删除模型的经典公式。

维护账讨论另一量词：对每条满足规定触发策略的操作历史，总扫描与搬迁能否由更新支付。同容量清理的具体账本理路全局重建Global rebuilding在坏度量越界时从活动元素重建结构，并把线性成本收费给足够多次更新。给出一个例子：容量m不变，从零墓碑起，到墓碑数达到 $\lceil m/4\rceil$ 才清理；至少发生 $D\ge \lceil m/4\rceil$ 次成功删除，可支付 $m+m+n\le 3m\le 12D$ 的扫描、初始化与搬迁。重新插入的探测总量仍是另一笔费用，不能从“每条只搬一次”推出。

本历史第18步是为了教学而主动重建，之前仅删除一次。它没有遵守上述阈值，所以不能拿这两次数值宣称已证明摊还常数；可在没有更新时反复发出重建调用，也能反复付整表成本。

单次最坏工作仍在哪里 ​

本例最长普通线性探测为5次；一般容量m下，有限扫描的最坏上界为m。链地址一次按键查找可比较全部n个记录。一次重建至少承担整表扫描与新表初始化，极端碰撞时，开放定址重插还可能累计二次量级的探测。即使某个随机模型给出期望摊还常数更新，也不能由此删除这些单次昂贵可能性。

检查器本身做得更慢：线性表的独立可达性检查最坏查看 $O(nm)$ 个路径位置；完整快照用 $O(m+n)$ 时间和空间，保存q步完整输出要按各步容量求和，固定容量时为 $O(q(m+n))$。这些工作属于外部核验器，没有藏进哈希表操作的性能声明。

6. 复算数组的权威前沿 ​

从容量与长度均为8的 [a,b,c,d,e,f,g,h] 开始。触发追加前固定旧规模 $N=8$，旧区记O，新区B容量16，初始前沿 $k=0$。用户动作先做，随后做满剩余任务允许的复制预算，预算q取1或2。

权威位置仍按原页协议：$i<k$ 去B，$k\le i<N$ 去O，$N\le i<n$ 去B。每个微步只做 B[k]=O[k]，然后增加k；达到8即提交为稳态A。新区尚未复制的旧下标不能被当成有效值读取。

下面的两列每格依次写“用户位置；随后复制的旧下标；操作末前沿”。提交表示新A已经接管全部下标。

两次执行的最终逻辑序列都是 [A,b,c,d,e,f,g,H,I,j]。第三步之后，旧O[0]仍是小写a，B[0]已经是大写A；这不是不变量失败，因为O[0]已失去权威性。第二步必须更新O[7]，它之后被复制成H。把这次写错误路由到B[7]，独立检查立即发现未迁移区域被写入；之后从O[7]复制还会用旧h覆盖它。

旧路线要求的五步任务也完整保留在输出 original_N8_route：append(i), read(0), write(7,H), read(7), append(j)，每步预算2。末前沿依次为2、4、6、提交、稳态；读取结果为a与H，最终序列为 [a,b,c,d,e,f,g,H,i,j]。它与上表是两条不同的历史，不能混用结束值。

7. 迁移边界题与完整答案 ​

1. 如果从触发追加起连续执行追加，预算1会不会来不及？不会。第t次合法操作末 $k=min(8,t)$；第8次复制完毕，也恰好把长度增至16。第9次追加才要求容量32，此时上一轮已经提交。预算2在第4次就提交；两种预算下一次启动都在第9次。一般N下完成步数为 $\lceil N/q\rceil \le N<N+1$。

2. 如果操作混有读写，上式哪里改变？新增尾部的数量只等于追加次数a，所以 $n=N+a\le N+t$；复制仍由每次成功的合法操作推进。读写不消耗新容量，因此不会提前下一次扩容的期限。新增尾部没有加入待复制集合，本轮任务始终只有最初的N个旧槽。

3. 如果N=1，预算2是不是越界复制？触发追加先写B[1]，剩余任务只有1项，所以复制 min(2,1)=1 项，当次提交为容量2。预算1的结果相同。代码实际覆盖这个边界，没有第二次读O[1]。

4. 迁移中读下标−1，或写下标n，会不会顺便搬迁？本实验在任何用户动作和复制之前拒绝它们。长度、前沿、O和B的完整快照均保持不变。Python列表原本允许负下标，这里明确禁止。浮点预算1.0、布尔键、缺少value的put等输入也先拒绝，不能等某个循环抛错时才发现状态已被改坏。

5. 满载追加时分配失败如何恢复？失败注入发生在发布O、B、N、k以及增加n之前，原数组 [a,…,h]、n=8、C=8都不变。之后去掉故障重新调用同一追加，正常写入i并领取预算。失败请求不算截止期公式中的成功操作，也没有吃掉尾部空位；任意多个这样的失败不会让容量需求追上复制进度。

6. 每次至多复制两项，是否已经证明这个Python程序最坏常数时间？没有。新区 [None]*16 实际初始化16槽；一般为2N槽。提交时退休N槽的列表，引用处理也可能有线性费用。输出分别列 copied_slots、allocated_slots、retired_slots。原页的最坏常数定理依赖未初始化区块保留与释放为常数的抽象模型；本实现只逐项验证路由、复制预算和截止期。测量器的全量快照也不计入这项算法定理。

7. 能否在迁移中一直返回同一个连续缓冲区？不能。这一接口只保证逻辑下标读写和追加。尚未迁移的中段在O，已迁移前缀与新尾部在B；若客户端必须持有整段连续内存地址，就需要另一套存储或接口方案。删除、收缩、并发也没有因本实验通过而得到许可或证明。

8. 完成标准与来源 ​

完成实验时，应能在不运行程序的情况下复算第五、第十一、第十四步的探测与计数；指出第四步后为何墓碑不能提供停止证据；给出两类四步最短错误历史；从原始槽位检查可达性；分别说明43次固定探测、维护摊还账与随机期望的量词。数组部分应能从任意一行决定读写位置，解释旧副本为什么可以陈旧，并独立算出预算1与2的结束边界。

这里没有新增基础概念：它把旧页已经证明的契约、墓碑、摊还和前沿协议变成可执行证据。全部有限测试通过，仍不能替代任意操作长度上的归纳证明；原页的完整证明与接口继续承担这一责任。

• MIT 6.031，Abstraction Functions & Rep Invariants，抽象函数、合法表示和表示不变量的分工
• Pat Morin，Open Data Structures，第5章，§5.1的链地址，§5.2的活动数n、已用数q、墓碑、重新插入与随机分析；本实验的used对应该书q
• Cornell CS3110，Lecture 20: Amortized Analysis，序列总成本与动态表几何增长
• Goodrich、Hirschberg、Mitzenmacher、Thaler，Cache-Oblivious Dictionaries and Multimaps with Negligible Failure Probability，§4.1、印刷页11的crossover index。原文半满启动、访问前复制；本页沿用既有去摊还化页独立证明的满载启动、动作后复制协议，不移用原文外围字典的概率保证