字典与哈希:高效索引与去重
你做数据分析或 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


