08 哈希法
冲突、拉链、探测、扩容与 Python 容器
第 01 题 问题 1
哈希函数和哈希表是什么关系？
参考答案
哈希函数产生哈希值，哈希表用它定位桶或槽并维护记录。
解析
还需要判等、处理冲突和扩容；哈希函数不是完整的表。
第 02 题 问题 2
哈希冲突一定意味着两个键相等吗？
参考答案
不一定。
解析
不同键可能映射到同一个桶；必须继续比较键。
第 03 题 问题 3
容量 5、h(k)=k%5，键 12、7、22 分别进入哪个桶？
参考答案
都进入桶 2。
解析
这是冲突，不代表三条记录只能保留一条。
第 04 题 问题 4
拉链法如何处理冲突？
参考答案
在同桶的链/容器内保存多个键值对，并逐项查键。
解析
查询成本还取决于桶内记录数。
第 05 题 问题 5
开放寻址删除槽后，为什么不能总是直接设为从未使用的空槽？
参考答案
可能截断其他键的探测路径。
解析
通常用删除标记 tombstone，或采用维护探测不变式的其他方案。
第 06 题 问题 6
装载因子 α 如何定义？容量 8、记录 6 条是多少？
参考答案
α=n/m=6/8=0.75。
解析
它反映记录数与桶/槽数量关系；扩容阈值是具体实现的选择。
第 07 题 问题 7
扩容后直接复制旧桶编号，是否通常正确？
参考答案
不正确。
解析
若桶索引依赖新容量，要对键重新计算位置。
第 08 题 问题 8
列表能直接作为 Python dict 的键吗？元组一定能吗？
参考答案
列表不能；元组只有其成员均可哈希时才能。
解析
可变列表不可哈希，包含列表的元组也不可哈希。
第 09 题 问题 9
若 a==b，正确的哈希实现要求 hash(a) 与 hash(b) 有何关系？
参考答案
必须相等。
解析
反过来哈希相等不必键相等；这是一致性规则。
第 10 题 问题 10
把参与哈希/判等的字段在入表后修改，可能有什么问题？
参考答案
后续查找可能无法正确定位原记录。
解析
键在表内应保持哈希和判等语义稳定。
第 11 题 问题 11
dict 的查找复杂度是否永远 O(1)？
参考答案
不是，常规假设下平均 O(1)，最坏可 O(n)。
解析
碰撞、键哈希与判等成本都可能影响实际成本。
第 12 题 问题 12
set 与 dict 的主要接口差异是什么？
参考答案
set 保存唯一元素并支持集合运算；dict 保存键到值的映射。
解析
两者都通常要求键/元素可哈希；用途不同。