跳到主内容
芝麻园地

D03 · 预测 · 操作 · 解释结构选择

哈希表实验:碰撞、查找、标题索引和操作成本

资料多了,每次查 ID 或检查同名都从头扫描;换哈希后,以为落到同一个桶的键就是同一个标题。碰撞不是相等。

返回实战路线 →

先说明你的预测

  • 教学哈希为各字符码点和 % 桶数,采用链式冲突;查找仍比较完整键。这是公开简化模型,不是 Python dict 内部实现。
  • 本地项目建立 by_id 与 Python strip().casefold() 标题索引;新增、修改、删除、撤销后都同步,加载后从记录重建,不把两份索引分别落盘。
  • 网页键只用于受控 ASCII 示例,不对任意标题执行 Python 规范化。改键后旧键必须未命中;不存在、碰撞、重名和重载一致性分别测试。

这是确定性教学模型,状态检查只核对模型不变量,不检查你的预测答案、不执行 Python,也不证明掌握。模型操作次数与浏览器耗时、Python 实现成本分别理解。

受控数据结构模型

手动观察模型

每次操作只改变受控样例。这里不运行学生 Python、不读取磁盘,也不以操作次数或模型状态签发掌握证明。

公开简化哈希与链式冲突

hash(key) = sum(character_code_points) % bucket_count

同一次查找另外按稳定资料 ID 升序进行顺序扫描,对比完整键比较次数;构建/重建计数单独展示。

键是小写 ASCII 教学样例,值代表稳定资料 ID;不对学生输入做 Python 标题规范化。a 与 e 在 4 个桶时都进入桶 1,但仍是两个完整键。

以下为下一次构建/重建的待应用参数,修改会使原模型检查失效,按按钮后才改变索引。控件输入与模型状态都会在本机保存。

  1. 桶 0: ∅
  2. 桶 1: a → doc_00000000000000000000000000000001 (h=1) · e → doc_00000000000000000000000000000002 (h=1) ·
  3. 桶 2: b → doc_00000000000000000000000000000003 (h=2) ·
  4. 桶 3: ∅

固定样例 a、e、b 已构建;a 和 e 在 4 桶时碰撞。 · 当前模型不变量: 一致

操作计数与模型范围

检查键、ID、桶和查询结果一致。顺序基线按稳定 ID 升序;完整键比较不含重建该视图的排序或显示复制,建表成本单列。不是 Python dict 性能证明。

累计哈希
3
累计键比较
1
累计顺序查找比较
0
累计条目写入/删除
3
构建/重建
1
显式查找
0
构建累计哈希
3
构建累计键比较
1
构建累计条目写入
3
条目
3
桶位
4
存储键值对
3
最长碰撞链
2
本次哈希
3
本次键比较
1
本次顺序查找比较
0
本次条目写入/删除
3

合适散列和负载假设下,查找平均接近 O(1),最坏仍可 O(n),还需计入键长。构建/重建要处理全部键和链比较;额外存储为桶与条目。同一次查找按稳定资料 ID 升序做顺序扫描,分别统计两种比较次数,并单独统计构建成本;模型计数不是 Python dict 计时。

计数来自模型定义,不是浏览器耗时;模型为显示和保存状态产生的复制不计作底层容器操作。

本次执行轨迹(最多保留 40 条)

  1. 固定样例 a、e、b 已构建;a 和 e 在 4 桶时碰撞。

这里只检查模型自身状态,未执行你的 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 的性能与布局不能从此模型推断;项目必须验证索引与当前资料一致。

下载本实验参考实现(答案) · 版本与来源摘要

课名索引与相关实验