为什么字典排序是非确定性的？

Question

为什么字典排序是非确定性的？

pythondictionarypython-3.xpython-3.3non-deterministic

48

我最近从Python 2.7切换到Python 3.3，似乎在Python 2中字典键的排序是任意的但一致的，而在Python 3中，例如使用vars()获取的字典键的顺序似乎是不确定的。

如果我运行：

class Test(object): pass
parameters = vars(Test)
print(list(parameters.keys()))

如果在Python 2.7和Python 3.3中都需要，那么：

Python 2.7 consistently gives me

['__dict__', '__module__', '__weakref__', '__doc__']

With Python 3.3, I can get any random order – for example:

['__weakref__', '__module__', '__qualname__', '__doc__', '__dict__']
['__doc__', '__dict__', '__qualname__', '__module__', '__weakref__']
['__dict__', '__module__', '__qualname__', '__weakref__', '__doc__']
['__weakref__', '__doc__', '__qualname__', '__dict__', '__module__']

这种不确定性从何而来？为什么像这样的东西

list({str(i): i for i in range(10)}.keys())

始终保持一致，每次运行都提供相同的结果

['3', '2', '1', '0', '7', '6', '5', '4', '9', '8']

… ?

- Anaphory

2个回答

14

请注意，Python 3.7仍然具有非确定性的集合。字典保留插入顺序，但集合不保留。集合可能表现出相同的随机行为。

python3 -c "print({str(i) for i in range(9)})"

仍然会在每次运行时得到不同的结果。

- Pete Cacioppi

来这里发表答案，因为我通过艰难的方式找到了答案...然后我看到了这个...+1 - user541686

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Zero Piraeus · Accepted Answer

更新：在Python 3.6中，dict有一个新实现，可以保留插入顺序。从Python 3.7开始，这种保持顺序的行为已经得到了保证：

字典对象保持插入顺序的特性已被宣布成为Python语言规范的正式部分。

这是一个2012年安全补丁的结果，它在Python 3.3中默认启用（请向下滚动至“Security improvements”）。

以下是公告内容：

哈希随机化导致字典和集合的迭代顺序不可预测，并在Python运行时有所不同。Python从未保证字典或集合键的迭代顺序，建议应用程序永远不要依赖此顺序。历史上，字典迭代顺序在发行版之间几乎没有改变，并且始终在连续执行Python的情况下保持一致。因此，某些现有的应用可能依赖于字典或集合的顺序。由于这个原因和许多不接受不受信任的输入的Python应用程序没有受到此攻击的影响，在此提到的所有稳定的Python版本中，默认情况下禁用了哈希随机化。

如上所述，在Python 3.3中，最后的大写部分不再是真实的。

另请参阅：object.__hash__() 文档（“注意”侧边栏）。

如果绝对必要，在受此行为影响的 Python 版本中，您可以通过将PYTHONHASHSEED环境变量设置为0来禁用哈希随机化。

你的反例：

list({str(i): i for i in range(10)}.keys())

尽管由于哈希冲突的处理方式，不同排序数量有限due to，但在Python 3.3中，实际上并不总是产生相同的结果：

$ for x in {0..999}
> do
>   python3.3 -c "print(list({str(i): i for i in range(10)}.keys()))"
> done | sort | uniq -c
     61 ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
     73 ['1', '0', '3', '2', '5', '4', '7', '6', '9', '8']
     62 ['2', '3', '0', '1', '6', '7', '4', '5', '8', '9']
     59 ['3', '2', '1', '0', '7', '6', '5', '4', '9', '8']
     58 ['4', '5', '6', '7', '0', '1', '2', '3', '8', '9']
     55 ['5', '4', '7', '6', '1', '0', '3', '2', '9', '8']
     62 ['6', '7', '4', '5', '2', '3', '0', '1', '8', '9']
     63 ['7', '6', '5', '4', '3', '2', '1', '0', '9', '8']
     60 ['8', '9', '0', '1', '2', '3', '4', '5', '6', '7']
     66 ['8', '9', '2', '3', '0', '1', '6', '7', '4', '5']
     65 ['8', '9', '4', '5', '6', '7', '0', '1', '2', '3']
     53 ['8', '9', '6', '7', '4', '5', '2', '3', '0', '1']
     62 ['9', '8', '1', '0', '3', '2', '5', '4', '7', '6']
     52 ['9', '8', '3', '2', '1', '0', '7', '6', '5', '4']
     73 ['9', '8', '5', '4', '7', '6', '1', '0', '3', '2']
     76 ['9', '8', '7', '6', '5', '4', '3', '2', '1', '0']

正如在本回答开头提到的那样，在Python 3.6中情况已经不再如此。

$ for x in {0..999}
> do
>   python3.6 -c "print(list({str(i): i for i in range(10)}.keys()))"
> done | sort | uniq -c
   1000 ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']