无序Python集的“顺序”

Question

我知道Python中的集合是无序的，但是我很好奇它们显示的“顺序”，因为它看起来是一致的。每次它们似乎都以相同的方式乱序：

>>> set_1 = set([5, 2, 7, 2, 1, 88])
>>> set_2 = set([5, 2, 7, 2, 1, 88])
>>> set_1
set([88, 1, 2, 5, 7])
>>> set_2
set([88, 1, 2, 5, 7])

…还有另一个例子：

>>> set_3 = set('abracadabra')
>>> set_4 = set('abracadabra')
>>> set_3
set(['a', 'r', 'b', 'c', 'd'])
>>>> set_4
set(['a', 'r', 'b', 'c', 'd'])

我很好奇为什么会这样。有什么帮助吗？

Answer 1

你应该观看此视频（尽管它是CPython 1特定的并且是关于字典的-但我认为它也适用于集合）。

基本上，python对元素进行哈希处理并获取最后N位（其中N由集合的大小确定），然后将这些位用作数组索引以将对象放置在内存中。然后按照它们在内存中存在的顺序产生对象。当然，当你需要解决哈希之间的冲突时，图片会稍微复杂一些，但这就是要点。

还要注意，它们的打印顺序取决于你放置它们的顺序（由于碰撞）。因此，如果你对传递给的列表进行重新排序set_2，那么在发生键冲突时，你可能会得到其他排序。

例如：

list1 = [8,16,24]
set(list1)        #set([8, 16, 24])
list2 = [24,16,8]
set(list2)        #set([24, 16, 8])

请注意，顺序保留在这些集合中的事实是“巧合”，并且与冲突解决有关（我一无所知）。问题的关键是，最后3位hash(8)，hash(16)并且hash(24)是相同的。因为它们是相同的，所以冲突解决方案将接管并将元素放置在“备份”存储位置中，而不是首先（最佳）选择中，因此，是否8占据某个位置或16由哪个位置首先到达聚会并获得“最佳”决定座位”。

如果用和重复该示例1，则无论输入列表中的顺序如何，你都将获得一致的顺序：23

list1 = [1,2,3]
set(list1)      # set([1, 2, 3])
list2 = [3,2,1]
set(list2)      # set([1, 2, 3])

因为最后3位hash(1)，hash(2)并且hash(3)是唯一的。

1 注意此处描述的实现适用于CPython dict和set。我认为一般说明对所有最新版本的CPython到3.6均有效。但是，从CPython3.6开始，还有一个附加的实现细节，实际上保留了的迭代插入顺序dict。似乎set仍然没有此属性。pypy的人（在CPython的人之前开始使用它）在此博客文章中描述了数据结构。最初的想法（至少对于python生态系统而言）存储在python-dev邮件列表中。