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

小编典典

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

all

与以前的版本不同，字典在 Python 3.6 中排序（至少在 CPython
实现下）。这似乎是一个重大变化，但它只是文档中的一小段。它被描述为 CPython 实现细节而不是语言特性，但也暗示这可能在未来成为标准。

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

以下是文档中的文本：

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

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

阅读 155

2022-03-04

共1个答案

小编典典

字典是在 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 的一致实现，它们还必须提供插入有序字典。

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

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

第一个数组，按插入的顺序dk_entries保存字典的条目（类型PyDictKeyEntry为）。保留顺序是通过这是一个仅附加的数组来实现的，其中总是在末尾插入新项目（插入顺序）。
第二个，dk_indices，保存dk_entries数组的索引（即，指示相应条目在中的位置的值dk_entries）。该数组充当哈希表。当一个键被散列时，它会导致存储在其中的一个索引，dk_indices并通过 indexing 获取相应的条目dk_entries。由于只保留索引，因此该数组的类型取决于字典的整体大小（范围从类型int8_t（1字节）到int32_t/ int64_t（4/8字节）32/64位构建）

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

现在情况并非如此，因为只存储了所需的条目（那些已插入的条目），并且保留了一个稀疏类型的数组intX_t（X取决于 dict 大小）2/3 * dk_sizes full。空白处从 typePyDictKeyEntry变为intX_t.

因此，很明显，创建一个类型PyDictKeyEntry的稀疏数组比存储ints 的稀疏数组需要更多的内存。

如果有兴趣，您可以在 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 是可逆的，提供顺序敏感的方法，主要是提供顺序敏感的相等测试（==、!=）。dicts
目前不提供任何这些行为/方法。

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

2022-03-04