dict 和 set 的实现原理
Python 中 dict 和 set 的底层实现原理是什么？为什么查找操作的时间复杂度是 O(1)？
回答
Yahuda
dict 和 set 的底层实现是哈希表（Hash Table）。
- 存储时通过
hash()计算 key 的哈希值，映射到数组槽位 - 查找时直接计算哈希值定位，平均时间复杂度 O(1)
- Python 采用开放地址法解决哈希冲突
- 当负载因子超过 2/3 时自动扩容并 rehash
注意：dict 的 key 和 set 的元素必须是可哈希的（hashable），即实现了 __hash__() 和 __eq__() 方法。