字典是在 Python 3.6+ 中排序的吗？

字典是在 Python 3.6+ 中排序的吗？

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

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

从 Python 3.7 开始，这是一个有保证的语言特性，而不仅仅是一个实现细节。 From a python-dev message by GvR：

让它如此。 “字典保持插入顺序”是裁决。谢谢！

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

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

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

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

第二个，dk_indices，保存 dk_entries 数组的索引（即，指示相应条目在 dk_entries 中的位置的值）。该数组充当哈希表。当一个键被散列时，它会导致存储在 dk_indices 中的索引之一，并且通过索引 dk_entries 来获取相应的条目。由于只保留索引，因此该数组的类型取决于字典的整体大小（在 32/64 位构建上，范围从 int8_t（1 字节）类型到 int32_t/int64_t（4/8 字节））

在之前的实现中，必须分配类型为 PyDictKeyEntry 且大小为 dk_size 的稀疏数组；不幸的是，这也导致了很多空白空间，因为该数组不允许超过 2/3 * dk_size 满 for performance reasons。 （并且空白空间仍然有 PyDictKeyEntry 大小！）。

现在情况并非如此，因为仅存储 必需 条目（已插入的条目）和 intX_t 类型的稀疏数组（X 取决于 dict 大小）2/3 * dk_size 已满保持。空白区域从类型 PyDictKeyEntry 更改为 intX_t。

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

如果有兴趣，您可以查看有关此功能的完整对话on Python-Dev，这是一本好书。

In the original proposal made by Raymond Hettinger，可以看到使用的数据结构的可视化，它抓住了这个想法的要点。

例如，字典：d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'} 当前存储为 [keyhash, key, value]: entries = [[' --', '--', '--'], [-8522787127447073495, 'barry', 'green'], ['--', '--', '--'], ['--' , '--', '--'], ['--', '--', '--'], [-9092791511155847987, 'timmy', 'red'], ['--', '- -', '--'], [-6480567542315338377, 'guido', 'blue']] 相反，数据应按如下方式组织：indexes = [None, 1, None, None, None, 0, None, 2 ] 条目 = [[-9092791511155847987, 'timmy', 'red'], [-8522787127447073495, 'barry', 'green'], [-6480567542315338377, 'guido', 'blue']]

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

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

[2]：新的字典实现通过更紧凑的设计在**内存方面表现得更好**；这是这里的主要好处。速度方面，差异不是那么大，有些地方新 dict 可能会引入轻微的回归（例如键查找），而在其他地方（想到迭代和调整大小）应该会提高性能。

总体而言，字典的性能，尤其是在现实生活中，由于引入了紧凑性而有所提高。

---

以下是回答最初的第一个问题：

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

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

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

dict 并不明确意味着是一个有序集合，因此如果您想保持一致并且不依赖于新实现的副作用，您应该坚持使用 OrderedDict。

让你的代码面向未来:)

关于该here存在争议。

编辑：Python 3.7 将保留此功能 see

---

更新：Guido van Rossum announced on the mailing list 从 Python 3.7 dict 开始，所有 Python 实现都必须保留插入顺序。

---

我想添加到上面的讨论中，但没有评论的声誉。

Python 3.8 在字典中包含 reversed() 函数（删除了与 OrderedDict.

现在可以使用 reversed() 以反向插入顺序迭代字典和字典视图。 （由 Rémi Lapeyre 在 bpo-33462 中贡献。）查看 python 3.8 中的新功能

我没有看到任何提及相等运算符或 OrderedDict 的其他功能，因此它们仍然不完全相同。

---

为了在 2020 年全面回答这个问题，我引用 official Python docs 中的几句话：

在 3.7 版更改: 字典顺序保证为插入顺序。这种行为是 CPython 3.6 的实现细节。

在 3.7 版更改: 字典顺序保证为插入顺序。

在 3.8 版更改: 字典现在是可逆的。

字典和字典视图是可逆的。

关于 OrderedDict 与 Dict 的statement：

有序词典就像普通词典一样，但具有一些与排序操作相关的额外功能。现在它们变得不那么重要了，因为内置的 dict 类获得了记住插入顺序的能力（这种新行为在 Python 3.7 中得到了保证）。

---

如果 order 对判断两个字典是否相等非常重要，您仍然需要使用 OrderedDict。
为了实现此功能，OrderedDict 使用更多内存（内部维护双向链表）

from collections import OrderedDict

a = {"a": 1, "b": 2}
b = {"b": 2, "a": 1}
c = OrderedDict({"a": 1, "b": 2})
d = OrderedDict({"b": 2, "a": 1})

print(a == b)  # True
print(c == d)  # False
print(a == c)  # True
print(a == d)  # True

---