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

注意: 这个答案是在 Python 3.6中改变 dict类型的实现之前编写的。这个答案中的大多数实现细节仍然适用，但是 字典中键的列表顺序不再由散列值决定。集合实现保持不变。

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

键被散列，散列值被分配给动态表中的槽(它可以根据需要增长或缩小)。这个映射过程可能会导致冲突，这意味着一个键将不得不根据已经存在的内容在 下一个槽中开槽。

列出插槽上的内容循环，因此按照键 目前驻留在表中的顺序列出键。

以键 '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 实现以获得所有(有良好文档记录的)细节。您还可以观看关于 CPython dict如何工作的 Pycon 2010演讲者: Brandon Rhodes，或者选择一份 美丽的密码的副本，其中包括 Andrew Kuchling 编写的关于实现的一章。

请注意，在 Python 3.3中，也使用了随机散列种子，使散列冲突变得不可预测，以防止某些类型的分布式拒绝服务攻击(攻击者通过引起大量散列冲突使 Python 服务器失去响应)。这意味着给定字典或集的顺序依赖于当前 Python 调用的随机散列种子 还有。

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

CPython 3.6引入了一个 新的 dict实现，它可以维护插入顺序，引导速度更快，内存效率更高。新的实现没有保留一个大型的稀疏表，其中每一行都引用存储的哈希值、键和值对象，而是添加了一个较小的哈希 数组，它只引用单独的“密集”表中的索引(一个只包含实际键-值对的行数) ，而且正是密集表按顺序列出了所包含的项。看看 有关详情，请向 Python-Dev 查询。请注意，在 Python 3.6中，这被认为是 实施细节，Python-the-language 没有指定其他实现必须保持有序。这在 Python 3.7中发生了变化，其中的细节是 升格为 a < em > 语言规格 ; 对于任何与 Python 3.7或更新版本正确兼容的实现，它 必须的都会复制这种保持顺序的行为。明确地说: 这个改变不适用于集合，因为集合已经有了一个“小”散列结构。

Python 2.7和更新的版本还提供了 OrderedDict级，dict的一个子类，它添加了一个额外的数据结构来记录键顺序。以牺牲一定的速度和额外的内存为代价，这个类记住您插入键的顺序; 然后列出键、值或项目将按照这个顺序执行操作。它使用存储在附加字典中的双向链接列表来有效地更新订单。看看 作者: Raymond Hettinger。OrderedDict对象还有其他优点，例如 可以重新订购。

如果您想要一个有序的集合，您可以安装 oset包裹; 它可以在 Python 2.5及以上版本上工作。

“任意”和“不确定”不是一回事。

他们的意思是“在公共接口中”没有字典迭代顺序的有用属性。几乎可以肯定的是，迭代顺序的许多属性完全由当前实现字典迭代的代码决定，但是作者并没有向您承诺这些属性是可以使用的。这给了他们更多的自由来在 Python 版本之间更改这些属性(或者只是在不同的操作条件下，或者在运行时完全随机) ，而不用担心程序会中断。

因此，如果你编写的程序依赖于字典顺序的 任何财产，那么你就打破了使用字典类型的“契约”，Python 开发人员并没有承诺这将始终有效，即使在你测试它的时候它看起来是有效的。这基本上等同于依赖 C 语言中的“未定义行为”。

这更多的是对 Python 3.41 A 组的响应，在它作为一个复制品关闭之前。

其他人是对的: 不要依赖顺序，甚至不要假装有顺序。

也就是说，你可以依赖 一:

list(myset) == list(myset)

也就是说，顺序是 稳定。

理解为什么会有 感知订单需要理解以下几点:

• 巨蟒使用 散列集,

• 如何将 CPython 的哈希集存储在内存中

• 数字是如何被散列的

从头开始:

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

它有一个后台数组:

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

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

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

然后通过取数组长度的模数来进行索引:

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)，因为值为 -1是为其他用途保留的，所以返回 -2)。

那么，让我们看看第一个:

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:

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

前13个插槽里有1到13个杂凑20个插槽里有20个。

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

55进入 hash(55) % 32插槽，即23:

__  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就是 实施: 它遍历底层数组并弹出第一个元素，跳过未使用的插槽和“虚拟”条目(来自已删除元素的墓碑标记)。

这些都是实现细节。

这个问题的其他答案都写得很好。OP 问“如何”，我解释为“他们如何逃脱”或“为什么”。

Python 文档说，字典没有排序，因为 Python 字典实现了 抽象数据类型 关联数组

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

换句话说，一个计算机科学专业的学生不能假设关联数组是被订购的。对于 数学中的集合也是如此

集合中元素列出的顺序是不相关的

和 计算机科学

集合是一种抽象的数据类型，它可以存储特定的值，而不需要任何特定的顺序

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

Python 使用 < strong > hash table 存储字典，因此使用哈希表的字典或其他可迭代对象中没有顺序。

但是对于 hash 对象中的索引，python 基于以下代码 在 hashtable.c范围内计算索引:

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

因此，由于整数的哈希值是整数本身 ^*，索引是基于数字的(ht->num_buckets - 1是一个常数) ，所以由 比特位-和计算的 (ht->num_buckets - 1)和数字本身 ^*之间的索引(预计 -1的哈希值是 -2) ，以及其他对象的哈希值。

考虑使用 hash-table 的 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 hash 函数的更多细节，最好阅读以下来自 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 是它们自己的哈希代码，而且这适合于大小为2 * * 15的结果，所以每个哈希代码的最后15位都是0: 它们 所有映射到同一个表索引。

但是处理不寻常的案子不应该减缓通常的案子，所以我们只是 最后一个 i 位无论如何。它的冲突解决做休息。如果 我们 通常找到关键，我们正在寻找的第一次尝试(和，它转动 通常情况下，表的负载系数保持在2/3以下，所以概率 是我们的优势) ，那么保留最初的索引是最有意义的 计算非常便宜。

_{* 类 int的哈希函数:}

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