Python-为什么字典和集合中的顺序是任意的？

Question

我不明白在python中如何通过“任意”顺序循环遍历字典或集合。 我的意思是，这是一种编程语言，所以语言中的一切都必须100%确定，对吗？Python必须有某种算法来决定选择字典或集合的哪个部分，1，2等等。
我错过了什么？

Answer 1

顺序不是任意的，而是取决于字典或集合的插入和删除历史，以及特定的Python实现。对于这个答案的其余部分，对于"dictionary"，你还可以读取"set"；set被实现为只有键而没有值的字典

对键进行散列，并将散列值分配给动态表中的插槽（它可以根据需要增长或收缩）。映射过程可能导致冲突，这意味着必须根据已存在的键将密钥插入下一个插槽。

列出内容循环遍历插槽，因此键以它们当前在表中的顺序列出。

以键'foo'和'bar'为例，假设表的大小为8个插槽。在Python 2.7中，hash('foo')is -4177197833195190597，hash('bar')is 327024216814240868。模数8，这意味着这两个键分别插入插槽3和4中，然后：

>>> hash('foo')
-4177197833195190597
>>> hash('foo') % 8
3
>>> hash('bar')
327024216814240868
>>> hash('bar') % 8
4

这通知了他们的上市顺序：

>>> {'bar': None, 'foo': None}
{'foo': None, 'bar': None}

除3和4之外的所有插槽均为空，在表上循环时首先列出插槽3，然后列出插槽4，因此’foo’在之前列出’bar’。

bar和baz，但是散列值恰好相距8，因此映射到完全相同的插槽4：

>>> hash('bar')
327024216814240868
>>> hash('baz')
327024216814240876
>>> hash('bar') % 8
4
>>> hash('baz') % 8
4

现在，他们的顺序取决于首先插入哪个密钥。第二个密钥将必须移至下一个插槽：

>>> {'baz': None, 'bar': None}
{'bar': None, 'baz': None}
>>> {'bar': None, 'baz': None}
{'baz': None, 'bar': None}

此处的表顺序有所不同，因为一个或另一个键先插入插槽。

CPython使用的基础结构（最常用的Python实现）的技术名称是哈希表，该哈希表使用开放式寻址。如果你感到好奇，并且对C足够了解，请查看C实现的所有（详细记录）细节。你还可以观看Brandon Rhodes在Pycon 2010上所作的有关CPython如何dict工作的演示，或者获取Beautiful Code的副本，其中包括Andrew Kuchling撰写的有关实现的章节。

请注意，从Python 3.3开始，还使用了随机的哈希种子，从而使哈希冲突无法预测，以防止某些类型的拒绝服务（攻击者通过引起大量哈希冲突而使Python服务器无响应）。这意味着给定字典的顺序也取决于当前Python调用的随机哈希种子。

其他实现可以自由地为字典使用不同的结构，只要它们满足已记录的Python接口，但我相信到目前为止，所有实现都使用哈希表的变体。

CPython 3.6引入了一个新的 dict实现，该实现可以维护插入顺序，并且启动起来更快，内存效率更高。新的实现没有保留一个大的稀疏表，其中的每一行都引用了存储的哈希值以及键和值对象，而是添加了一个较小的哈希数组，该数组仅引用密集表中的索引（一个索引仅包含实际行数键值对），而密集表恰好按顺序列出了包含的项。有关更多详细信息，请参见Python-Dev的建议。请注意，在Python 3.6中，这被认为是实现细节，Python语言不指定其他实现必须保留顺序。这在Python 3.7中有所更改，其中的详细信息是提升为语言规范 ; 为了使任何实现与Python 3.7或更高版本正确兼容，必须复制此保留顺序的行为。

Python 2.7及更高版本还提供了一个OrderedDict类，该类的子类dict添加了额外的数据结构来记录键顺序。以某种速度和额外的内存为代价，此类会记住你按什么顺序插入键。然后列出键，值或项目将按此顺序进行。它使用存储在其他词典中的双向链接列表来使订单保持最新状态。请参阅Raymond Hettinger的帖子，概述该想法。请注意，该set类型仍然是无序的。

如果你需要订购的套装，则可以安装oset软件包；它适用于Python 2.5及更高版本。