Python list、tuple、dict 的底层实现
哪些公司问过
答案要点
- list 是存放对象指针的动态数组,下标访问 O(1),append 均摊 O(1)
- list 的头部、中间插入删除以及 in 判断都是 O(n)
- tuple 是不可变定长数组,更省内存,元素可哈希时自身可哈希
- dict 是开放寻址哈希表,3.6 起采用索引数组加条目数组的紧凑结构,保持插入顺序
- dict 的 key 必须可哈希,查找平均 O(1),填充超过约 2/3 时扩容
易错点
- 认为 list 里直接存储元素本身,实际存的是对象指针
- 认为 dict 冲突用链表法解决,CPython 用的是开放寻址
- 认为 tuple 一定可哈希,元素中有 list 时就不可哈希
面试官常见追问
- 为什么 list 不能作为 dict 的 key?
- 需要频繁在头部插入删除,用什么结构?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。