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

问题描述：

我不明白在 Python 中如何以“任意”顺序循环遍历字典或集合。

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

我错过了什么？

解决方案 1：

注意：此答案是在 Python 3.6 中类型的实现发生更改之前编写的。此答案中的大多数实现细节仍然适用，但字典dict中键的列出顺序不再由哈希值决定。集合实现保持不变。

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

密钥经过哈希处理，哈希值被分配到动态表中的槽位（可以根据需要增大或缩小）。并且该映射过程可能会导致冲突，这意味着必须根据已经存在的内容将密钥插入下一个槽位。

列出内容会循环遍历各个槽位，因此键会按照它们当前在表中的顺序列出。

以键'foo'和'bar'为例，假设表大小为 8 个槽。在 Python 2.7 中，hash('foo')是-4177197833195190597，hash('bar')是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 上发表的关于 CPythondict工作原理的演讲，或者购买一本《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 概述该想法的帖子。OrderedDict对象还有其他优点，例如可重新排序。

如果您想要一个有序集，您可以安装该oset包；它适用于 Python 2.5 及更高版本。

解决方案 2：

这更像是对Python 3.41 A 集在被关闭为重复之前的回应。

其他人说得对：不要依赖命令。甚至不要假装有命令。

话虽如此，但有一件事你可以信赖：

list(myset) == list(myset)

也就是说，顺序是稳定的。

要理解为什么存在感知秩序，需要理解以下几点：

• Python 使用哈希集，

• CPython 的哈希集在内存中的存储方式以及

• 数字如何被散列

从顶部开始：

哈希集是一种存储随机数据的方法，查找时间非常快。

它有一个支持数组：

# A C array; items may be NULL,
# a pointer to an object, or a
# special dummy object
_ _ 4 _ _ 2 _ _ 6

我们将忽略特殊的虚拟对象，其存在只是为了使删除更容易处理，因为我们不会从这些集合中删除。

为了实现真正快速的查找，您需要使用一些魔法来计算对象的哈希值。唯一的规则是两个相等的对象具有相同的哈希值。（但如果两个对象具有相同的哈希值，则它们可能不相等。）

然后通过对数组长度取模来生成索引：

hash(4) % len(storage) = index 2

这使得访问元素变得非常快。

哈希只是故事的大部分内容，因为hash(n) % len(storage)和hash(m) % len(storage)可以得出相同的数字。在这种情况下，可以尝试几种不同的策略来解决冲突。CPython在进行伪随机探测之前使用 9 次“线性探测” ，因此它会在查找其他地方之前先查看槽的右侧最多 9 个位置。

CPython 的哈希集存储如下：

• 哈希集的满度不能超过60%（注意：此负载因子以前为 66%，在 Python 3.7 中已降低）。如果有 20 个元素，而后备数组的长度为 30 个元素，则后备存储将调整为更大。这是因为小型后备存储会更频繁地发生冲突，而冲突会使所有速度变慢。

• 当后备存储变得太满时，它将自动调整大小以增加未使用空间的比率（未使用空间的比率越高，处理哈希冲突时找到插槽的速度就越快）。对于较小的集合，存储大小将增加四倍，对于较大的集合（>50,000），存储大小将增加一倍（来源）。

因此，当您创建一个数组时，后备存储器的长度为 8。一旦它已满 4 并添加一个元素，它将包含 5 个元素。5 > ³⁄₅·8因此这会触发调整大小，并且后备存储器的大小将增加四倍至 32。

>>> import sys
>>> s = set()
>>> for i in range(10):
...     print(len(s), sys.getsizeof(s))
...     s.add(i)
... 
0 216
1 216
2 216
3 216
4 216
5 728
6 728
7 728
8 728
9 728

最后，hash(n)只返回n整数（除了因为该值保留用于其他用途而hash(-1)返回的）。-2`-1`

那么，让我们看一下第一个：

v_set = {88,11,1,33,21,3,7,55,37,8}

len(v_set)是 10，所以在添加完所有项目后，后备存储至少为 15(+1) 。2 的相关幂是 32。因此后备存储为：

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

我们有

hash(88) % 32 = 24
hash(11) % 32 = 11
hash(1)  % 32 = 1
hash(33) % 32 = 1
hash(21) % 32 = 21
hash(3)  % 32 = 3
hash(7)  % 32 = 7
hash(55) % 32 = 23
hash(37) % 32 = 5
hash(8)  % 32 = 8

因此这些插入为：

__  1 __  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
   33 ← Can't also be where 1 is;
        either 1 or 33 has to move

因此我们期望的顺序如下

{[1 or 33], 3, 37, 7, 8, 11, 21, 55, 88}

将不在开头的 1 或 33 替换为其他位置。这将使用线性探测，因此我们将获得：

       ↓
__  1 33  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

或者

       ↓
__ 33  1  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

您可能认为 33 会被替换，因为 1 已经存在，但由于在构建集合时会调整大小，因此实际情况并非如此。每次重建集合时，已添加的项目都会被重新排序。

现在你明白为什么了

{7,5,11,1,4,13,55,12,2,3,6,20,9,10}

可能是有序的。有 14 个元素，因此后备存储至少为 21+1，即 32：

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

1 到 13 的哈希值位于前 13 个槽位中。20 位于 20 个槽位中。

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ __ __ __ __ __ __ __ __ __

55 进入hash(55) % 3223 号槽：

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ 55 __ __ __ __ __ __ __ __

如果我们选择 50，我们预计

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ 50 __ 20 __ __ __ __ __ __ __ __ __ __ __

瞧瞧：

>>> {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 20, 50}
{1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 50, 20}

pop从外观上看，它的实现相当简单：它遍历底层数组并弹出第一个元素，跳过未使用的插槽和“虚拟”条目（已删除元素的墓碑标记）。

这就是全部实施细节。

解决方案 3：

“任意”与“不确定”不同。

他们说的是，字典迭代顺序中没有“在公共接口中”的有用属性。几乎可以肯定，迭代顺序的许多属性完全由当前实现字典迭代的代码决定，但作者并没有承诺您可以使用它们。这让他们可以更自由地在 Python 版本之间更改这些属性（甚至只是在不同的操作条件下，或者在运行时完全随机地更改），而不必担心您的程序会崩溃。

因此，如果您编写的程序依赖于字典顺序的任何属性，那么您就“违反了使用字典类型的契约”，并且 Python 开发人员不保证这将始终有效，即使您测试时它似乎暂时有效。这基本上相当于依赖 C 中的“未定义行为”。

解决方案 4：

这个问题的其他答案都很棒，写得很好。原帖者问的是“如何”，我将其理解为“他们如何逃脱惩罚”或“为什么”。

Python 文档说字典是无序的，因为 Python 字典实现了抽象数据类型 关联数组。正如他们所说

返回绑定的顺序可能是任意的

换句话说，计算机科学专业的学生不能假设关联数组是有序的。数学中的集合也是如此

集合元素的排列顺序无关紧要

和计算机科学

集合是一种抽象数据类型，可以存储某些值，没有任何特定的顺序

使用哈希表实现字典是一个有趣的实现细节，因为就顺序而言，它具有与关联数组相同的属性。

解决方案 5：

Python 使用哈希表来存储字典，因此使用哈希表的字典或其他可迭代对象没有顺序。

但是关于哈希对象中项目的索引，python 根据以下代码计算索引hashtable.c：

key_hash = ht->hash_func(key);
index = key_hash & (ht->num_buckets - 1);

因此，由于整数的哈希值是整数本身，索引基于数字（是一个常数），所以通过和数字本身之间的按位与ht->num_buckets - 1计算的索引（除了 -1 之外，它的哈希值为 -2），以及其他具有哈希值的对象的索引。(ht->num_buckets - 1)

考虑以下set使用哈希表的示例：

>>> set([0,1919,2000,3,45,33,333,5])
set([0, 33, 3, 5, 45, 333, 2000, 1919])

对于数字，33我们有：

33 & (ht->num_buckets - 1) = 1

事实上是：

'0b100001' & '0b111'= '0b1' # 1 the index of 33

注意，在这种情况下(ht->num_buckets - 1)是8-1=7或0b111。

对于1919：

'0b11101111111' & '0b111' = '0b111' # 7 the index of 1919

对于333：

'0b101001101' & '0b111' = '0b101' # 5 the index of 333

有关 Python 哈希函数的更多详细信息，建议阅读以下来自Python 源代码的引述：

前面的主要细节：大多数哈希方案都依赖于具有“良好”的哈希函数，即模拟随机性。Python 则不然：其最重要的哈希函数（用于字符串和整数）在常见情况下非常有规律：

>>> map(hash, (0, 1, 2, 3))
  [0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
  [-1658398457, -1658398460, -1658398459, -1658398462]

这不一定是坏事！相反，在大小为 2**i 的表中，将低阶 i 位作为初始表索引非常快，并且对于由连续的整数范围索引的字典，完全不会发生冲突。当键是“连续”字符串时，情况大致相同。因此，这在常见情况下会提供比随机更好的行为，这是非常理想的。

另一方面，当发生冲突时，填充哈希表连续片段的趋势使得良好的冲突解决策略至关重要。仅取哈希码的最后 i 位也容易受到攻击：例如，将列表视为[i << 16 for i in range(20000)]一组键。 由于 int 是它们自己的哈希码，并且这适合大小为 215 的字典，因此每个哈希码的最后 15 位都是 0：它们都映射到同一个表索引。**

但是，应对特殊情况不应该减慢常见情况的速度，所以我们无论如何都只取最后 i 位。剩下的就交给碰撞解决。如果我们通常在第一次尝试时就找到我们正在寻找的密钥（事实证明，我们通常能做到——表负载因子保持在 2/3 以下，因此胜算对我们有利），那么最好让初始索引计算变得非常便宜。

• 类别的哈希函数int：

class int:
    def __hash__(self):
        value = self
        if value == -1:
            value = -2
        return value