无序Python集的“顺序”

无序Python集的“顺序”

你应该观看此视频（尽管它是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邮件列表中。