Python 如何确定集合中元素的顺序？-IT科技

摘要：问题描述：我知道sets在 Python 中它们是无序的，但我对它们显示的“顺序”感到好奇，因为它似乎是一致的。它们似乎每次都以同样的方式乱序：>>> set_1 = set([5, 2, 7, 2, 1, 88]) >>> set_2 = set([5, 2, 7, 2,...

问题描述：

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

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

解决方案 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])

请注意，这些集合中保留顺序的事实是“巧合”，并且与冲突解决有关（我对此一无所知）。关键是hash(8)，hash(16)和的最后 3 位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)是唯一的。

1注意此处描述的实现适用于 CPythondict和set。我认为一般描述适用于所有现代版本的 CPython 3.6 及以下版本。但是，从 CPython3.6 开始，有一个额外的实现细节，实际上保留了迭代的插入顺序dict。似乎set仍然没有这个属性。pypy 人员（他们在 CPython 人员之前就开始使用它）在这篇博客文章中描述了数据结构。原始想法（至少对于 python 生态系统而言）存档在 python-dev 邮件列表中。

解决方案 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 解释器消耗的内存。

解决方案 3：

mgilson 的精彩答案中暗示了一个关键点，但在任何现有答案中都没有明确提及：

小整数哈希值为自身：

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

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

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

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

当您将这 5 个数字存储为 N=8 时会发生什么？好吧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 值。）这正是您所看到的。

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