¿Por qué el orden del diccionario no es determinista?

Question

¿Por qué el orden del diccionario no es determinista?

Recientemente cambié de Python 2.7 a Python 3.3, y parece que mientras en Python 2 el orden de las claves del diccionario era arbitrario pero consistente, en Python 3 el orden de las claves de un diccionario obtenido con p.ej. vars() parece no determinista.

Si corro:

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

Tanto en Python 2.7 como en Python 3.3, entonces:

Python 2.7 consistentemente me da

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

Con Python 3.3, puedo obtener cualquier orden aleatorio-para ejemplo:

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

¿De dónde viene este no-determinismo? Y por qué es algo como

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

Consistent consistente entre corridas, siempre dando

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

… ?

30

python python-3.x dictionary python-3.3 non-deterministic

Author: Zero Piraeus, 2013-02-19

Source

1 answers

score 35 · Accepted Answer

Actualización: En Python 3.6, dict tiene una nueva implementación que conserva el orden de inserción. Sin embargo, este es un detalle de implementación, y no debe confiarse en él.

Este es el resultado de una corrección de seguridad de 2012, que estaba habilitada por defecto en Python 3.3 (desplácese hacia abajo hasta "Mejoras de seguridad").

Del anuncio:

La aleatorización Hash hace que el orden de iteración de los dictados y conjuntos sea impredecible y difiere entre las ejecuciones de Python. Python nunca ha garantizado orden de iteración de claves en un dict o conjunto, y se aconseja a las aplicaciones que nunca confía en ello. Históricamente, el orden de iteración dict no ha cambiado muy a menudo liberaciones y siempre ha sido consistente entre sucesivas ejecuciones de Python. Por lo tanto, algunas aplicaciones existentes pueden estar confiando en dict o orden de conjuntos. Debido a esto y el hecho de que muchas aplicaciones Python que no aceptan entrada no confiable no son vulnerables a este ataque, en todas las versiones estables de Python mencionado aquí, LA ALEATORIZACIÓN DE HASH ESTÁ DESHABILITADA DE FORMA PREDETERMINADA.

Como se señaló anteriormente, el último bit en mayúscula ya no es verdadero en Python 3.3.

Véase también: object.__hash__() documentación (barra lateral" Nota").

Si es absolutamente necesario, puede deshabilitar la aleatorización hash en las versiones de Python afectadas por este comportamiento configurando el PYTHONHASHSEED variable de entorno a 0.

Su contraejemplo:

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

Does no de hecho siempre da el mismo resultado en Python 3.3, aunque el número de órdenes diferentes es limitado debido a la forma en que se manejan las colisiones hash:

$ 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']

Como se señaló al principio de esta respuesta, ese ya no es el caso en 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']