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

问题描述：

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

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

在保留元素顺序的同时，新字典实现如何比旧字典表现更好？

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

解决方案 1：

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

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

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

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

就这样吧。“Dict 保持插入顺序”是裁决。谢谢！

这仅仅意味着你可以依赖它。如果其他 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（4/8字节）32/64位构建）

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

现在情况不同了，因为只存储了所需的条目（已插入的条目），并且保留了类型为 s full的稀疏数组intX_t（X取决于字典大小） 。空白空间从类型更改为。2/3 * dk_size`PyDictKeyEntry`intX_t

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

如果有兴趣的话，你可以在 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]：新字典实现的设计更紧凑，因此在内存方面表现更好；这是主要优点。速度方面，差异并不大，新字典可能会在某些地方引入轻微的回归（例如键查找），而在其他地方（想到迭代和调整大小）应该会提高性能。
总体而言，由于引入了紧凑性，字典的性能（尤其是在实际情况下）得到了改善。

解决方案 2：

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

我应该在 Python 3.6 中使用dict或吗？OrderedDict

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

此新实现的保序方面被视为实现细节，不应依赖

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

让你的代码适应未来:)

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

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

解决方案 3：

更新：Guido van Rossum在邮件列表中宣布，从 Python 3.7 开始dict，所有 Python 实现都必须保留插入顺序。

解决方案 4：

我想参与上述讨论，但没有资格发表评论。

Python 3.8reversed()在字典中包含了该函数（从中删除了另一个差异）OrderedDict。

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

我没有看到任何提及相等运算符或其他特征，OrderedDict所以它们仍然不完全相同。

解决方案 5：

为了在 2020 年全面回答这个问题，让我引用Python 官方文档中的几句话：

在 3.7 版中更改：保证字典顺序与插入顺序一致。此行为是从 3.6 版开始的 CPython 实现细节。

在 3.7 版更改: 保证字典顺序与插入顺序一致。

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

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

关于OrderedDict与Dict的声明：

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

解决方案 6：

在 3.7 版中更改：保证字典顺序与插入顺序一致。此行为是从 3.6 版开始的 CPython 实现细节。