字典、映射与集合 ADT

形式陈述 ​

给定键域 $K$ 与值域 $V$，字典或映射的抽象状态是有限偏函数公理库函数Function · Map · Mapping由定义域、陪域和单值图共同组成，并把每个输入送到唯一输出的映射。

$$M:K\rightharpoonup V,$$

其定义域 $\mathrm{dom}(M)$ 是当前存储的键。lookup(k) 在 $k\in \mathrm{dom}(M)$ 时返回唯一的 $M(k)$，否则报告缺失；contains(k) 判断这一成员关系；insert(k,v) 或 update(k,v) 产生满足 $M^{\prime }(k)=v$、其余键值不变的新状态；delete(k) 移除 $k$；iterate() 恰好枚举当前所有键值对，但除非规格另有声明，不承诺顺序。可变接口把这些函数关系实现为状态转移，不改变其可观察语义。

集合 ADT 是该规格的退化情形：只记录键是否存在，可把值域取为单位类型 $\{\star \}$，于是状态由有限集合公理库集合Set由确定成员组成的数学对象；成员关系而非表示顺序决定集合。 $S\subseteq K$ 完全决定。若同一键可同时关联多个值，对象已变成 multimap $K\rightharpoonup \mathcal{P}(V)$；它与“重复插入覆盖旧值”的普通 map 不是同一接口。

直觉 ​

抽象数据类型公理库抽象数据类型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) 可规定为无操作，也可返回“键不存在”的错误；两种设计都能自洽，但不能在实现之间无声切换。键的相等关系和可变性也属于边界：若键插入后其哈希值或比较结果改变，具体结构可能再也找不到它，即使抽象状态原本仍含该键。

推论与应用 ​

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

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

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, Ch. 11, dictionaries and hash tables.
• Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., Addison-Wesley, 2011, Ch. 3, symbol tables.