x=2 时，{2,3,10} 和 {x,3,10} 的顺序如何/为何不同？

Question

集合是无序的，或者更确切地说，它们的顺序是实现细节。我对那个细节很感兴趣。然后我看到了一个令我惊讶的案例：

print({2, 3, 10})
x = 2
print({x, 3, 10})

输出（在线尝试！）：

{3, 10, 2}
{10, 2, 3}

尽管相同的元素以相同的顺序编写，但它们的顺序不同。这是如何发生的？这是出于某种原因故意这样做的吗？例如，为了优化查找速度？

我的

sys.version

和

sys.implementation

:

3.13.0 (main, Nov  9 2024, 10:04:25) [GCC 14.2.1 20240910]
namespace(name='cpython', cache_tag='cpython-313', version=sys.version_info(major=3, minor=13, micro=0, releaselevel='final', serial=0), hexversion=51183856, _multiarch='x86_64-linux-gnu')

Answer 1

这是几个因素的函数：

1. 哈希桶冲突 - 对于最小的

   set

   大小，

   8

   （CPython 的实现细节）、

   2

   和

   10

   在它们的缩减哈希码上发生冲突（分别是

   2

   和

   10

   ；mod

    8

   ，他们是两者 2)。无论哪一个先插入，“获胜”并获得存储桶索引 2，另一个就会被探测操作移动。

2. 编译时优化：在现代 CPython 中，长度至少为三个元素的常量文字的

   set

   和

   list

   在编译时被构造为不可变容器（分别为

   frozenset

   和

   tuple

   ）。在运行时，它会构建一个空的

   set

   /

   list

   ，然后使用不可变容器对其进行

   update

   s/

   extend

   ，而不是为每个元素执行单独的加载和

   add

   s/

   append

   。这意味着当您使用

   s = {2, 3, 10}

   进行构建时，您实际上是在执行

   s = set()

   、

   s.update(frozenset({2, 3, 10}))

   ，而

   s = {x, 3, 10}

   则是通过在堆栈上加载

   x

   、

   3

   和

   10

   来构建，然后构建

   set

   作为单个操作。

这两者意味着您实际上以不同的方式构建它；

{x, 3, 10}

正在插入

2

，然后是

3

，然后是

10

，因此桶

2

和

3

被填满，并且

10

被重新定位（探测策略明确地将其放入桶

0

或

1

，在桶

2

之前）。当您执行

{2, 3, 10}

时，在编译时它会创建一个

frozenset({3, 10, 2})

，然后在运行时，它会创建空的

set

，然后通过迭代该

frozenset

来更新它，它已经对元素重新排序了，所以现在它们不再被添加到

2

中，

3

，

10

顺序，“首选”桶的竞赛由不同的元素获胜。