python字典底层是哈希表，通过hash()和取模定位bucket，冲突时用伪随机探测；查找平均o(1)，冲突多或装载因子超2/3时变慢；键须不可变以保证哈希稳定；3.7+保持插入顺序靠entries数组索引实现。
Python字典的底层实现是哈希表（Hash Table），这是它能在平均情况下实现 O(1) 时间复杂度完成查找、插入和删除操作的关键。
哈希表如何组织数据
字典内部维护一个连续的数组（称为“散列表”或“bucket数组”），每个位置（bucket）存储一个键值对的引用（或空值）。当插入一个键值对时：
- Python 对键调用
hash()函数，得到一个整数哈希值； - 用该哈希值对数组长度取模（
hash % table_size），确定初始索引位置； - 若该位置为空，直接写入；若已被占用（哈希冲突），则按“开放寻址法”中的“伪随机探测”（实际为线性探测变种，含扰动机制）寻找下一个空位。
为什么查找快？又为何有时变慢？
理想情况下，每个键映射到唯一桶位，查找只需一次哈希+一次地址访问。但现实存在哈希冲突：
- 相同哈希值（不同键）→ 探测序列延长 → 查找需多次比较；
- 大量冲突会使性能退化至接近 O(n)（极端情况，如所有键哈希全相同）；
- Python 会动态扩容：当装载因子（已用桶数 / 总桶数）超过约 2/3 时，自动重建更大哈希表并重散列所有项，维持效率。
键必须是可哈希的，原因在此
哈希表依赖键的 不可变性 和 稳定哈希值：
立即学习“Python免费学习笔记（深入）”；
- 如果键在字典中被修改（如把 list 当作键），其哈希值可能变化，后续再也无法定位原位置；
- 因此只有不可变类型（str、int、tuple 等）默认可哈希；自定义类需显式定义
__hash__和__eq__才能作键； - 字典本身不可哈希，不能作为其他字典的键——因为它是可变的，且没有固定哈希值。
小技巧：理解 dict 的内存与顺序
从 Python 3.7 起，字典保持插入顺序，但这不是靠额外链表，而是哈希表设计的副产品：
- 插入时新元素总追加到一个独立的“entries数组”末尾；
- 哈希表只存该 entries 数组的索引，而非键值本身；
- 这样既保留哈希效率，又天然记录顺序，且删除时通过标记“dummy slot”避免移动元素破坏顺序。
