python 中的集合每次都从 0-9 排序？！不是无序的

Question

一开始我以为这是一个巧合，所以我写了一个测试来尝试一下，结果确实如此，我运行了 100 万次，每次返回的集合都是有序和排序的。仅当您使用 0-9 之间的整数时才会发生这种情况，一旦插入大于 9 的整数，则之后插入的任何整数将不会被排序。为什么是这样？对于浮点数来说，它也可以排序，但并不总是正确的，很奇怪，我认为它们完全无序。任何关于为什么每次都对 0-9 进行排序的建议将不胜感激，我一开始也不相信它，所以这是我使用的代码，您可以轻松地自己运行它并看到它是真的。

import random

def check_set():
    constructing = True
    s = set()
    while constructing:
        x = random.randint(0, 9)
        if x not in s: s.add(x)
        if len(s) == 10: constructing = False
    return s
def main():
    for x in range(10000):
        l = list(check_set())
        if l != [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
            print('wow')
if __name__ == '__main__':
    main()

Answer 1

这些整数散列到自己：

>>> [*map(hash, range(10))]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

当您将数字 0 到 9 添加到一个集合中时，该集合会为至少 10 个数字（我认为实际上是 32 个）腾出空间。所以它的内部数组至少有索引 0 到 9。并且因为这些数字散列到自己，所以它们存储在集合的内部数组中自己的索引处（值i存储在 index hash(i)=处i）。因此，当您迭代它时，您就会对它们进行排序。

用较小的例子进一步说明：

集合从内部大小 8 开始，并且值i想要转到索引hash(i) % 8。因此，如果添加0和8，两者都想转到索引0。第一个实际上到达了索引0，另一个必须到达其他（更大的）索引。因此：

>>> {0, 8}, {8, 0}
({0, 8}, {8, 0})

如果您改为添加1and 8，则1想要转到索引1并8想要转到索引0，因此8无论插入顺序如何，总是先出现：

>>> {1, 8}, {8, 1}
({8, 1}, {8, 1})

0 到 9 的示例：

>>> s = set()
>>> for i in 8, 9, 0, 1, 2, 3, 4, 5, 6, 7:
        s.add(i)
        print(s)

{8}    # the only element (stored at index 0)
{8, 9}    # 9 gets stored at index 1, so after 8
{8, 9, 0}    # indices 0 and 1 are already taken, so 0 goes to some higher index
{8, 9, 0, 1}    # similar
{0, 1, 2, 8, 9}    # the set internally resized and re-added all values, each
                   # value ends up at its own index (e.g., 8 goes to index 8)
{0, 1, 2, 3, 8, 9}    # 3 goes to index 3
{0, 1, 2, 3, 4, 8, 9}    # same for the rest, all go to their own index...
{0, 1, 2, 3, 4, 5, 8, 9}
{0, 1, 2, 3, 4, 5, 6, 8, 9}
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}