Python 3.7+ 中 dict 保序是如何实现的？
Python 3.7+ 的 dict 通过 entries（有序紧凑存储）和 indices（稀疏索引）双数组结构实现插入顺序保证与 O(1) 查找，无需额外排序或链表；其保序是语言规范强制、零开销的，不同于需维护双向链表的 OrderedDict。
Python 3.7+ 中 dict 保证插入顺序，不是靠额外维护一个顺序列表，而是通过重构底层存储结构实现的——核心是把“哈希表”和“插入序列表”合二为一，用更紧凑、更高效的方式同时满足查找快和有序两个目标。
底层用两个数组协同工作
CPython 3.7+ 的 dict 内部不再只用传统哈希表（一个 key-value 混存的稀疏数组），而是引入两个分离又关联的数组：
-
entries 数组（dense）：按插入顺序线性存放所有键值对（
key,value,hash），类似一个紧凑的记录表； -
indices 数组（sparse）：大小是 entries 的约 2–4 倍，每个位置存的是该 hash 槽对应在 entries 中的索引（或特殊标记如
DKIX_EMPTY/DKIX_DUMMY）。
查找时，先用 key 的 hash 定位 indices 中的槽位，再跳转到 entries 对应位置取值——既保持 O(1) 平均查找性能，又天然保留插入顺序（因为 entries 就是按序追加的）。
插入过程自动维持顺序
每次调用 dict[key] = value 时：
- 计算 key 的 hash，映射到 indices 的某个位置；
- 若该位置为空，就在 indices 中写入新 entry 在 entries 中的下标（即当前 entries 长度）；
- 然后把 (key, value, hash) 追加到 entries 末尾。
没有“额外排序”，也没有“链表维护”，顺序就是追加的自然结果。删除操作稍复杂（需标记 dummy 并延迟清理），但不破坏已有 entry 的相对顺序。
与 OrderedDict 的本质区别
Python 3.7+ 的 dict 保序是语言规范强制要求，且零额外开销；而 collections.OrderedDict 是纯 Python 实现（3.7 前）或 C 优化版（3.7+ 后），它额外维护双向链表来记顺序，内存占用更高、操
move_to_end() 或 popitem(last=False) 等特有方法，否则普通有序需求直接用 dict 即可。
注意：保序仅针对插入顺序，不等于“稳定排序”
dict 本身不提供排序能力。如果你遍历 dict.keys()、dict.items()，看到的是插入顺序；但如果你对 keys 做 sorted(dict.keys())，得到的是字典序，跟插入无关。保序 ≠ 自动排序，只是“你放进去什么样，拿出来还是那个样”。
