Python中集合的顺序

Question

我原以为，当我们遍历一个集合时，遍历的顺序是根据与这个集合对应的哈希表中哈希值的大小来决定的。为了验证这个想法，我写了一段代码。

我看到有地方说，在Python中，当哈希表填满超过60%时，它的大小会翻倍。最开始它有八个位置。所以，如果我填满了六个位置，它就应该变成16个位置，因为要重新调整大小。那时候，存储在这些位置中的哈希值应该是 hash(x)%16。

>>> t = tuple(hash(i)%16 for i in (chr(i) for i in range(97, 103)))

这段代码创建了一个元组 t，里面是字符 'a' 到 'f' 的哈希值取模16的结果。我重复这个过程，直到没有冲突，最后得到了 t = (4, 3, 1, 7, 12, 9)。我本以为当我打印 set('abcdef') 时，它会显示 {'c','b','a','d','f','e'}，但实际输出却是 {'c','d','f','b','a','e'}。

不过，如果我改成这样做

>>> t = tuple(hash(i)%32 for i in (chr(i) for i in range(97, 103)))

我得到了 t = (20, 19, 1, 7, 28, 9)，这次正确预测了顺序 {'c','d','f','b','a','e'}。

每次我用六个元素和'%32'，都能正确预测顺序。

那么，这到底是怎么回事呢？哈希表的大小是32吗？为什么会这样？

Answer 1

你在看一些实现细节，然后把它们总结了一下。不过你漏掉了一个很重要的细节：对于小的数据集，哈希表的大小会乘以4。

需要注意的是，这些内容可能会发生变化。正如链接中的问题提到的，负载因子在2017年从2/3变成了3/5。合理的代码不应该依赖于这些细节。