无序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

这种行为的原因是Python使用哈希表来实现字典：https://en.wikipedia.org/wiki/Hash_table#Open_addressing

钥匙的位置由它的存储器地址决定。如果您知道Python对某些对象重用内存：

>>> a = 'Hello world'
>>> id(a)
140058096568768
>>> a = 'Hello world'
>>> id(a)
140058096568480

您可以看到对象每次初始化时都有不同的地址。

但对于小整数，它不会改变：

>>> a = 1
>>> id(a)
40060856
>>> a = 1
>>> id(a)
40060856

即使我们用不同的名称创建第二个对象，它也将是相同的：

>>> b = 1
>>> id(b)
40060856

这种方法允许保存Python解释器使用的内存。

Answer 2

您应该注意这个video（尽管它是CPython¹特定的，而且是关于字典的——但我假设它也适用于集合）。

基本上，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])

注意这些集合中保留顺序的事实是“巧合”，并且与碰撞分辨率有关（我对此一无所知）。关键是hash(8)、hash(16)和hash(24)的最后3位是相同的。因为它们是相同的，冲突解决将接管并将元素放在“备份”内存位置，而不是第一个（最佳）选择，因此8是占用一个位置还是16取决于谁先到达聚会并占据了“最佳位置”。

如果我们用1、2和3重复此示例，则无论它们在输入列表中的顺序如何，都将得到一致的顺序：

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

由于hash(1)的最后3位，hash(2)和hash(3)是唯一的。

---

¹注意这里描述的实现适用于CPythondict和set。我认为一般的描述对于3.6之前的所有现代版本的CPython都是有效的。但是，从CPython3.6开始，还有一个额外的实现细节，它实际上保留了dict迭代的插入顺序。似乎set仍然没有此属性。数据结构由pypy人员（在CPython人员之前开始使用它）用this blog post来描述。最初的想法（至少对于python生态系统而言）is archived on the python-dev mailing list。

Answer 3

AFAIK Python集是使用hash table实现的。项目出现的顺序取决于使用的哈希函数。在程序的同一次运行中，哈希函数可能不会更改，因此您得到的顺序相同。

但是不能保证它总是使用同一个函数，并且顺序会在不同的运行中发生变化——或者在同一个运行中，如果插入了很多元素并且哈希表必须调整大小。