Python字典查找平均时间复杂度为O(1)，因其底层采用哈希表，通过哈希函数将键映射到固定内存位置，配合开放寻址法处理冲突，并在负载因子超阈值时自动扩容，实现均摊O(1)。
Python 的 dict 查找平均时间复杂度是 O(1)，核心原因在于它底层使用了**哈希表（hash table）**，通过哈希函数将键快速映射到内存中的固定位置，从而避免逐个比较。
哈希表让“找键”变成“算地址”
普通列表查找需要从头遍历，最坏 O(n)；而字典不遍历，它对键调用哈希函数（如 hash("name")），得到一个整数哈希值，再对这个值取模（比如 % 表大小），直接算出该键应该存放在哪个“桶”（bucket）里。只要哈希分布合理、冲突少，一次计算就能定位——这就是 O(1) 的来源。
实际中不是绝对 O(1)，但平均是
哈希冲突无法完全避免（不同键算出相同索引），Python 用“开放寻址法”解决：遇到冲突就线性探测下一个空位。只要负载因子（已用桶数 / 总桶数）控制得当（Python 默认扩容阈值是 2/3），平均探测次数趋近常数。所以是平均时间复杂度 O(1)，最坏情况（大量冲突+恶意输入）可能退化到 O(n)，但日常使用几乎不会遇到。
扩容机制保障效率不退化
当字典变大、负载因子超标时，Python 会自动重新分配更大内存，并把所有键值对重新哈希填入新表。虽然单次扩容是 O(n)，但它是均摊发生的——就像动态数组 append 那样，多次插入的均摊时间仍是 O(1)。
立即学习“Python免费学习笔记（深入）”；
键必须是可哈希的，否则没法算地址
只有不可变类型（如 str、int、tuple（且元素都可哈希））才能做字典键，因为它们的哈希值稳定、可预测。如果允许 list 当键，那它一变，哈希值就变，原来存的位置就找不到了——这会直接破坏哈希表逻辑。
