Python字典是基于开放寻址法的哈希表，平均查找O(1)但最坏O(n)，依赖键的哈希分布；3.7+插入有序属实现细节而非规范；键须可哈希；defaultdict比setdefault更高效且仅一次哈希。
Python 字典不是“有序容器”或“线程安全结构”，它本质是基于开放寻址法的哈希表实现，底层用 PyDictObject 结构管理键值对数组、哈希缓存与探查序列。
字典的哈希冲突处理：为什么 dict 查找平均 O(1)，但最坏 O(n)
Python 字典在插入时对键调用 hash()，取模映射到索引；若位置已被占用，按固定探查序列（伪随机偏移）寻找下一个空槽。这叫“开放寻址 + 二次哈希”。
常见错误现象：dict.keys() 在 CPython 3.7+ 虽然保持插入顺序，但这只是实现细节，不是语言规范——你不能依赖它在 PyPy 或旧版本中表现一致。
- 键必须是可哈希的：
list、dict、set直接报TypeError: unhashable type - 自定义类要支持字典键，必须正确定义
__hash__和__eq__，且__hash__返回值在对象生命周期内不可变 - 哈希碰撞高发场景（如大量字符串仅末位不同）会显著拉长探查链，使单次
__getitem__退化为线性扫描
dict.setdefault() 与 collections.defaultdict 的本质区别
setdefault 是原子操作：键存在则返回值，不存在则插入默认值并返回；而 defaultdict 是子类封装，在 __missing__ 钩子中自动构造新值，不触发 KeyError。
立即学习“Python免费学习笔记（深入）”；
性能差异明显：defaultdict(list) 比反复写 d.setdefault(k, []).append(v) 快约 15–20%，因为后者每次都要计算两次哈希（一次查、一次设），且涉及条件分支。
from collections import defaultdict推荐：一次哈希，无分支
d = defaultdict(list) d['a'].append(1)
不推荐：两次哈希 + 条件判断
d2 = {} d2.setdefault('a', []).append(1)
-
defaultdict的工厂函数在每次缺失键访问时调用，若工厂开销大（如defaultdict(lambda: expensive_init())），可能引发意外性能问题 -
setdefault支持任意表达式作为默认值，而defaultdict只接受可调用对象 -
defaultdict不会出现在dict.keys()中，直到首次访问该键；setdefault立即写入
内存布局真相：为什么小字典比大字典“更稀疏”
CPython 字典初始分配 8 个桶（slot），负载因子（used / size）超过 2/3 就扩容，新大小为 ≥2×旧大小的最小 2 的幂。扩容后所有键值对重哈希，旧数组丢弃。
这意味着：一个只有 3 个元素的 dict 实际占用了 8 个指针空间（64 位系统下约 64 字节），而装满 512 个元素的字典可能只分配 1024 个桶——看似浪费，实为保障平均查找性能。
- 用
sys.getsizeof(d)查看的是字典对象本身内存，不含键值对象的引用内容；真实内存占用需递归统计 -
dict.clear()不释放底层数组，只清空条目；再次插入仍复用原空间，避免频繁 realloc - 若需彻底释放内存，可赋值新字典：
d = {}（前提是无其他引用）
字典的“插入有序”在 3.7 是稳定行为，但它的底层逻辑仍是哈希驱动——顺序只是探查路径和插入时机的副产品，不是设计目标。真正需要强顺序语义时，应显式使用 collections.OrderedDict 或 Python 3.7+ 的 dict 并加注释说明版本约束。
