列表与字典的底层实现
就讲四个东西：动态数组的过度分配、Timsort、紧凑哈希表、开放寻址。
- 理解列表的动态数组和过度分配策略
- 理解 append 均摊 O(1) 的原因
- 理解字典的紧凑哈希表实现
- 理解字典有序性的来源
列表与字典的底层实现
list 和 dict 是 Python 中最常用的数据结构。理解它们的底层实现，能帮你选对数据结构，避开性能陷阱。
列表：动态数组
Python 的 list 本质是一个 C 动态数组，存储的是 PyObject 指针（8 字节/个）。它不是链表！
因为过度分配预留了空间，大多数 append 直接放入空闲槽位，时间复杂度是 O(1)。偶尔需要重新分配加复制，时间复杂度是 O(n)。但 n 次 append 的总时间是 O(n)，所以均摊下来是 O(1)。这和 Java ArrayList、C++ vector 的策略一样。
列表操作的复杂度
insert(0) 和 pop(0) 是 O(n)，因为要移动整个数组。如果需要频繁在头部操作，用 collections.deque（双端队列，两端 O(1)）。in 操作在 list 中是 O(n)，在 set/dict 中是 O(1)——成员检查用 set！
Timsort：Python 的排序算法
list.sort() 和 sorted() 用的是 Timsort，是 Tim Peters 给 Python 做的，把归并排序和插入排序结合起来的。
字典：紧凑哈希表
Python 3.6 起 dict 改用紧凑哈希表，查找是 O(1)、还省内存；插入顺序在 CPython 3.6 还只是实现细节，从 Python 3.7 起才成为官方语言保证。
dict/set 的 in 是 O(1)，list 的 in 是 O(n)——大数据量成员检查一定用 set。字典的 key 必须可哈希（不可变类型），list/dict 不能做 key，tuple 可以（如果元素都不可变）。字典在 CPython 3.7+ 保证插入顺序，但不要依赖这个写业务逻辑（用 OrderedDict 表达意图）。遍历字典时不要修改字典大小，会报 RuntimeError。
字典操作的复杂度
哈希冲突与开放寻址
当两个 key 的哈希值映射到同一个槽位时，发生冲突。CPython 用开放寻址法（open addressing）解决：
开放寻址：冲突时找下一个空槽
探测序列：线性探测: h, h+1, h+2, ... （简单但容易聚集）二次探测: h, h+1, h+4, h+9, ...随机探测: CPython 用伪随机扰动（基于 hash 值）CPython 的探测公式（简化）：perturb = hashidx = (idx * 5 + perturb + 1) & maskperturb >>= 5为什么不用链式地址（链表）？开放寻址对 CPU 缓存更友好（连续内存）但删除困难（需要墓碑标记 DUMMY）
负载因子（已用槽位/总槽位）超过 2/3 时，字典会扩容（翻倍）。
在列表头部 insert(0, x) 的时间复杂度是？
Python 3.7+ 字典的什么特性成为官方保证？
资深工程师加餐
底层原理 · 大厂视角 · 工程经验，点卡片展开
with 语句等价于 try/finally：无论正常结束还是中途抛异常，退出时都会执行清理（关文件、释放锁、断开连接）。实现方式有两种：类里写 __enter__/__exit__，或用 contextlib.contextmanager 把生成器变成上下文管理器。凡是「打开了必须关闭/获取了必须释放」的资源，都应该用 with 托管。
挑战任务
性能对比器
对比 list 和 set 的成员检查性能，用 10 万元素验证 set 的 O(1) 优势。
课后作业
用 deque 优化
就用 collections.deque 实现高效队列，支持两端 O(1) 添加和弹出。