数据类型与内置结构
四种内置容器是 Python 的日常主力。面试主线：每种结构的底层实现、复杂度、什么时候用哪个。
底层实现与复杂度
| 结构 | 底层 | 查找 | 插入/追加 | 特点 |
|---|---|---|---|---|
| list | 动态数组（连续内存） | O(n) | 尾部摊还 O(1)，头部 O(n) | 按下标访问 O(1) |
| dict | 哈希表 | O(1) 均摊 | O(1) 均摊 | 3.7+ 保插入序 |
| set | 哈希表（只存键） | O(1) 均摊 | O(1) 均摊 | 去重、集合运算 |
| tuple | 定长数组 | O(n) | 不支持 | 不可变、可哈希 |
list 是动态数组：底层是连续内存的指针数组（ob_item），所以按下标访问 O(1)。扩容策略是倍增（约 1.125 倍），所以 append 摊还 O(1)；insert(0, x) 要搬所有元素，O(n)。
dict/set 是哈希表：键算哈希定位桶，冲突用开放寻址（CPython）。均摊 O(1)，但扩容（load factor 超 2/3）时要 rehash，单次操作可能 O(n)。dict 的键必须可哈希（不可变对象），这就是不可变类型能当键的原因。
dict 从 3.7 起保证插入顺序（3.6 是 CPython 实现细节，3.7 成为语言规范）。这不是“有序字典”（不按键排序），只是插入序。
推导式
squares = [x * x for x in range(10)] # 列表推导
even = {x for x in nums if x % 2 == 0} # 集合推导
mapping = {k: v for k, v in pairs} # 字典推导
gen = (x * x for x in range(10)) # 生成器表达式(惰性!)- 推导式比 for 循环快（C 层执行），可读性好
- 生成器表达式是惰性的：不一次生成全部，适合大序列（见迭代器篇）
- 嵌套推导可读性差，超过两层用普通循环或拆函数
常用操作与陷阱
| 操作 | 复杂度 | 说明 |
|---|---|---|
x in list |
O(n) | 大 list 判存在很慢，换 set |
x in dict/set |
O(1) | 查重的正确结构 |
list.count / index |
O(n) | 遍历 |
dict.get(k, default) |
O(1) | 安全取值 |
collections.deque |
两端 O(1) | 需要双端操作时替代 list |
高频优化点：“判断是否存在”一律用 set，list 的 in 是 O(n)，数据量大时差别巨大。
面试追问
- list 为什么 append 快、insert(0) 慢？ 动态数组：尾部追加摊还 O(1)（倍增扩容），头部插入要搬移全部元素 O(n)
- dict 怎么做到 O(1)？ 哈希表：键哈希定位桶，开放寻址处理冲突。均摊 O(1)，扩容 rehash 时单次 O(n)
- dict 有序吗？ 3.7+ 保证插入顺序，不是排序序。需要按键排序用 sorted() 或 OrderedDict
- 为什么 dict 的 key 要不可变？ 哈希表依赖键的哈希值稳定，可变对象哈希会变，破坏查找
- 列表推导和生成器表达式的区别？ 前者立即生成全部（占内存），后者惰性逐个产出（省内存）。大序列用生成器