dict底层与哈希

面试回答

常见问法

为什么 dict 查找快？什么对象可以当字典键？

回答

dict 本质上是哈希表，平均情况下可以接近 O(1) 查找。字典键要求可哈希，也就是：

• 哈希值在生命周期内稳定
• 支持相等性比较

因此常见可做键的是 int、str、tuple（前提是内部元素也可哈希），而 list、dict 通常不能做键。

data = {"name": "Tom", "age": 18}
print(data["name"])

追问

• 哈希冲突是怎么处理的
• 为什么可变对象通常不适合作键
• dict 和 set 在底层上有什么关系

原理展开

高频面试点有两个：

1. 为什么查找快：因为先算哈希，再定位槽位
2. 为什么键要可哈希：因为如果对象内容能变，哈希值就可能变化，字典内部索引关系会失效

key = (1, 2, 3)
mapping = {key: "ok"}

而下面不行：

# bad = {[1, 2]: "x"}  # TypeError

面试回答时不用展开 CPython 每个内部细节，但至少要说清： “dict 快在哈希索引，风险在冲突处理，前提是键必须稳定可哈希。”

易错点

• 把“可哈希”说成“不可变”而不解释原因
• 以为 dict 查找永远都是 O(1)
• 说不清 dict 和 set 都基于哈希思想