无序 Python 集合的“order”（顺序）是什么？

Question

无序 Python 集合的“order”（顺序）是什么？

69

我知道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'])

我只是好奇这个为什么。有人可以帮忙吗？

- ivan

4

相同版本的Python上运行的相同数据将每次按照相同的顺序放入相同的哈希桶中，因此在这些特定情况下，您可以确信它们是相同的。 - Ry-

2

相关：为什么Python会以这样的方式排序我的字典？。集合的实现方式与字典非常相似。 - David Robinson

@KirkStrauser：不，但这只是常识。为什么哈希算法会涉及随机数生成器呢？但是，是的，好的代码不依赖于此顺序。 - Ry-

@minitech 信不信由你，这是 Perl 的一项安全功能（请参见 http://perldoc.perl.org/perlsec.html#Algorithmic-Complexity-Attacks 和 http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf 进行证明）。它在至少一个 Perl 发布版本中默认启用；我不知道它的当前状态如何。 - Kirk Strauser

@RyanO'Hara -- 这在较新版本的Python中不是真实的。一些类型启用了哈希随机化。由于__hash__函数的随机种子，使用相同字符串进行多次运行通常会以不同的顺序结束。 - mgilson

显示剩余3条评论

5个回答

6

这种行为的原因是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解释器消耗的内存。

- Eugene Soldatov

1

嗨，我刚试了下面的例子，得到了相同的内存地址： >>> a="Helloworld" >>> id(a) 140298549847792 >>> a="Helloworld" >>> id(a) 140298549847792 - Manjunath Raddi

@ManjunathRaddi 同样的问题，你找出原因了吗？ - Prasanjit Rath

这是不正确的；对象的id()并不重要。重要的是hash()。 - Aran-Fey

4

有一点需要注意，mgilson的优秀回答中提到了，但是在现有的回答中没有明确提到：

小整数哈希值等于它们本身：

>>> [hash(x) for x in (1, 2, 3, 88)]
[1, 2, 3, 88]

字符串哈希到不可预测的值。事实上，从3.3版本开始，默认情况下它们是基于在启动时随机化的种子构建的（链接1）。因此，每个新的Python解释器会话都会得到不同的结果，但是：

>>> [hash(x) for x in 'abcz']
[6014072853767888837,
 8680706751544317651,
 -7529624133683586553,
 -1982255696180680242]

因此，考虑最简单的哈希表实现方式：只是一个包含N个元素的数组，其中插入值意味着将其放在hash(value)%N（假设没有冲突）中。你可以大致猜测N会有多大——它将比其中的元素数量稍微大一些。当从6个元素的序列创建集合时，N可以很容易地是8。

当您使用N=8存储这5个数字时会发生什么？那么hash(1)%8、hash(2)%8等就是这些数字本身，但hash(88)%8则为0。因此，哈希表的数组最终会保存88,1,2,NULL,NULL,5,NULL,7。所以很容易想到迭代集合可能会得到88,1,2,5,7。

当然，Python并不保证每次都能得到这个顺序。对于正确值N的猜测方式的微小更改可能意味着88会出现在其他位置（或与其他值相撞）。实际上，在我的Mac上运行CPython 3.7时，我得到了1,2,5,7,88.0。

同时，当您从大小为11的序列构建哈希，然后将随机哈希插入其中时，会发生什么？即使假设最简单的实现，并且假设没有冲突，您仍然不知道将获得什么顺序。它将在Python解释器的单个运行中保持一致，但在下一次启动它时会有所不同。（除非您将PYTHONHASHSEED设置为0或其他int值。）这正是您看到的。

当然，值得看一下集合实际实现的方式，而不是猜测。但是，基于最简单的哈希表实现的假设所猜测的（除了冲突和哈希表扩展之外）正是发生的事情。

- abarnert

3

据我所知，Python的集合是使用哈希表实现的。项目出现的顺序取决于所使用的哈希函数。在同一次程序运行中，哈希函数可能不会改变，因此您将获得相同的排序结果。

但是，并不能保证它总是使用相同的函数，而且在不同的运行中 - 或者在同一个运行中如果您插入了大量元素并且哈希表需要调整大小时 - 排序会发生变化。

- MAK

2

集合基于哈希表。一个值的哈希应该是一致的，因此顺序也将保持一致 - 除非两个元素哈希到相同的代码，此时插入的顺序将改变输出顺序。

- Mark Ransom

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mgilson · Accepted Answer

你应该观看这个视频（尽管它是关于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)、hash(2)和hash(3)的最后三位是唯一的，所以这里提到的实现适用于CPython中的dict和set。我认为这个通用描述在CPython 3.6及所有现代版本中都是有效的。但是，从CPython 3.6开始，有一个额外的实现细节，实际上保留了dict迭代的插入顺序。看起来set仍然不具备这个属性。这种数据结构由pypy团队（在CPython之前就开始使用这种方法）在这篇博客文章中进行了描述。原始想法（至少对于Python生态系统）则可以在python-dev邮件列表中找到。