Python 字典为什么查询高效
Python 字典（dict）之所以查询效率非常高（平均时间复杂度为 O(1)），主要归功于其底层实现——哈希表（Hash Table）。
1. 核心：哈希表（Hash Table）
字典本质上是一个哈希表。哈希表是一种通过键（key） 直接映射到值（value） 存储位置的数据结构。
工作流程：
- 哈希函数（Hash Function）：
- 当你向字典中插入一个键值对（如
d['name'] = 'Alice'）时，Python 会先对键'name'调用其__hash__()方法，得到一个整数，称为哈希值（hash value） - 这个哈希值是确定性的：同一个键，每次计算得到的哈希值都相同。
- 不可变类型（如
str,int,tuple）都有__hash__方法，因此可以作为字典的键；而可变类型（如list,dict）没有，所以不能作为键。
- 当你向字典中插入一个键值对（如
- 索引计算（Indexing）：
- 哈希值通常是一个很大的整数，不能直接用作数组下标。
- Python 会将哈希值通过一个函数（通常是取模运算）映射到哈希表的槽位（slot） 索引上。例如：
index = hash(key) % table_size。
- 存储/查找：
- Python 直接访问计算出的索引位置，将值存储进去（插入）或读取出来（查找）。
- 由于数组的索引访问是 O(1) 操作，所以字典的查找/插入/删除平均也是 O(1)。
2. 处理哈希冲突（Collision）
不同的键可能产生相同的哈希值（或映射到同一索引），这称为哈希冲突。Python 字典使用了两种主要技术来解决：
a. 开放寻址法（Open Addressing）
- Python 字典主要使用基于开放寻址的哈希表。
- 当目标槽位已被占用时，它会按照一定的探测序列（如线性探测、二次探测）寻找下一个空闲槽位。
- Python 使用了一种优化的探测方式，能有效减少“聚集”（clustering）问题。
b. 键值对存储结构
- Python 字典的底层结构设计巧妙，它将哈希值、键、值作为一个整体存储。
- 在查找时，即使索引位置被占用，Python 会先比较哈希值，如果不同则直接跳过；如果相同，再比较键是否相等（
==）。 - 这种“先比哈希，再比键”的方式大大加快了查找速度，尤其是在哈希冲突较多时。
3. 动态扩容（Resizing）
- 哈希表的大小是固定的，但字典是动态的。
- 当字典中元素过多，导致装载因子（元素数 / 槽位数）过高时，哈希冲突概率上升，性能下降。
- Python 会在装载因子达到一定阈值（如 2/3）时，自动扩容：创建一个更大的哈希表，并将所有键值对重新哈希到新表中。
