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

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

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

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

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

250616 次浏览
小开

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

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

我想留档的这句话其实已经足够回答你的问题了

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

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

让你的代码成为未来的证明：）

有一个关于这里的争论。

编辑：Python 3.7将保留此功能看到

小开
最佳答案

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

它们是有序插入[1]。

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

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

让它这样做。“迪克特保持插入顺序”是裁决。谢谢！

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

Python3.6字典实现如何在保留元素顺序的同时比旧的执行更好[2]？

基本上，由保持两个数组。

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

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

在前面的实现中，必须分配类型为PyDictKeyEntry和大小为dk_size的稀疏数组；不幸的是，它也导致了大量的空空间，因为该数组不允许超过2/3 * dk_size满出于性能原因。

现在情况并非如此，因为只存储了选填/必填条目（已插入的条目），并且保留了类型为intX_t（X取决于字典大小）2/3 * dk_size的稀疏数组满。空格从类型PyDictKeyEntry更改为intX_t。

因此，显然，创建PyDictKeyEntry类型的稀疏数组比存储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存在的情况下，“有序”暗示了“字典”对象*不提供*的进一步行为。OrderedDICT是可逆的，提供顺序敏感的方法，并且主要提供顺序感知的相等测试 (`==`, `! =`). `字典目前不提供任何这些行为/方法。
[2]：新的字典实现通过更紧凑的设计在内存方面表现得更好；这是这里的主要好处。在速度方面，差异并不是那么剧烈，有些地方新字典可能会引入轻微的回归（例如，键查找），而在其他地方（想到迭代和调整大小）应该会有性能提升。 总的来说，词典的性能，特别是在现实生活中，由于引入了紧凑性而提高。
小开

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

小开

我想补充上面的讨论，但没有评论的名声。

Python 3.8包含字典上的reversed()函数（删除了OrderedDict的另一个区别。

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

我没有看到任何提及等号操作符或OrderedDict的其他功能，所以它们仍然不完全相同。

小开

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

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

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

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

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

A声明关于OrderedDlicvs Dlic：

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

小开

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


提交答案