哈希表先把键映射到有限的桶，再在桶内确认键是否相等。哈希值相同只说明需要进一步比较，不能推出键相同；有限桶接收无限候选键时，碰撞本身无法彻底消除。
碰撞如何处理
链地址法把同桶元素放在一条链或其他容器里，开放寻址法则在表内继续寻找空位置。装载因子是元素数与桶数的比值；越拥挤，探查和碰撞通常越多。扩容重新分配桶，单次可能线性，但合理增长策略能控制一串插入的总成本。
在合适散列分布和装载条件下，查询、插入、删除的平均成本可以接近 O(1)；恶意碰撞或退化输入会破坏这个结论。Python dict 保持插入顺序，顺序是语言层面的行为，不能因此把它当作按键排序的树。
键必须可哈希。相等对象应有相等哈希值，放入哈希表后参与相等判断的状态不能随意变化。可变 list 不能直接作键，可以在含义合适时转换为 tuple。1 与 True 相等，在字典里可能指向同一项；需要区分类型时应把类型纳入复合键。
一次扫描统计互补关系
给定整数序列，统计下标对 i<j 且 values[i]+values[j]==target 的数量。扫描到当前值 x 时，历史表只保存左侧元素，因此 target-x 的出现次数正好是以当前位置为右端的合法配对数。先查询，再把 x 记入历史，可以排除同一位置与自身配对。
def count_pairs(values, target):
counts = {}
answer = 0
for value in values:
answer += counts.get(target - value, 0)
counts[value] = counts.get(value, 0) + 1
return answer
if __name__ == '__main__':
print(count_pairs([2, 2, 2], 4))
[2,2,2] 目标为4时有三对，不是一个不同值对。[4] 目标为8时结果为零；若先插入当前元素，便会错误得到一对。不同合法下标对按右端位置被唯一归类，所以不会重复计数。平均时间 O(n)，额外空间 O(u)，u 是不同值数量。
何时不用哈希
需要按范围查询、找前驱后继、稳定的有序遍历时，有序数组或平衡树更自然。整数键范围很小且稠密时，直接计数数组可以减少对象开销。哈希表依赖随机访问；超大数据或外存场景还需要考虑分块、排序和I/O。
哈希表里的普通哈希也不是密码学摘要。不要把 Python hash() 的结果保存为跨进程持久ID，字符串等对象的散列可能因进程随机化变化；持久身份应使用明确规则和相应摘要方案。
练习与面试自查
写出返回全部下标对的版本，并解释输出本身为什么可能达到 Θ(n²)。本例只计数所以能保留线性期望时间。再用双重循环作小规模基线，随机生成正数、负数与重复值对拍。
面试时要能明确说出：O(1) 是在什么假设下；碰撞为什么不等于覆盖旧值；可变键破坏了哪个不变量；输入重复时“不同值对”和“不同下标对”怎样影响答案。
本地运行
示例仅使用 Python 标准库，适用于 Python 3.10 及以上。把 example.py 与 test_example.py 保存到同一个目录，在该目录运行：
python example.py
python -m unittest -v test_example.py
测试检查本文列出的边界；新增练习仍需自己补充断言。