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

Question

我不明白循环字典或在 python 中设置是如何按“任意”顺序完成的。

我的意思是，它是一种编程语言，所以语言中的所有内容都必须 100% 确定，对吗？ Python 必须有某种算法来决定选择字典或集合的哪一部分，第一、第二等等。

我错过了什么？

Answer 1

Note: This answer was written before the implementation of the dict type changed, in Python 3.6. Most of the implementation details in this answer still apply, but the listing order of keys in dictionaries is no longer determined by hash values. The set implementation remains unchanged.

顺序不是任意的，而是取决于字典或集合的插入和删除历史，以及具体的 Python 实现。对于本答案的其余部分，对于“字典”，您还可以阅读“设置”；集合被实现为只有键没有值的字典。

键被散列，散列值被分配给动态表中的槽(它可以根据需要增长或缩小)。并且该映射过程可能导致冲突，这意味着必须根据已经存在的键将 key 插入下一个槽中。

列出内容在槽上循环，因此键按照它们当前在表中的顺序列出。

拿 key 'foo'和 'bar'例如，假设表大小为 8 个插槽。在 Python 2.7 中，hash('foo')是 -4177197833195190597 , hash('bar')是 327024216814240868 . Modulo 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 实现)使用的底层结构的技术名称是 hash table ，一种使用开放寻址的。如果你很好奇，并且足够了解 C，请查看 C implementation所有(有据可查的)细节。你也可以看这个Pycon 2010 presentation by Brandon Rhodes关于 CPython dict作品，或拿起一份 Beautiful Code ，其中包括由 Andrew Kuchling 编写的关于实现的一章。

请注意，从 Python 3.3 开始，还使用了随机散列种子，使散列冲突不可预测，以防止某些类型的拒绝服务(攻击者通过导致大量散列冲突使 Python 服务器无响应)。这意味着给定字典或集合的顺序也取决于当前 Python 调用的随机哈希种子。

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

CPython 3.6 引入了一个新的 dict保持插入顺序的实现，并且启动速度更快，内存效率更高。新实现不是保留一个大的稀疏表，其中每一行都引用存储的散列值以及键和值对象，而是添加了一个较小的散列数组，该数组仅引用单独的“密集”表中的索引(一个只包含尽可能多的行)因为有实际的键值对)，并且恰好是按顺序列出包含的项目的密集表。见 proposal to Python-Dev for more details .请注意，在 Python 3.6 中，这被视为实现细节，Python-the-language 没有指定其他实现必须保留顺序。这在 Python 3.7 中发生了变化，这里的细节是 elevated to be a language specification ;对于任何与 Python 3.7 或更高版本正确兼容的实现 必须复制这种保留顺序的行为。明确地说:此更改不适用于集合，因为集合已经具有“小”哈希结构。

Python 2.7 及更新版本还提供了 OrderedDict class ，dict 的子类它添加了一个额外的数据结构来记录 key 顺序。以一定的速度和额外的内存为代价，这个类会记住你插入 key 的顺序；列出键、值或项目将按该顺序列出。它使用存储在附加字典中的双向链表来有效地保持订单最新。见 post by Raymond Hettinger outlining the idea . OrderedDict对象还有其他优点，例如可重新排序。

如果您想要订购的套装，您可以安装 oset package ;它适用于 Python 2.5 及更高版本。