为什么字典和集合中的顺序是任意的？
我不太明白在Python中，遍历字典或集合是怎么以“任意”顺序进行的。
我的意思是，既然这是一个编程语言，那么语言中的一切都应该是完全确定的，对吧？Python一定有某种算法来决定字典或集合中哪个部分是第一个、第二个，依此类推。
我是不是漏掉了什么？
5 个回答
“任意的”并不等同于“不可确定的”。
他们的意思是，字典的遍历顺序没有什么有用的特性是“公开的”。实际上，字典遍历顺序可能有很多特性是由当前实现字典遍历的代码决定的，但作者并没有把这些特性承诺给你，作为你可以使用的东西。这让他们在不同的Python版本之间（甚至在不同的运行条件下，或者在运行时完全随机）更自由地改变这些特性，而不必担心你的程序会因此出错。
所以，如果你写的程序依赖于字典顺序的任何特性，那么你就是在“违反使用字典类型的约定”，而Python的开发者并不承诺这总是有效，即使在你测试的时候看起来是有效的。这基本上就相当于在C语言中依赖“未定义行为”。
这段内容主要是对Python 3.41 中的集合问题的回应，之前这个问题被关闭了，因为它被认为是重复的。
其他人说得对：不要依赖顺序。甚至不要假装有顺序。
不过，有一件事是可以依赖的：
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) % 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实现）使用的底层结构的技术名称是哈希表，它采用开放寻址法。如果你感兴趣，并且对C语言有一定了解，可以查看C语言实现的详细信息（文档写得很清楚）。你也可以观看Brandon Rhodes在Pycon 2010的演讲，了解CPython的dict是如何工作的，或者买一本《优雅的代码》，里面有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及以上版本。