字典在 Python 3.6 中是有序的吗？

Question

从 Python 3.6 开始，字典是按插入顺序排列的。它被描述为 CPython 实现细节而不是语言功能。 文件 指出：

dict() 现在使用 PyPy 首创 的“紧凑”表示。与 Python 3.5 相比，新的 dict() 的内存使用量减少了 20% 到 25%。 PEP 468 （在函数中保留 **kwargs 的顺序。）由此实现。这个新实现的顺序保留方面被认为是一个实现细节，不应依赖（这可能会在未来改变，但在更改语言规范之前，希望在语言中使用这个新的 dict 实现几个版本为所有当前和未来的 Python 实现强制保留顺序语义；这也有助于保持与旧版本语言的向后兼容性，其中随机迭代顺序仍然有效，例如 Python 3.5）。 （由 INADA Naoki 在 issue 27350 中贡献。想法 最初由 Raymond Hettinger 提出。）

新字典实现如何在保持元素顺序的同时比旧字典执行得更好？

---

2017 年 12 月更新： dict 保证 Python 3.7 保留插入顺序

原文由 Chris_Rands 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

字典是否在 Python 3.6+ 中排序？

它们是 插入顺序 的[1] 。

从 Python 3.6 开始，对于 Python 的 CPython 实现，字典 _会记住插入项目的顺序_。 _这被认为是 Python 3.6 中的一个实现细节_；你需要使用 OrderedDict 如果你想要在 Python 的其他实现（和其他有序行为[1] ）中 保证 插入顺序。

从 Python 3.7 开始，这是一个有保证的语言特性，而不仅仅是一个实现细节。 来自 GvR 的 python-dev 消息：

做到这一点。 “字典保持插入顺序”是裁决。谢谢！

这仅仅意味着 _您可以信赖它_。如果 Python 的其他实现希望成为 Python 3.7 的一致实现，它们也必须提供插入顺序字典。

---

Python 3.6 字典实现如何在保持元素顺序的同时比旧版本执行得更好[2] ？

本质上，通过 _保留两个数组_。

• 第一个数组 dk_entries 以插入顺序保存字典的条目（ 类型为 PyDictKeyEntry ）。保留顺序是通过这是一个仅附加数组来实现的，其中新项目总是插入到末尾（插入顺序）。

• 第二个 dk_indices 包含 dk_entries 数组的索引（即指示相应条目在 dk_entries 中的位置的值）。该数组充当哈希表。当一个键被散列时，它会导致存储在 dk_indices 中的索引之一，并通过索引 dk_entries 获取相应的条目。由于仅保留索引，因此此数组的类型取决于字典的总体大小（范围从类型 int8_t ( 1 字节）到 int32_t int64_t 0e -6fae --- ( 4 / 8 bytes) on 32 / 64 bit builds)

在之前的实现中，必须分配一个稀疏数组类型 PyDictKeyEntry 和大小 dk_size ；不幸的是，由于 性能原因，该数组不允许超过 2/3 * dk_size full ，因此它也导致了很多空白空间。 （并且空白区域 仍然 有 PyDictKeyEntry 大小！）。

现在情况并非如此，因为只存储了 所需 的条目（那些已插入的条目）和类型稀疏数组 intX_t （ X 取决于字典大小） 2/3 * dk_size 保存完整。空白空间从类型 PyDictKeyEntry 更改为 intX_t 。

因此，显然，创建一个类型为 PyDictKeyEntry 的稀疏数组比用于存储 int s 的稀疏数组需要更多的内存。

如果有兴趣，您可以 在 Python-Dev 上 查看有关此功能的完整对话，这是一本不错的读物。

---

在 Raymond Hettinger 提出的最初提议中，可以看到所使用的数据结构的可视化，它抓住了想法的要点。

例如字典：

 d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

当前存储为 [keyhash, key, value]：

 entries = [['--', '--', '--'],
           [-8522787127447073495, 'barry', 'green'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           [-9092791511155847987, 'timmy', 'red'],
           ['--', '--', '--'],
           [-6480567542315338377, 'guido', 'blue']]

相反，数据应按如下方式组织：

 indices =  [None, 1, None, None, None, 0, None, 2]
entries =  [[-9092791511155847987, 'timmy', 'red'],
            [-8522787127447073495, 'barry', 'green'],
            [-6480567542315338377, 'guido', 'blue']]

正如您现在可以直观地看到的那样，在最初的提议中，很多空间基本上是空的，以减少碰撞并加快查找速度。使用新方法，您可以通过在索引中将稀疏性移动到真正需要的地方来减少所需的内存。

---

[1]：我说“有序插入”而不是“有序”，因为随着 OrderedDict 的存在，“有序”暗示了 `dict` 对象*不提供*的进一步行为。 OrderedDicts 是可逆的，提供顺序敏感的方法，主要是提供顺序敏感的相等性测试（`==`、`!=`）。 `dict` 目前不提供任何这些行为/方法。

---

[2]：新的字典实现通过更紧凑的设计表现出更好的**内存明智**；这是这里的主要好处。在速度方面，差异不是那么大，新字典在某些地方可能会引入轻微的回归（ 例如键查找），而在其他地方（想到迭代和调整大小）应该会出现性能提升。总的来说，字典的性能，尤其是在现实生活中，由于引入了紧凑性而得到改善。

原文由 Dimitris Fasarakis Hilliard 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

下面是回答原来的第一个问题：

我应该在 Python 3.6 中使用 dict 还是 OrderedDict ？

我认为文档中的这句话实际上足以回答您的问题

这个新实现的顺序保持方面被认为是一个实现细节，不应该被依赖

dict 没有明确表示是一个有序集合，所以如果你想保持一致而不依赖于新实现的副作用，你应该坚持使用 OrderedDict 。

让你的代码面向未来:)

这里 有一个关于这个的争论。

编辑： Python 3.7 将保留此功能， 请参阅

原文由 Maresh 发布，翻译遵循 CC BY-SA 3.0 许可协议