1哈希函数与相等契约
闭卷重建哈希函数与相等契约的ADT、表示不变量、操作与复杂度。
数据结构与抽象数据类型 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2链地址法
闭卷重建链地址法的ADT、表示不变量、操作与复杂度。
3开放寻址与探测序列
闭卷重建开放寻址与探测序列的ADT、表示不变量、操作与复杂度。
4墓碑、删除与聚簇
闭卷重建墓碑、删除与聚簇的ADT、表示不变量、操作与复杂度。
5装载因子、扩容与rehash
闭卷重建装载因子、扩容与rehash的ADT、表示不变量、操作与复杂度。
6最坏攻击与随机化
闭卷重建最坏攻击与随机化的ADT、表示不变量、操作与复杂度。
7实验：开放寻址字典
闭卷重建实验：开放寻址字典的ADT、表示不变量、操作与复杂度。
第 1 页 · 背面（答案）
机制：每个桶保存冲突键集合，查询先定位桶再按相等比较，装载因子可大于1；实验：插入冲突键并统计桶长度、成功/失败比较次数；边界：更新已有键不能增加size，删除空桶元素后链结构也要保持。
机制：相等键必须产生相同哈希，哈希把大键空间映到有限桶；分布与计算成本都重要；实验：为整数/字符串实现稳定哈希并检查相等对象契约；边界：进程随机盐会让跨运行桶位置变化，不能把hash值当持久化标识。
机制：墓碑表示曾占用但已删除，查询继续穿过，插入可复用最早墓碑；过多墓碑需重建；实验：构造冲突簇删除中间键后继续查询尾键；边界：看到墓碑不能立即停止，插入也不能跳过后面可能已存在的相同键。
机制：元素直接放表槽，线性/二次/双重哈希生成探测序列，查询遇真正空槽才可停止；实验：对小表逐步执行线性探测并输出槽位；边界：删除直接置空会截断后续键查询，探测必须覆盖表或检测已满。
机制：糟糕分布或对抗键会把字典退化为线性，随机种子和树化桶等策略缓解；实验：构造同余冲突键比较探测长度与随机分布；边界：平均O(1)依赖分布假设，不是所有输入的确定保证。
机制：装载接近阈值时分配新表并按新容量重新插入所有活键，因为桶位置依赖容量；实验：从容量4扩到8并比较每个键新位置；边界：直接复制槽数组会让查询按新模数找不到键，墓碑通常不应复制。
机制：实现put/get/delete/resize，区分EMPTY/TOMBSTONE并报告探测次数；实验：覆盖更新、冲突、删除链、墓碑复用和扩容测试；边界：键相等与哈希规则必须稳定；表满时不能无限探测。