字典与哈希：高效索引与去重
你做数据分析或 AI 工程，迟早会遇到这三类'性能坑'：
- 明明只是'查一下某个 id 对应的特征'，结果写成了 O(n) 的循环，数据一大就卡死。
- 去重/判重写得很玄学：字符串去重、样本去重、Embedding 近似去重混在一起，最后谁都不敢动。
- join/merge 用得飞起，但一旦遇到'非结构化 key'（JSON、列表、dict），就不知道怎么稳定索引。
这一章我们把最常用、最容易被低估的基础能力讲透：字典（hash table）与哈希（hashing）。 目标只有一个：让你在工程里把'查询'和'去重'写得又快又稳。
0. 本章目标与适用场景
学完你应该能做到：
- 识别'该用 dict/set 的地方'，避免无意义的 O(n) 循环
- 掌握哈希表的时间复杂度直觉：平均 O(1) vs 最坏情况
- 写出可维护的'索引结构'：id→记录、key→聚合、bucket→列表
- 用 set/dict 解决常见去重：行去重、字段去重、组合 key 去重
- 处理'不可哈希对象'（list/dict）并构造稳定 key
- 理解哈希与碰撞、以及工程上如何规避'哈希不稳定'问题
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
