字典、映射与集合 ADT

抽象数据类型理路抽象数据类型Abstract data type · ADT由值集合与操作语义定义、独立于具体表示的数据接口。先规定用户能够观察什么，再把存储方法留给实现。对 map，核心事实不是桶、指针或树高，而是每个当前键至多有一个现行值，以及每次操作如何改变这张有限对应表。哈希表可以放弃顺序换取期望常数时间，平衡搜索树可以维护键序支持范围查询；只要查询和更新遵守同一契约、迭代返回规范允许的某个次序，它们就能实现同一个基本 ADT；无需让每次迭代的输出序列逐项相同。

这种分层也解释了为什么复杂度不能偷偷写进定义。lookup 的语义是返回对应值或缺失，并不自动意味着 $O(1)$、$O(\log n)$ 或保持插入顺序。只有某个具体实现或扩展接口作出成本、顺序和并发保证后，客户端才能依赖它们。

设初始映射为空，依次执行 insert("Ada", 36)、insert("Lin", 41)、insert("Ada", 37)。普通 map 的最终状态为 $\{\text{Ada}\mapsto 37,\text{Lin}\mapsto 41\}$，第二次写入 Ada 覆盖旧值；multimap 则可能保留 Ada 的两个值。若接口没有说明覆盖还是累积，调用方无法判断第三次操作后的结果，规格就是不完整的。

同一状态用哈希表迭代可能先返回 Lin，也可能先返回 Ada；有序 map 则按键比较次序输出。这一差异不影响 lookup，却会影响序列化和可复现实验，因此“迭代次序”必须作为额外契约明确加入，不能从 map 一词推断。集合接口同样只保证成员语义；数学集合可以无限，而实际数据结构在任一有限时刻只表示有限个已存元素。

空映射上的 delete(k) 可规定为无操作，也可返回“键不存在”的错误；两种设计都能自洽，但不能在实现之间无声切换。键的相等关系和可变性也属于边界：若键插入后其哈希值或比较结果改变，具体结构可能再也找不到它，即使抽象状态原本仍含该键。

实现应按操作组合和存储层选择。二叉搜索树理路二叉搜索树Binary search tree · BST每个结点左子树键小于、右子树键大于该结点键的二叉树。提供有序字典的基本比较模型，红黑树理路红黑树Red-black tree用节点颜色和路径黑高不变量保持近似平衡的二叉搜索树。把查找、插入和删除都约束在最坏 $O(\log n)$；B 树理路B 树B-tree以高扇出、有界节点占用率和等深叶层降低外存查找 I/O 的平衡搜索树。与B+ 树理路B+ 树B+ tree · B-plus tree将全部记录保存在等深叶层、以内部路由键和叶链同时支持单键与范围访问的多路搜索树。把高分支节点和块访问用于外存，其中 B+ 树把记录集中在叶层，便于范围扫描。跳表理路跳表skip list用独立几何高度建立多层稀疏链表，以期望对数时间支持有序字典操作。用随机层高换取期望对数时间，字典树理路字典树Trie · Prefix tree按字符串前缀共享路径组织键集合的树形数据结构。按键的符号前缀导航，成本取决于键长而非元素个数；Cuckoo Hashing理路Cuckoo Hashingcuckoo hashing · 布谷鸟哈希为每个键提供两个候选槽，以踢出链和必要的重哈希换取常数最坏查找。在已经成功构造的两位置表中只检查两个候选槽，因而查询为最坏常数时间；插入的期望摊还界则需要另外分析重定位失败与重哈希。这些结构在各自的键域条件下实现同一基本 ADT：搜索树需要一致的键序，trie 需要可逐符号读取的有限键，哈希结构需要可计算的哈希与相等判断。它们不共享同一顺序能力、最坏界或存储模型。

哈希表理路哈希表Hash table用哈希函数把键映射到桶并处理冲突的字典结构。、搜索树和 trie 都可以实现字典；集合去重、符号表、缓存索引、数据库主键表则共享同一组成员与更新语义。算法分析应先用 lookup、insert、delete 等抽象操作证明正确性，再代入所选实现的最坏、摊还或期望成本。这样更换实现只改变性能论证，不会连带改写算法含义。

把值域换成计数器可得到频率表，换成对象列表可得到倒排索引；这些仍是普通 map，只是值类型更丰富。真正允许一个键拥有多个独立关联、且分别插删关联时，才需要 multimap 的另一套操作规格。

把同一接口交给两个表示检查 ​

要比较两个实现，先把返回值也写进小规格。配套字典契约实验采用 put(k,v) 覆盖旧值并返回空结果，get(k) 返回 (found,value)，delete(k) 返回删除前的同一对结果，缺失删除不改变映射。found 单独存在，因而“键存在且值为 None”与“键缺失”不会混淆。重建只改变表示，抽象映射与键数都保持不变。迭代只比较键值对，不要求链桶顺序等于槽位顺序。

实验让一份独立的 Python dict 只执行这些抽象转移。链地址表和线性探测表各执行同一条操作历史，每步同时核对返回值、活动记录和表示不变量。抽象检查器不调用被测实现的 get 来拼出期望答案，也不复用它的停止规则；否则，一个错误查询可能同时污染“实际结果”和所谓标准答案。

检查的次序很重要。先确认物理记录中没有重复键，再把它们解释成映射。若两个槽都保存 (3,b)，直接调用 dict(records) 会把它们折叠成一项，甚至与正确抽象状态完全相同；物理唯一性却已经失败，下一次删除一个副本可能让旧值重新出现。实验专门注入“遇墓碑立即插入”的错误，让这个原本会被抽象化掩盖的问题在第四步被抓住。

这些检查是实现精化的有限证据。推广到任意历史仍需证明：初始表示合法；每个公开操作保持表示不变量，并与抽象转移相符。测试提供具体失败状态，归纳证明负责覆盖没有列举的长度与键值。MIT 6.031 的抽象函数与表示不变量给出了这一分工的基础。