3-13 关联数组、哈希函数-使用名字而不是索引访问数组

📄 一句话概括

数组用【第几个】找数据，关联数组（字典／Map）用【名字】找数据——名字背后站着一个哈希函数：把键瞬间算成一个存取位置，让查找从【挨个翻】变成【一步到位】。

📝 本节和前面几节的关系

3-8 的数组按下标访问——但现实里【苹果的库存】比【第 3 格的库存】好记。这一篇的字典是 Python 课（6-6 顺带见过）到数据库（3-1~3-3 索引加速查询）之间的桥：哈希是【查找为什么能快】的第一现场。

一、关联数组：键值对的集合

stock = {"apple": 3, "banana": 5}
print(stock["apple"])    # 3 —— 按【名字】取，不用记住它是第几格
stock["cherry"] = 12     # 新增一对

三个别名指同一个东西：关联数组（教材用词）、字典（Python）、映射／Map（Java／C++）。内部全是键（key）→ 值（value）的成对存放：键唯一、值随意。

二、哈希函数：名字变位置的秘密

【按名字找】为什么能快到 O(1)（和存多少条无关）？靠哈希函数——把键变成一个数组下标：

hash("apple") -> 840870762... -> 折算 -> 下标 7

键进来，哈希函数算出一个数字（哈希值）；
哈希值除以表长取余，得桶号（存取位置）；
存：值放进那个桶；取：对键重算一遍，直达同一个桶。

同一个键永远算出同一个桶（这就是哈希函数的纪律）——存取都对同一个位置，自然【一步到位】。3-2 的位运算在这里干重活（取余、混位）。

三、哈希冲突：两个键挤进一个桶

桶是有限的，键是无限的——两个不同键算出同一个桶（"apple" 和 "banana" 撞桶）迟早发生，这叫哈希冲突。主流解法链地址法：桶里不直接放值，挂一条小链表，撞了就往下接（3-15 链表派上用场）。冲突多了查找变慢，所以好的哈希函数追求散得开、算得快、结果稳定。

Python 的彩蛋：字符串键必须【不可变】（3-9 说过字符串不可变）才安全——内容变了哈希值就变了，数据就找不到了。所以字典的键只能是字符串、数字、元组这类不可变对象，列表当键直接报错。

四、动手 Demo：一步到位与冲突现场

stock = {"apple": 3, "banana": 5}
stock["apple"] += 1
print(stock["apple"], stock.get("pear", 0))   # 4 0

print(hash("apple") == hash("apple"))         # True  同键同哈希

看到什么算成功：4 0、True。

读结果：get("pear", 0) 是【不存在就给默认值 0】的安全取法——直接 stock["pear"] 会 KeyError；hash("apple") 每次运行数值可能不同（Python 故意加盐防攻击），但同一次运行内相同键必得相同值——哈希函数的纪律所在。

五、30 秒实验

跑 d = {[1,2]: "a"}——TypeError: unhashable type: list；换成 d = {(1,2): "a"} 就通过。列表可变不能当键、元组不可变可以——30 秒验证【键必须不可变】。

六、常见误区

【字典查找快是因为数据排好序了】——错。快是因为哈希函数直接算出位置，和排序无关；按序遍历字典反而是它不擅长的。
【哈希冲突是异常状况，正常系统不会发生】——错。冲突是常态（键无限桶有限），系统设计好了处理管线（链地址法）；要防的是冲突过多导致退化成一条长链。
【哈希值相同说明两个键相同】——错。不同键可以同哈希（冲突本身）；反过来【同键必同哈希】才成立。单向箭头别读反。

自测三问（点开对答案）

1. **哈希查找为什么是 O(1)？** 答：对键重算一次哈希直接得出存取位置，不用逐个比较——查找步数与数据总量无关。 2. **什么是哈希冲突、主流怎么解决？** 答：不同键算出同一个桶；主流用链地址法——桶里挂链表，冲突的条目依次接在后面。 3. **为什么 Python 列表不能当字典的键？** 答：列表可变，内容一变哈希值就变，数据将永远找不到；键必须选不可变对象（字符串、数字、元组）。

☐ 下一节（3-14 地址、指针）