这更多是对Python 3.41 A set的响应，之前它被关闭为重复问题。

其他人都是对的：不要依靠顺序。甚至不要假装有一个。

话虽如此，有一件事是你可以依赖的：

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，则支持存储会重新调整大小变大。这是因为小的支持存储碰撞更容易发生，碰撞会拖慢所有的操作。

• 当支持存储占用的空间过多时，它将自动调整大小以增加未使用空间的比率（更高的未使用空间比率意味着处理哈希碰撞时更容易找到一个段）。对于小型集合，存储空间会增加4倍，对于大型集合（> 50,000），存储空间将增加2倍（来源）。

因此，当您创建一个长度为8的数组时，支持存储的长度为8。一旦它占用的空间超过了四分之三而您添加了一个元素，它将包含五个元素。 5>³⁄₅·8，因此这将触发调整大小，支持存储将增加4倍，大小为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) % 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 看起来非常简单，实现方式是：它遍历底层数组并弹出第一个元素，跳过未使用的槽和“虚拟”条目（已删除元素的坟墓标记）。

这都是具体实现细节。

注意：这篇答案是在 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实现）所使用的底层结构的技术名称是哈希表（hash table），它使用的是开放地址法。如果你感到好奇，且懂得足够好的C语言，可以看一下C实现，了解所有（有很好的文档）细节。您还可以观看 Brandon Rhodes 在 Pycon 2010 上的演讲，了解 CPython dict 的工作原理，或者阅读《精美代码》（Beautiful Code）的一章，其中包括由 Andrew Kuchling 所撰写的实现章节。

请注意，在Python 3.3以及之后版本，随机哈希种子也被使用，使得哈希碰撞不可预测，以防止某些类型的拒绝服务攻击（攻击者通过导致大量哈希碰撞而使Python服务器无响应）。这意味着给定字典或集合的顺序也取决于当前 Python 调用的随机哈希种子。

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

CPython 3.6引入了新的dict实现，保持插入顺序，并且速度更快，更节约内存。新的实现不再保留一个大而稀疏的表，在每行引用存储的哈希值，键和值对象的同时，添加一个较小的哈希数组，仅引用一个独立的“密集”表（仅包含与实际 键值对一样多的行），而恰好是密集表按顺序列出所包含的项目。更多详细信息请参见Python-Dev提案（https://mail.python.org/pipermail/python-dev/2012-December/123028.html）。请注意，在Python 3.6中，这被认为是一个实现细节，Python语言没有规定其他实现必须保留顺序。这在Python 3.7中发生了改变，该细节被提升为语言规范；为了与Python 3.7或更高版本兼容，任何实现都必须复制这种保留顺序的行为。而且要明确的是：此更改不适用于集合，因为集合已经有一个“小”哈希结构。

Python 2.7及更高版本还提供了一个OrderedDict类，它是dict的子类，添加了一个额外的数据结构来记录键的顺序。以一些速度和额外的内存为代价，此类记住插入键的顺序；列出键、值或项目时将按该顺序进行。它使用一个存储在额外字典中的双向链表来高效地保持顺序更新。请参见Raymond Hettinger的帖子，概述了这个想法。OrderedDict对象具有其他优点，例如可重新排序。如果你想要一个排好序的集合，你可以安装oset包；它适用于Python 2.5及以上版本。