第十五章 字典与哈希：高效索引与去重

第十五章 字典与哈希：高效索引与去重

• 0. 本章目标与适用场景
• 1. 字典为什么快：把“查找”从 O(n) 变成 O(1)
• 2. 哈希表的工作机制：你需要的工程直觉
• 3. 字典与集合：索引与去重的两把刀
  • 3.1 dict：key→value（索引/映射）
  • 3.2 set：key 的集合（判重/过滤）
• 4. 数据工程中的“高频索引模式”（可直接套用）
  • 4.1 主键索引：id → row
  • 4.2 分组聚合：key → list（bucket）
  • 4.3 计数：key → count（Counter）
  • 4.4 反向索引：token → doc_ids（IR/RAG 基础）
• 5. 去重的三种层级：值去重、行去重、组合 key 去重
  • 5.1 值去重：单列 unique
  • 5.2 行去重：整行判等（结构化数据）
  • 5.3 组合 key 去重：最常见、最推荐
• 6. 不可哈希对象怎么办：把 key 变成“稳定且可哈希”
  • 6.1 list → tuple
  • 6.2 dict → 规范化后再哈希（稳定 key）
• 7. 哈希与“相等”的关系：为什么要同时实现 **hash** 与 **eq**
  • 7.1 dataclass 的安全写法（不可变 + 可哈希）
• 8. 哈希碰撞：要重视，但别恐惧
  • 8.1 工程建议：避免拿 Python 内置 hash 做持久化 key
• 9. 数据/AI场景中的“哈希指纹”：去重、缓存、实验复现
• 10. 性能意识：什么时候 dict/set 是“必选项”
• 11. 实战清单：你可以立刻回去改的 8 个点
• 12. 小结
• 下一章

你做数据分析或 AI 工程，迟早会遇到这三类“性能坑”：

• 明明只是“查一下某个 id 对应的特征”，结果写成了 O(n) 的循环，数据一大就卡死。
• 去重/判重写得很玄学：字符串去重、样本去重、Embedding 近似去重混在一起，最后谁都不敢动。
• join/merge 用得飞起，但一旦遇到“非结构化 key”（JSON、列表、dict），就不知道怎么稳定索引。

这一章我们把最常用、最容易被低估的基础能力讲透：字典（hash table）与哈希（hashing）。
目标只有一个：让你在工程里把“查询”和“去重”写得又快又稳。

0. 本章目标与适用场景

学完你应该能做到：

1. 识别“该用 dict/set 的地方”，避免无意义的 O(n) 循环
2. 掌握哈希表的时间复杂度直觉：平均 O(1) vs 最坏情况
3. 写出可维护的“索引结构”：id→记录、key→聚合、bucket→列表
4. 用 set/dict 解决常见去重：行去重、字段去重、组合 key 去重
5. 处理“不可哈希对象”（list/dict）并构造稳定 key
6. 理解哈希与碰撞、以及工程上如何规避“哈希不稳定”问题

1. 字典为什么快：把“查找”从 O(n) 变成 O(1)

列表里查找：

# O(n)for row in rows:if row["id"]== target:return row 

字典索引：

# O(1) 平均 idx ={ row["id"]: row for row in rows}return idx.get(target)

当 n=10 万、100 万时，这个差距就是“能不能上线”的差距。

2. 哈希表的工作机制：你需要的工程直觉

哈希表可以理解为：

• hash(key) → 一个整数
• 用这个整数映射到数组位置（bucket）
• bucket 里可能有多个元素（碰撞），再做一次比较确认

平均复杂度（工程上最常用）：

• 查找/插入/删除：O(1)

最坏情况：

• 如果大量 key 碰撞，可能退化为 O(n)（但正常业务很少遇到）

你需要的工程直觉是：
只要 key 设计合理、hash 分布均匀，dict/set 就是你最可靠的“索引结构”。

3. 字典与集合：索引与去重的两把刀

3.1 dict：key→value（索引/映射）

• id → record
• token → count
• user_id → features
• doc_id → embedding path

3.2 set：key 的集合（判重/过滤）

• seen_ids
• unique_words
• visited_nodes

最常见的去重：

seen =set() out =[]for x in xs:if x in seen:continue seen.add(x) out.append(x)

4. 数据工程中的“高频索引模式”（可直接套用）

4.1 主键索引：id → row

defbuild_pk_index(rows, key="id"