D03 · 预测 · 操作 · 解释结构选择
哈希表实验:碰撞、查找、标题索引和操作成本
资料多了,每次查 ID 或检查同名都从头扫描;换哈希后,以为落到同一个桶的键就是同一个标题。碰撞不是相等。
返回实战路线 →先说明你的预测
- 教学哈希为各字符码点和 % 桶数,采用链式冲突;查找仍比较完整键。这是公开简化模型,不是 Python dict 内部实现。
- 本地项目建立 by_id 与 Python strip().casefold() 标题索引;新增、修改、删除、撤销后都同步,加载后从记录重建,不把两份索引分别落盘。
- 网页键只用于受控 ASCII 示例,不对任意标题执行 Python 规范化。改键后旧键必须未命中;不存在、碰撞、重名和重载一致性分别测试。
这是确定性教学模型,状态检查只核对模型不变量,不检查你的预测答案、不执行 Python,也不证明掌握。模型操作次数与浏览器耗时、Python 实现成本分别理解。
受控数据结构模型
这里只检查模型自身状态,未执行你的 Python,也不判断预测是否正确。
未检查或已失效
分级学习提示
提示是固定教学内容,使用情况会记入学习记录。
提示 1
手算 a、e 在 4 个桶时的位置。桶相同,是否足以断言两个键相等?
提示 2
桶只缩小候选范围,链内仍比较完整键。更新标题时先验证新键,再移除旧键并登记新键,保留同一资料 ID。
提示 3
对存在、不存在、同桶不同键及改键后的旧键写断言。记录构建哈希次数、链内比较和存储;不要拿一次动画耗时证明复杂度。
我的 Python 草稿
这里只保存和导出草稿,不运行代码,也不与起始工程同步。修改草稿、输入或策略后,原模型结果与自报记录会失效。
本机学习记录
只保存在当前浏览器,可导出;不跨设备同步,不证明掌握。F01 与六任务旧记录会迁移保留。
- 已打开 D03: —
- 模型检查: 未检查或已失效
- 本地测试自报: —
- 最高提示层级: 0/3
- 已查看参考: —
- 无帮助变式自报: —
到同一校园资料整理器中实现
class DocumentIndex:
def rebuild(self, documents):
raise NotImplementedError
def lookup_id(self, identifier):
raise NotImplementedError
def lookup_title(self, title):
raise NotImplementedError
独立快照在 M1 基础上只保留本实验的故障;M2 起始工程包含三个实验的待修部分。参考代码与自己的作品分开。
python check_environment.py python -m unittest tests.test_d03 -v python -m unittest discover -s tests -v
使用 Python 3.11+ 与标准库,在新目录解压后运行。起始包预期失败以包内逐项清单为准。测试通过的参考实现只证明材料可运行,自己的代码仍需真实执行。
独立变式
独立实现 challenges.word_counts(words) 词频统计,明确键是规范化词、值是出现次数。Python 端按 strip().casefold() 处理,测试重复词、大小写、Straße/STRASSE 和空白;网页不模拟任意 Unicode 的 casefold。
python -m unittest tests.test_m2_variants -v
在 tests/test_student_counterexamples.py 中替换跳过占位,补自己的反例与解释。看过提示或参考的本次记录不会标记为无帮助完成。
成本与模型边界
合适散列和负载假设下,查找平均接近 O(1),最坏仍可 O(n),还需计入键长。构建/重建要处理全部键和链比较;额外存储为桶与条目。同一次查找按稳定资料 ID 升序做顺序扫描,分别统计两种比较次数,并单独统计构建成本;模型计数不是 Python dict 计时。
参考解释与答案
查看参考解释(会记录使用)
哈希把键映射到桶,链式模型还要逐项比较处理碰撞。改键不是覆盖值:必须使旧键失效并保留同一资料身份。Python dict 的性能与布局不能从此模型推断;项目必须验证索引与当前资料一致。
课名索引与相关实验
- F03:稳定 ID 查找
先保留正确的顺序查找基线。
- F04:标题规则
优化索引不改变规范化与失败规则。
- 栈实验:让校园资料误操作可以撤销
- 队列实验:按顺序批处理资料与观察环形回绕