无序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 ¹特定的和关于字典 - 但我认为它也适用于集合).

基本上,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,2并且3,无论输入列表中的顺序如何,您都将获得一致的顺序:

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)是唯一的.

¹ 注意此处描述的实现适用于CPython dict和set.我认为一般描述适用于所有现代版本的CPython,最高可达3.6.但是,从CPython3.6开始,还有一个额外的实现细节,实际上保留了迭代的插入顺序dict.看来set仍然没有这个属性.这篇博客文章描述了数据结构,由pypy人员(在CPython人员之前开始使用它)开始.最初的想法(至少对于python生态系统)存档在python-dev邮件列表中.

Answer 2

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

键的位置由它的内存地址定义。如果您知道 Python 会为某些对象重用内存：

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

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

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

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

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

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

这种方法可以节省 Python 解释器消耗的内存。