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

Question

我最近从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一直给我

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

• 使用Python 3.3,我可以得到任何随机顺序 - 例如:

  ['__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']

......？

Answer 1

更新:在Python 3.6中,dict有一个新的实现,它保留了插入顺序.从Python 3.7开始,这种保留顺序的行为得到保证:

dict对象的插入顺序保存性质已被声明为Python语言规范的官方部分.

这是2012年安全修复的结果,默认情况下在Python 3.3中启用(向下滚动到"安全性改进").

从宣布:

散列随机化导致dicts和集的迭代顺序不可预测,并且在Python运行中不同.Python从未保证dict或set中键的迭代顺序,建议应用程序永远不要依赖它.从历史上看,dict迭代顺序在各个版本中并没有经常发生变化,并且在Python的连续执行之间始终保持一致.因此,一些现有的应用程序可能依赖于字典或集合排序.由于这一点以及许多不接受不受信任的输入的Python应用程序不容易受到这种攻击的事实,在这里提到的所有稳定的Python版本中,HASH RANDOMIZATION被DEFAULT禁用.

如上所述,Python 3.3中的最后一个大写位不再正确.

另见: object.__hash__()文档("注释"侧栏).

如果绝对必要,可以通过将PYTHONHASHSEED环境变量设置为,在受此行为影响的Python版本中禁用散列随机化0.

你的反例:

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

...实际上并不总是在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']

Answer 2

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

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

从一次运行到下一次运行仍然给出不同的结果。