一句话定义
哈希表通过键的哈希值定位候选槽位,再用相等比较确认键。良好的散列与装载控制使查找、插入、删除的平均成本接近常数。
为什么重要
- 最常用的“提速”工具:把 的“在列表里找”变成 的“在集合里查”,能减少重复线性扫描;收益取决于数据规模与键的计算成本。
- 缓存、去重、计数、索引、记忆化(见 k2.algo.dynamic-programming)都依赖它。
使用边界
平均 O(1) 通常把哈希和相等比较当作常数;长字符串、自定义键和严重碰撞会改变实际成本。缓存键应包含模型、参数和模板版本,不能只用 prompt。
原理 / 图解
下标计算的基本形式:
装载因子 (元素数 / 槽位数)越高,冲突越多;所以哈希表会在装满前扩容。
CPython 的 dict 采用开放寻址与紧凑存储(3.6 起保持插入顺序,3.7 起成为语言规范):源码注释 https://github.com/python/cpython/blob/main/Objects/dictobject.c ;3.7 规范说明 https://docs.python.org/3/whatsnew/3.7.html 。字符串哈希默认随机化以防哈希碰撞攻击:https://docs.python.org/3/reference/datamodel.html#object.__hash__ 。
可运行示例
list 与 set 查找对比、手写链地址法哈希表、可哈希性、Counter / defaultdict / 保序去重(Python 3.15.0 一稿运行记录):
# 文件:examples/12_hash_table.py
# 哈希表:key --哈希函数--> 桶位置,平均 O(1) 查找。Python 的 dict / set
from timeit import timeit
n = 100_000
data_list, data_set = list(range(n)), set(range(n))
print(f"在 {n} 个元素中查找: list {timeit(lambda: n-1 in data_list, number=200)/200*1e6:.0f} µs"
f" | set {timeit(lambda: n-1 in data_set, number=200)/200*1e9:.0f} ns")
# 手写一个最简哈希表(链地址法),观察冲突
class HashMap:
def __init__(self, cap=8): self.buckets = [[] for _ in range(cap)]
def _idx(self, k): return hash(k) % len(self.buckets)
def put(self, k, v):
b = self.buckets[self._idx(k)]
for i, (kk, _) in enumerate(b):
if kk == k: b[i] = (k, v); return
b.append((k, v))
def get(self, k):
for kk, v in self.buckets[self._idx(k)]:
if kk == k: return v
raise KeyError(k)
m = HashMap(4)
for k in ["apple", "pear", "fig", "kiwi", "plum", "lime"]: m.put(k, len(k))
print("get('plum') =", m.get("plum"), "| 各桶长度:", [len(b) for b in m.buckets], "(字符串哈希每次进程启动都随机化,分布会变)")
# 可哈希才能做键;相等的对象哈希必须相等
print("hash(1) == hash(1.0) == hash(True):", hash(1) == hash(1.0) == hash(True), "→ 字典里它们是同一个键:", {1: "a", 1.0: "b", True: "c"})
try: {[1, 2]: "x"}
except TypeError as e: print("列表不能做键:", e)
# 常用:计数、分组、去重
from collections import Counter, defaultdict
words = "the cat and the hat and the bat".split()
print("词频 Top2:", Counter(words).most_common(2))
groups = defaultdict(list)
for w in words: groups[len(w)].append(w)
print("按长度分组:", dict(groups))
print("保序去重:", list(dict.fromkeys(words)))
一稿留存输出:
在 100000 个元素中查找: list 656 µs | set 64 ns
get('plum') = 4 | 各桶长度: [2, 4, 0, 0] (字符串哈希每次进程启动都随机化,分布会变)
hash(1) == hash(1.0) == hash(True): True → 字典里它们是同一个键: {1: 'c'}
列表不能做键: cannot use 'list' as a dict key (unhashable type: 'list')
词频 Top2: [('the', 3), ('and', 2)]
按长度分组: {3: ['the', 'cat', 'and', 'the', 'hat', 'and', 'the', 'bat']}
保序去重: ['the', 'cat', 'and', 'hat', 'bat']
- 10 万元素查找:list 与 set 的本轮计时显示了查找成本差异;纳秒级单次结果尤其需要重复测量。
1、1.0、True相等且哈希值相同,所以在字典中是同一个键,最后结果只有{1: 'c'}。- 列表可变、不可哈希,不能做键(见 k1.py.mutability)。
常见误区
- “哈希表永远 ”:这是平均情况;极端冲突时退化为 ,扩容那一次也是 。
- 把可变对象当键:自定义类如果重写了
__eq__却没正确实现__hash__,会导致查不到或无法哈希。 - 依赖 set 的遍历顺序:set 不保证顺序;dict 保证插入顺序。
- 以为字符串的
hash()每次运行都一样:默认每个进程随机化(PYTHONHASHSEED),不能把hash()结果持久化当 ID 使用,持久化用hashlib。
与 AI 开发的关系
- 分词表:token 字符串 → id 的映射就是一个大字典。
- 缓存:对相同 prompt 的 LLM 响应缓存、嵌入向量缓存(键可用
hashlib.sha256(prompt))。 - 去重:训练数据精确去重用哈希;近似去重用 MinHash/LSH 等“局部敏感哈希”。https://en.wikipedia.org/wiki/Locality-sensitive_hashing
- 特征哈希:sklearn 的
HashingVectorizer用哈希把文本映射到固定维度。https://scikit-learn.org/stable/modules/feature_extraction.html#feature-hashing
延伸阅读
- Python 字典文档:https://docs.python.org/3/library/stdtypes.html#mapping-types-dict
collections(Counter、defaultdict):https://docs.python.org/3/library/collections.html- Raymond Hettinger 演讲 “Modern Python Dictionaries”(PyCon 2017):https://www.youtube.com/watch?v=npw4s1QTmPg
理解检查
两个键哈希值相同,是否就会覆盖同一个字典项?
参考答案:不会。还要比较键是否相等;哈希碰撞不等于相同键。
核验与复现
核验日期:2026-10-14。示例状态:运行通过。本轮日志:12_hash_table.py。
配套代码与核验资料