从精确字典到近似成员：哈希结构验收实验
同一个“哈希冲突”，可能触发换槽、移动整段余数，或迫使整批重建。本实验分别验收五项构造：随机哈希函数、两个精确字典、一个动态指纹多重集和一个静态成员过滤器。不要把它们包装成具有相同返回值与更新能力的同一种容器。
路线入口为把哈希假设变成可检查的状态。下载标准库检查器与确定结果。普通执行和Python的-O模式应给出相同检查结果；所有断言使用显式异常，不会因优化模式被关闭。
1. 先固定随机性，不能把经验分布当成定理
读简单制表哈希。键为00、01、10、11，c=2、每位置两个字符，r=2。穷举四个表项各取0至3的256张表，统计前三输出和四输出：
- 前三输出有64种组合，各出现4次
- 四输出仍只有64种组合，始终满足四项异或为0
- 因而前三输出独立，第四项已由前三确定
再用r=3、表T0=[1,6]、T1=[3,5]手算2、4、5、3。概率结论针对整个随机表空间；这张具体表只检查求值规则。
迁移有两项：把两个位置改为共享同一张表，找出ab与ba必然相撞；把均匀三位输出模3，算出桶概率3/8、3/8、2/8和两键碰撞22/64。分别说明改变了哪个前提，不能仅说“结果有些偏”。
2. 精确字典必须保留完整键和值
Robin Hood：距离成为否定证据
读Robin Hood哈希。m=8、首页为键模8，值为键乘10，依次插入0、1、8、16、2。最终前五槽为：
| 槽 | 键 | 值 | 距离 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 8 | 80 | 1 |
| 2 | 16 | 160 | 2 |
| 3 | 1 | 10 | 2 |
| 4 | 2 | 20 | 2 |
记录8、16各抢占键1的槽位。删除8后，16、1、2各前移一槽、距离减1；输出每次移动和最终空洞。然后逐键检查：距首页d的键，前面每个t<d槽的住户距离都至少t。
另按0、8、16、2插入，距离0、1、2、1并不单调。查询24在第四个槽即可由距离不足否定。实现若只检查“全局距离非降”，会误拒绝这个合法表。
迁移：用首页7的键7、15、23及首页0的键0构造跨尾部布局，删除15并核对循环距离。另将某已存键值更新为None，要求get仍报告found=True；键缺失才报告false。
Hopscotch：位图属于首页
读Hopscotch哈希。m=8、H=3，先插0至4，再插8。交出两次旧键移动3→5、1→3，以及洞偏移5→3→1。最终槽0至5为0、8、2、1、4、3，首页位图分别为011、100、001、100、001、000。
删除键0后，物理首页0为空，但hop[0]仍有第1位，键8仍能查到。另以同首页0的0、8、16占满三格后插24，应返回失败且旧映射不变，哪怕其它五槽全空。
更强边界是合法布局[空,7,4,5]，m=4、H=3。插1的规定贪心过程失败，但布局[4,1,5,7]可存下所有键。这要求报告“本次搬移策略失败”，不能报告“不存在任何可行放置”。固定输入从有效布局开始即可核算法边界；配套额外记录保留一段从空表到达此状态的历史。
3. 商过滤器：先解码，再相信布尔答案
读商过滤器。取q=r=3，依次插入完整指纹9、11、18、10、58、59、1。最终物理表为：
| 槽 | 余数 | O | C | S | 实际商 |
|---|---|---|---|---|---|
| 0 | 3 | 1 | 1 | 1 | 7 |
| 1 | 1 | 1 | 0 | 1 | 0 |
| 2 | 1 | 1 | 0 | 1 | 1 |
| 3 | 2 | 0 | 1 | 1 | 1 |
| 4 | 3 | 0 | 1 | 1 | 1 |
| 5 | 2 | 0 | 0 | 1 | 2 |
| 6 | 空 | 0 | 0 | 0 | 无 |
| 7 | 2 | 1 | 0 | 0 | 7 |
从空槽6后开始，解码次序为58、59、1、9、10、11、18。查18的双游标分别经过哪些商、哪些run？删除10后，余数3和商2的余数2前移，最终空洞在槽5；O仍留在0、1、2、7。
必须与独立Counter比较完整指纹多重集，并对全部64种指纹穷举查询。不能用被测查询函数自己重建“期望集合”，那会把同一个错误重复两次。
迁移：把同一指纹3插入两次，再删一次，仍须查询为真。解释两份指纹来自不同真实键时，为什么不能去重；若待删原键从未存在，仅因误报命中，为什么外部应拒绝删除。完整指纹查询为真与原键真实存在，是两种不同命题。
4. Xor过滤器：构建证书与查询误报分开
读Xor过滤器，取九个位置、三位指纹：
| 键 | 端点 | 指纹 |
|---|---|---|
| a | 0、3、6 | 1 |
| b | 0、4、6 | 2 |
| c | 1、3、7 | 4 |
| d | 1、4、8 | 3 |
交出剥离次序(c,7),(d,8),(a,3),(b,4)及每一步支点只属于唯一剩余边的检查。逆序得到B=[0,0,0,1,2,0,0,5,1]，逐个成员复算三个值异或等于其指纹。
迁移到两条同端点(0,1,2)的边：指纹都为5时有64种三位数组赋值，却无法度一剥离；指纹5、6时根本无解。构造过程对两者都返回未构建，证明这个返回值不是一般方程无解证书。
固定另一张成功表后，对固定非成员的三个位置，穷举指纹0至7，应恰有一个通过。只有这个查询指纹独立于所有构建信息且均匀时，比例1/8才是条件误报概率；共用有限独立哈希而未经证明，不能照抄结论。
5. 交付与成本说明
提交五项材料：随机表空间分布、两种精确字典轨迹及不变量、可完整解码的商过滤器、xor剥离与逆序赋值证书，以及上述结构迁移的反例。查询返回“缺失”、过滤器返回“可能存在”和插入/构建返回“失败”须分栏记录。
检查器的小规模穷举、随机操作和额外不变量扫描用于验正确性，不是高性能实现基准。Robin与商过滤器固定容量最坏扫描O(m)；Hop查询O(H)，朴素搬洞过程按单位位操作为O(mH²)；xor每轮核心剥离O(n+m)，去重、哈希求值和重试另计。Python大整数的位成本、检查器重复扫描全表的费用也另计。结论应引用正文归纳和不变量，不能用有限测试次数替代证明。