Python 字典是使用最频繁的内置容器之一，它的查找速度极快，平均时间复杂度为 O(1)。这种速度并不是靠遍历键值对实现的，而是依赖哈希表将任意键映射到固定大小的存储区域。理解哈希表的工作方式以及 CPython 对字典的紧凑化改造，能够帮助你避开不必要的性能损耗，写出更高效的查找逻辑。
一、哈希表核心：从散列值到桶位置
哈希表之所以能实现常数级查找，关键在于它把键通过哈希函数转换成一个整数，再用这个整数直接计算存储位置。Python 中的 hash() 函数就是完成这个转换的入口。对于字符串、整数、元组等内置不可变类型，CPython 已经实现了高效且分布均匀的哈希算法。例如对一个字符串调用 hash('apple')，会得到一个在进程内稳定的散列值，字典内部再用这个散列值与当前表大小的掩码做按位与运算，就能确定该键应该落在哪个桶位置。
下面这段代码展示了最基础的定位过程：
key = 'apple' h = hash(key) mask = 7 # 假设表大小为 8 bucket_index = h & mask print(bucket_index)
实际场景中不可能所有键都得到不同的散列值，两个不同的键可能映射到同一个桶，这就是哈希碰撞。CPython 使用开放寻址法处理碰撞：当目标桶已经被占用时，会按照固定的探测序列继续查找下一个桶，直到找到匹配的键或遇到空槽。探测序列会混合散列值的高位信息，避免多个键集中在相邻位置，从而减少碰撞后的聚集现象。删除键时也不会直接把桶清空，而是留下一个伪删除标记，保证探测链不会因为空槽而中断。
正因如此，字典查找并非完全无条件的 O(1)。如果哈希函数分布很差，或者大量键故意产生相同散列值，探测次数就会上升，最坏情况下可能退化为线性查找。不过对于常规使用场景，内置类型的哈希质量足够好，平均探测次数通常接近一次。
二、CPython 字典的紧凑实现与查找流程
较新的 Python 版本对字典实现做了重要改造，核心变化是将索引表与键值对表分离。早期字典中每个桶直接保存键、值和散列信息，导致稀疏表也占用大量内存。紧凑实现则增加了一层索引表，索引表只存储槽位编号，而真正的键值对按插入顺序连续存放在 entries 表中。这样不仅减少了空槽的内存开销，还让连续插入的键值对在内存中相邻，大幅提升 CPU 缓存命中率。
查找一个键时，CPython 会先计算散列值，再通过索引表和掩码得到 entries 中的槽位编号，然后取出键对象与目标键进行比较。比较时先判断引用是否相同，如果不是同一个对象再调用 __eq__ 比较值。下面用简化代码模拟这个流程：
class CompactDict:
def __init__(self):
self.indices = [None] * 8
self.entries = []
def _find(self, key):
h = hash(key)
mask = len(self.indices) - 1
pos = h & mask
while self.indices[pos] is not None:
idx = self.indices[pos]
if self.entries[idx][0] == key:
return idx
pos = (pos + 1) & mask
return -1
当 entries 表的填充比例超过阈值时，字典会触发扩容。扩容不是简单地把数组变大，而是重新分配更大的索引表和 entries 表，并对所有已有键重新计算散列位置。这个过程称为重哈希，开销与当前键数量成正比。如果一开始就能预估键的数量，通过 dict.fromkeys() 或提前构造字典来减少扩容次数，能够显著降低插入阶段的时间消耗。
三、字典查找性能基准测试与优化实践
要直观感受字典查找有多快，可以把它跟列表的线性查找做对比。列表的 index() 方法需要从头逐个比较元素，时间复杂度是 O(n)，而字典通过哈希表定位，基本不受元素数量影响。下面的基准测试在 1 万个元素中反复查找，对比两种结构的耗时：
import timeit
n = 10000
keys = list(range(n))
d = {k: k for k in keys}
lst = list(keys)
def dict_lookup():
for k in keys:
_ = d[k]
def list_lookup():
for k in keys:
_ = lst.index(k)
print('dict lookup:', timeit.timeit(dict_lookup, number=100))
print('list lookup:', timeit.timeit(list_lookup, number=1))
在大多数机器上，字典查找 100 轮的总时间仍然远小于列表查找 1 轮的时间。随着 n 增大，列表查找的时间会按线性增长，而字典查找的时间几乎保持不变。这就是为什么当需要频繁判断元素是否存在或按键取值时，字典和集合是更合适的数据结构。
想让字典查找保持在最佳状态，可以从几个方面入手。第一，尽量使用 int、str、tuple 等内置不可变类型作为键，这些类型拥有高度优化的哈希实现。第二，不要用列表、字典等可变对象作键，它们无法哈希，会直接抛出 TypeError。第三，如果自定义类需要作键，应确保 __hash__ 计算足够快，并且与 __eq__ 的语义一致：相等的对象必须返回相同的散列值。第四，如果只需要判断键是否存在，不关心值，可以考虑使用集合取代字典，内存占用更小，查找性能同样优秀。
四、常见性能陷阱与规避方法
字典虽然高效，但如果使用不当也会出现性能问题。一个典型误区是使用可变对象作为键。列表、字典、集合本身不可哈希，直接用作键会报错：
bad_key = [1, 2, 3]
try:
{bad_key: 'value'}
except TypeError as e:
print(e)
另一个容易被忽视的问题是哈希碰撞攻击。如果攻击者能够构造出大量散列值相同的字符串键，字典的探测链会变得非常长，查找性能会显著下降。现代 Python 默认启用了字符串哈希随机化，每次进程启动时都会引入随机种子，使得攻击者难以预测散列值，从而降低这类攻击的风险。不过对于来自不可信来源的大量键，仍然需要保持警惕。
此外，在循环中频繁重建字典也会带来不必要的开销。比如每次迭代都创建一个新的字典再查询，不如在循环外构建一次并复用。如果键集合是固定的，可以提前用 dict.fromkeys(keys) 分配好字典，再通过赋值更新值。对于大量小型映射关系，使用 namedtuple 或 dataclass 有时比大量独立字典更节省内存，因为对象布局更紧凑，属性访问也避免了哈希计算。
整体来看，Python 字典极速查找的本质是哈希表加开放寻址，再配合紧凑内存布局降低缓存未命中。理解这套机制后，你可以在选择数据结构时更有依据，也能通过简单的键设计和预分配策略，让字典查找始终保持在接近 O(1) 的水平。