你观察得太敏锐了！确实，Python 3.6之后的普通字典并没有像OrderedDict那样用额外的列表或链表来记录插入顺序——它的实现要巧妙得多，完全是在底层哈希表的结构上做了优化，而且几乎没增加内存开销。

先说说旧字典的痛点 #

在Python 3.5及更早版本里，字典的底层是一个单一的哈希桶数组：每个桶里要么是空的，要么存着键、值、哈希值的组合。插入时通过哈希计算确定桶的位置，所以插入顺序和实际存储顺序完全脱节，遍历字典的键时顺序是随机的（取决于哈希值和冲突情况）。

3.6+ 字典的双数组结构 #

CPython团队重构了字典的底层实现，把原来的单一桶数组拆成了两个独立的数组：

• indices数组：这个数组的元素是小整数，包含哈希值的高位信息和一个标记位（用来区分空桶、已删除桶、有效桶）。数组的长度和哈希表的容量一致，它的作用是快速定位有效条目在entries数组中的位置。
• entries数组：这个数组是按插入顺序来存储完整的条目（键、值、哈希值）的。新插入的元素总是追加到数组的末尾，而哈希冲突或者删除操作留下的空槽会被后续的插入操作复用，但不会打乱已有的顺序。

为什么内存开销没明显增加？ #

这种拆分并没有额外引入大的存储结构：

• indices数组的每个元素是紧凑的小整数（比如在64位系统上是8字节），比原来每个桶存完整的键值对要小很多。
• entries数组虽然按顺序存储，但空槽只是标记为可复用，不会占用额外的内存空间。

对比OrderedDict，它是在普通字典的基础上额外维护了一个双向链表，每个链表节点还要存储前后指针，这就是为什么你看到它的内存占用（1304字节）远大于普通字典的原因——链表带来了大量的额外开销。

怎么实现有序遍历？ #

当你遍历字典的键、值或项时，Python会按顺序遍历indices数组，找到所有标记为有效的索引，然后根据这些索引去entries数组里按插入顺序取出对应的元素。这样既保留了哈希表的高效查询特性，又自然实现了插入顺序的保留。

另外要注意：Python 3.6时这还只是CPython的一个实现细节，到了Python 3.7，这个有序特性被正式写入了Python语言规范，所有符合规范的Python实现都必须支持字典的插入顺序保留。

内容的提问来源于stack exchange，提问作者Rares Dima