集合是否像 python3.6 中的 dicts 一样排序

2022-01-17 00:00:00 python python-3.6 set python-internals cpython

问题描述

由于 Python 3.6 中 dict 实现的变化，现在默认排序.sets 现在也保留顺序吗?

Due to changes in dict implementation in Python 3.6 it is now ordered by default. Do sets preserve order as well now?

我找不到任何有关它的信息，但由于这两种数据结构在它们的底层工作方式上非常相似，我认为可能是这种情况.

I could not find any information about it but as both of those data structures are very similar in the way they work under the hood I thought it might be the case.

我知道 dict 不能在所有情况下都被订购，但大多数情况下都是如此.如 Python 文档中所述:

I know there is no promise for dicts to be ordered in all cases but they are most of the time. As stated in Python docs:

这个新实现的顺序保留方面被认为是一个实现细节，不应依赖

The order-preserving aspect of this new implementation is considered an implementation detail and should not be relied upon

解决方案

不，set仍然是无序的.

您可以通过显示应该具有明确定义的哈希顺序"1 的 set 来验证这一点，以确保我们不会意外得到 set 看起来有序但实际上不是:

You can verify this just by displaying a set that should have a "well-defined hash order"1 to make sure we don't accidentally get a set that looks ordered but actually isn't:

>>> a_set = {3,2,1}
>>> a_set
{1, 2, 3}
>>> list(a_set)
[1, 2, 3]

如果已订购，您会期望 {3, 2, 1} 和 [3, 2, 1] 作为示例的结果.

If it were ordered you would expect {3, 2, 1} and [3, 2, 1] as result of the examples.

虽然 dict 实际上是有序的(相同的例子只是稍作修改):

While dicts are actually ordered (same example just a bit modified):

>>> a_dict = {3: 3, 2: 2, 1:1}
>>> a_dict
{3: 3, 2: 2, 1: 1}
>>> list(a_dict)
[3, 2, 1]

<小时>

1 定义明确的哈希顺序":

1 "well-defined hash order":

对于满足 0 <= integer 的整数sys.hash_info.modulus hash 只是数字本身.这意味着如果集合是根据散列基于"排序的(而不是基于插入时间"排序)并且散列值不冲突(这就是我使用小数字和仅相差一个的数字的原因)顺序应该是确定性的，因为它们占据了集合中彼此相邻的插槽:

For integers that satisfy 0 <= integer < sys.hash_info.modulus the hash is just the number itself. That means if the set is ordered "based" on the hash (and not ordered based on the insertion "time") and the hash values don't collide (that's why I used small numbers and numbers that only differ by one) the order should be deterministic because they occupy slots inside the set that are next to each other:

  • 从小到大
  • 或从特定值到最高值，然后从最小值到特定值.如果集合中的下一个(在相邻的意义上)空闲槽位是第一个空闲槽位，则会发生这种情况.

以后者为例:

>>> a_set = {6,7,8,9}
>>> a_set
{8, 9, 6, 7}

相关文章