Sunday面试指南

Python 字典底层是什么结构?为什么查找快,还能保留插入顺序?

下面是模拟面试对话,用来讲解本题,不是真实面经。

🧑‍💻 面试官:Python 字典为什么查找快?

🙋‍♂️ 我:它用哈希表,根据 key 找到 value。

🧑‍💻 面试官:两个 key 算到同一个位置,会覆盖吗?

🙋‍♂️ 我:还需要继续判断它们是不是同一个键。

🧑‍💻 面试官:那哈希位置和插入顺序怎么同时保留?更新旧键会把它挪到最后吗?

字典的查找位置和遍历顺序承担不同工作。先理解这两条路径,就不会把插入顺序当成排序。

面试速答(60 秒版)

Python 的 dict 是键值映射。CPython 使用哈希表相关结构,通过键的哈希值缩小查找范围,再结合键的相等关系确认目标。

哈希冲突不表示新数据必须覆盖旧数据。不同键可能产生冲突,实现会继续寻找合适位置,最坏情况下查找也可能变慢。

同时,Python 3.7 起把保持插入顺序作为 dict 的语言保证。它保存的是加入的先后顺序,并没有按键大小自动排序。更新已有键的值通常保留原来的位置,删除后再加入则会进入末尾。

因此,回答时可以把查找和遍历分开讲。平均查找快,和遍历时按插入顺序走,可以通过不同的内部安排同时做到。

字典的查找与顺序分别怎么看

知识点详解:查一个键和遍历全部键,走的是不同路径

先看一次键查询需要做什么

假设 settings 保存几个配置项。读取 settings[“timeout”],程序不希望每次都从第一个配置开始逐条找。

哈希值可以帮助它定位候选位置。不过,候选位置里有一个键,不代表它就是 timeout。实现还要确认键是否匹配;遇到冲突,需要按规则继续探查。

在 CPython 3.11 的常见字典布局里,有负责定位的索引区域,也有保存条目的区域。源码还包含共享键等不同形态,下面用普通字典解释主要关系,不把一张简图当成所有布局的完整源码。

冲突为什么不会直接覆盖?

假设两个不同配置名碰到相同的候选位置。字典需要能同时保存它们,所以“算到同一个位置”只是查找过程遇到了冲突。

已有条目的键相等,才会按映射语义更新对应值;键不同,则继续找到可以使用的位置。CPython 使用开放寻址相关的探查方式,这与给每个桶挂一条链表不是同一种实现。

通常说字典查询平均 O(1),隐含了哈希和数据分布等条件。大量冲突、复杂的哈希或比较方法,都可能增加成本。这个结论也没有保证任意自定义键的比较永远便宜。

碰到同一位置,还要确认键

插入顺序,是另外一件事

对于普通字典,可以把按加入顺序组织的条目和负责查找的索引分开理解。查一个键时利用索引,遍历时按条目顺序前进。

因此,先插入 b,再插入 a,遍历通常仍是 b、a。下面检查更新和删除重加。TS 使用 Map 对照相近的插入顺序行为,Map 的键规则和底层实现仍与 Python dict 不同。

values = {"b": 2, "a": 1}
values["b"] = 3
print(list(values))       # ['b', 'a']
del values["b"]
values["b"] = 4
print(list(values))       # ['a', 'b']

如果界面需要按名字排序,仍然要明确排序规则。保持插入顺序不能代替排序,也不能替你保证上游每次按相同顺序构造字典。

更新值与删除重加,顺序不同

扩容和删除会影响哪些工作?

加入的条目多了,索引空间需要调整。扩容要为条目重新组织查找结构,因此某一次插入可能承担比平时更多的工作。

删除以后,查找路径也不能简单被截断,否则后面因为冲突放下的键可能再也找不到。实现会保留必要的删除状态,并在合适时机整理结构;具体阈值与布局要跟着版本源码确认。

这些都解释了为什么字典不能无限增长而没有成本。项目里可以分别测查找耗时、构造耗时和内存占用,不拿一次小字典查询的结果推断大规模表现。

本题不展开可哈希对象的完整条件,那部分已经有单独文章。依据:CPython 3.11 dictobject.c、Python 3.11 dict 顺序规则。

扩容整理索引,成员仍有顺序

面试官继续追问

已有键重新赋值,会重新占一个顺序位置吗?

普通更新保留这个键的位置。删除以后再添加,是一次新的插入,应区别处理。

dict 有序,可以当作排行榜吗?

只有插入顺序,没有按分数排序的保证。排行榜还要规定比较规则及同分时的处理。

遍历时添加或删除键可以吗?

结构变化可能导致 RuntimeError 或遍历不完整。需要修改结构时,先明确使用快照、收集待删键还是构造新字典。

面试速记卡

  • 哈希帮助定位候选,匹配键仍需要确认。
  • 冲突不等于覆盖,相等键更新才符合映射语义。
  • dict 保持插入顺序,不自动按键排序。
  • 旧键更新通常位置不变,删除重加进入末尾。
  • 平均 O(1) 有条件,扩容、冲突和比较都可能增加成本。

公司面试真题

真题根据求职者公开面经整理,题意经过概括,非逐字原话或公司官方题库;本文为 Sunday 的独立解析。

  • 字节跳动 · 测试开发(国际化) · 原帖未明确批次

    Python 字典的底层怎样实现,哈希冲突怎样寻址?(题意整理)

    字节国际化 测开一面 ↗
    原帖发布于 2023-09-08

  • 字节跳动 · 测试开发 · 原帖未明确批次

    Python 字典有什么特点?(题意整理)

    字节测开面经 ↗
    原帖发布于 2025-09-16

浏览公司面试真题 →
简历汪永久免费在线制作简历,模板直接套用、导出无水印,永久免费、下载免费,不需要付费解锁任何功能。去写简历