为什么 Python 集合不保留插入顺序？

我最近惊讶地发现，虽然在 Python 3.7+ 中字典可以保证保留插入顺序，但集合却不能：

>>> d = {'a': 1, 'b': 2, 'c': 3}
>>> d
{'a': 1, 'b': 2, 'c': 3}
>>> d['d'] = 4
>>> d
{'a': 1, 'b': 2, 'c': 3, 'd': 4}

>>> s = {'a', 'b', 'c'}
>>> s
{'b', 'a', 'c'}
>>> s.add('d')
>>> s
{'d', 'b', 'a', 'c'}

造成这种差异的原因是什么？导致 Python 团队更改 dict 实现的相同效率改进是否也不适用于集合？

我不是在寻找指向有序集实现的指针或使用字典作为集合的替代品的方法。我只是想知道为什么 Python 团队没有在对字典这样做的同时让内置集合保持顺序。

集合和字典针对不同的用例进行了优化。集合的主要用途是快速成员资格测试，这是与顺序无关的。对于字典来说，查找的成本是最关键的操作，并且密钥更有可能存在。对于集合，事先无法知道元素是否存在，因此集合实现需要针对已找到和未找到的情况进行优化。此外，对常见集合操作（​​例如并集和交集）的一些优化使得很难在不降低性能的情况下保留集合排序。

虽然这两种数据结构都是基于哈希的，但一个常见的误解是集合只是作为具有空值的字典来实现。甚至beforeCPython 3.6 中的紧凑 dict 实现中，set 和 dict 实现已经存在显着差异，几乎没有代码重用。例如，字典使用随机探测，但集合使用线性探测和开放寻址的组合来改进缓存局部性。初始线性探头（默认9 steps在 CPython 中）将检查一系列相邻的密钥/哈希对，通过降低哈希冲突处理的成本来提高性能 - 连续的内存访问比分散的探针更便宜。

• dictobject.c - main, v3.5.9
• setobject.c - main, v3.5.9
• 问题18771- 更改集以减少 Python 3.4 中集合对象的哈希冲突成本。

这将是possible理论上将 CPython 的 set 实现更改为类似于紧凑字典，但实际上存在缺陷，并且著名的核心开发人员反对进行这样的更改。

集合保持无序。 （为什么？使用模式不同。而且实现也不同。）

– 吉多·范罗苏姆

集使用不同的算法，该算法无法修改以保留插入顺序。 如果需要订单，按组操作就会失去灵活性和优化性。集合数学是根据无序集合定义的。简而言之，集合排序不会在不久的将来出现。

– 雷蒙德·海廷格

关于是否压缩 3.7 集以及为什么决定反对的详细讨论可以在 python-dev 邮件列表中找到。

总结起来，要点是：不同的使用模式（插入排序字典如 **kwargs 是useful，对于集合来说更是如此），压缩集合的空间节省不太重要（因为只有键+哈希数组来致密，而不是键+哈希+值数组），并且集合当前使用的前述线性探测优化是不兼容的具有紧凑的实施方式。

我将在下面转载雷蒙德的帖子，其中涵盖了最重要的要点。

2016 年 9 月 14 日下午 3:50，埃里克·斯诺 (Eric Snow) 写道：

然后，我将对集合做同样的事情。

除非我误会了，否则雷蒙德反对制作类似的作品 更改为设置。

这是正确的。以下是人们对这个主题的一些想法 开始狂奔。

• 对于紧凑字典，节省的空间是净胜，因为索引消耗了额外的空间，并且过度分配了 键/值/哈希数组超出了改进后的偏移量 键/值/哈希数组的密度。然而对于套装来说，网很多 不太有利，因为我们仍然需要指数和过度分配 但只能通过仅增加三个中的两个来抵消空间成本 数组。换句话说，当你有 浪费了键、值和哈希的空间。如果你失去其中之一 第三，它不再具有吸引力。

• 集合的使用模式与字典不同。前者有更多的命中或未命中查找。后者丢失钥匙的情况往往较少 查找。另外，对设置到设置操作的一些优化 很难在不影响的情况下保留集合顺序 表现。

• 我寻求替代途径来提高设定性能。而不是紧凑（这并没有赢得太多空间，并且产生了成本） 额外的间接），我添加了线性探测以降低成本 冲突并提高缓存性能。这个改进是 与我提倡的压缩方法不兼容 字典。

• 目前，字典上的排序副作用是无法保证的，因此开始坚持集合也是有序的还为时过早。 该文档已经链接到创建 OrderedSet 的方法（https://code.activestate.com/recipes/576694/）但似乎 吸收率几乎为零。另外，现在埃里克·斯诺（Eric Snow）给了我们一个 快速 OrderedDict，比以往任何时候都更容易构建 OrderedSet MutableSet 和 OrderedDict，但我再次没有观察到任何真正的 感兴趣，因为典型的逐组数据分析并不真正需要 或关心订购。同样，快速会员的主要用途 测试与顺序无关。

• 也就是说，我确实认为有空间向 PyPI 添加替代集实现。特别是，有一些有趣的 可排序数据的特殊情况，其中可以进行设置到设置的操作 通过比较整个范围的键来加速（参见https://code.activestate.com/recipes/230113-implementation-of-sets-using-sorted-lists为起点）。 IIRC，PyPI 已经有类似集合的绽放代码 过滤器和布谷鸟散列。

• 我知道 Python 核心接受主要代码块是令人兴奋的，但这不应该打开闸门 除非我们确定，否则对其他数据类型进行更多重大重写 这是有保证的。

——雷蒙德·海廷格

From [Python-Dev] Python 3.6 dict 变得紧凑并获得私有版本；并且关键字变得有序，2016 年 9 月。