¿Por qué el orden en los diccionarios y conjuntos es arbitrario?

No entiendo cómo se realiza un bucle sobre un diccionario o un conjunto en Python por orden 'arbitrario'.

Quiero decir, es un lenguaje de programación, así que todo en el lenguaje debe estar 100% determinado, ¿correcto? Python debe tener algún tipo de algoritmo que decida qué parte del diccionario o conjunto se elige, primero, segundo, etc.

¿Qué me estoy perdiendo?

Nota: Esta respuesta fue escrita antes de que la implementación del dicttipo cambiara, en Python 3.6. La mayoría de los detalles de implementación en esta respuesta aún se aplican, pero el orden de inclusión de las claves en los diccionarios ya no está determinado por los valores hash. La implementación del conjunto permanece sin cambios.

El orden no es arbitrario, sino que depende del historial de inserción y eliminación del diccionario o conjunto, así como de la implementación específica de Python. Para el resto de esta respuesta, para 'diccionario', también puede leer 'set'; los conjuntos se implementan como diccionarios con solo claves y sin valores.

Las claves son hash, y los valores hash se asignan a las ranuras en una tabla dinámica (puede crecer o reducirse según las necesidades). Y ese proceso de mapeo puede conducir a colisiones, lo que significa que una clave tendrá que ubicarse en un siguiente espacio en función de lo que ya existe.

Al enumerar los bucles de contenido en las ranuras, las claves se enumeran en el orden en que residen actualmente en la tabla.

Tome las llaves 'foo'y 'bar', por ejemplo, y supongamos que el tamaño de la tabla es de 8 ranuras. En Python 2.7, hash('foo')es -4177197833195190597, hash('bar')es 327024216814240868. Módulo 8, eso significa que estas dos teclas se ubican en las ranuras 3 y 4 y luego:

>>> hash('foo')
-4177197833195190597
>>> hash('foo') % 8
3
>>> hash('bar')
327024216814240868
>>> hash('bar') % 8
4

Esto informa su orden de listado:

>>> {'bar': None, 'foo': None}
{'foo': None, 'bar': None}

Todas las ranuras, excepto 3 y 4, están vacías, al recorrer la tabla se enumeran primero las ranuras 3 y luego las ranuras 4, por lo que 'foo'se enumeran antes 'bar'.

bary baz, sin embargo, tienen valores hash que están exactamente separados por 8 y, por lo tanto, se asignan exactamente a la misma ranura 4:

>>> hash('bar')
327024216814240868
>>> hash('baz')
327024216814240876
>>> hash('bar') % 8
4
>>> hash('baz') % 8
4

Su orden ahora depende de qué clave se introdujo primero; la segunda clave deberá moverse a la siguiente ranura:

>>> {'baz': None, 'bar': None}
{'bar': None, 'baz': None}
>>> {'bar': None, 'baz': None}
{'baz': None, 'bar': None}

El orden de la tabla difiere aquí, porque una u otra clave se asignó primero.

El nombre técnico de la estructura subyacente utilizada por CPython (la implementación de Python más utilizada) es una tabla hash , una que utiliza direccionamiento abierto. Si tiene curiosidad y entiende C bastante bien, eche un vistazo a la implementación de C para ver todos los detalles (bien documentados). También puede ver esta presentación de Pycon 2010 de Brandon Rhodes sobre cómo dictfunciona CPython , o recoger una copia de Beautiful Code , que incluye un capítulo sobre la implementación escrito por Andrew Kuchling.

Tenga en cuenta que a partir de Python 3.3, también se usa una semilla aleatoria de hash, lo que hace que las colisiones de hash sean impredecibles para evitar ciertos tipos de denegación de servicio (donde un atacante hace que un servidor de Python no responda al causar colisiones de hash masivas). Esto significa que el orden de un diccionario o conjunto dado también depende de la semilla aleatoria hash para la invocación actual de Python.

Otras implementaciones son libres de usar una estructura diferente para los diccionarios, siempre que satisfagan la interfaz documentada de Python para ellos, pero creo que todas las implementaciones hasta ahora usan una variación de la tabla hash.

CPython 3.6 presenta una nueva dict implementación que mantiene el orden de inserción, y es más rápido y más eficiente en el arranque de memoria. En lugar de mantener una tabla dispersa grande donde cada fila hace referencia al valor hash almacenado y los objetos clave y de valor, la nueva implementación agrega una matriz hash más pequeña que solo hace referencia a índices en una tabla 'densa' separada (una que solo contiene tantas filas) ya que hay pares clave-valor reales), y es la tabla densa que enumera los elementos contenidos en orden. Vea la propuesta a Python-Dev para más detalles . Tenga en cuenta que en Python 3.6 esto se considera un detalle de implementación, Python-the-language no especifica que otras implementaciones tengan que mantener el orden. Esto cambió en Python 3.7, donde este detalle se elevó para ser una especificación de lenguaje ; para que cualquier implementación sea correctamente compatible con Python 3.7 o posterior, debe copiar este comportamiento de preservación del orden. Y para ser explícito: este cambio no se aplica a los conjuntos, ya que los conjuntos ya tienen una estructura hash 'pequeña'.

Python 2.7 y posteriores también proporcionan una OrderedDictclase , una subclase dictque agrega una estructura de datos adicional para registrar el orden de las claves. Al precio de cierta velocidad y memoria extra, esta clase recuerda en qué orden insertó las llaves; listar claves, valores o elementos lo hará en ese orden. Utiliza una lista doblemente vinculada almacenada en un diccionario adicional para mantener el orden actualizado de manera eficiente. Vea la publicación de Raymond Hettinger que describe la idea . OrderedDictLos objetos tienen otras ventajas, como ser reordenables .

Si desea un conjunto ordenado, puede instalar el osetpaquete ; Funciona en Python 2.5 y versiones posteriores.

Esto es más una respuesta a Python 3.41 Un conjunto antes de que se cerrara como duplicado.

Los otros tienen razón: no confíe en el orden. Ni siquiera finjas que hay uno.

Dicho esto, hay una cosa en la que puede confiar:

list(myset) == list(myset)

Es decir, el orden es estable .

Comprender por qué hay un orden percibido requiere comprender algunas cosas:

• Que Python usa conjuntos hash ,

• Cómo se almacena el hash set de CPython en la memoria y

• Cómo se numeran los números

Desde la parte superior:

Un conjunto de hash es un método para almacenar datos aleatorios con tiempos de búsqueda realmente rápidos.

Tiene una matriz de respaldo:

# A C array; items may be NULL,
# a pointer to an object, or a
# special dummy object
_ _ 4 _ _ 2 _ _ 6

Ignoraremos el objeto ficticio especial, que existe solo para hacer que las eliminaciones sean más fáciles de manejar, porque no eliminaremos de estos conjuntos.

Para tener una búsqueda realmente rápida, haces algo de magia para calcular un hash de un objeto. La única regla es que dos objetos que son iguales tienen el mismo hash. (Pero si dos objetos tienen el mismo hash, pueden ser desiguales).

Luego realiza un índice tomando el módulo por la longitud de la matriz:

hash(4) % len(storage) = index 2

Esto hace que sea realmente rápido acceder a elementos.

Hashes sólo son la mayor parte de la historia, como hash(n) % len(storage)y hash(m) % len(storage)pueden resultar en el mismo número. En ese caso, varias estrategias diferentes pueden intentar resolver el conflicto. CPython usa "sondeo lineal" 9 veces antes de hacer cosas complicadas, por lo que buscará a la izquierda de la ranura hasta 9 lugares antes de buscar en otro lado.

Los conjuntos de hash de CPython se almacenan así:

• Un conjunto de hash no puede tener más de 2/3 de capacidad . Si hay 20 elementos y la matriz de respaldo tiene 30 elementos de largo, el almacén de respaldo cambiará de tamaño para ser más grande. Esto se debe a que se producen colisiones con mayor frecuencia en pequeñas tiendas de respaldo, y las colisiones ralentizan todo.

• La tienda de respaldo cambia de tamaño en potencias de 4, comenzando en 8, excepto para conjuntos grandes (elementos de 50k) que cambian de tamaño en potencias de dos: (8, 32, 128, ...).

Por lo tanto, cuando crea una matriz, el almacén de respaldo es de longitud 8. Cuando está lleno 5 y agrega un elemento, contendrá brevemente 6 elementos. 6 > ²⁄₃·8así que esto provoca un cambio de tamaño, y la tienda de respaldo se cuadruplica al tamaño 32.

Finalmente, hash(n)solo devuelve los nnúmeros (excepto -1que es especial).

Entonces, veamos el primero:

v_set = {88,11,1,33,21,3,7,55,37,8}

len(v_set)es 10, por lo que la tienda de respaldo es al menos 15 (+1) después de que se hayan agregado todos los artículos . El poder relevante de 2 es 32. Entonces, la tienda de respaldo es:

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

Tenemos

hash(88) % 32 = 24
hash(11) % 32 = 11
hash(1)  % 32 = 1
hash(33) % 32 = 1
hash(21) % 32 = 21
hash(3)  % 32 = 3
hash(7)  % 32 = 7
hash(55) % 32 = 23
hash(37) % 32 = 5
hash(8)  % 32 = 8

así que estos se insertan como:

__  1 __  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
   33 ← Can't also be where 1 is;
        either 1 or 33 has to move

Entonces esperaríamos una orden como

{[1 or 33], 3, 37, 7, 8, 11, 21, 55, 88}

con el 1 o 33 que no está al principio en otro lugar. Esto usará un sondeo lineal, por lo que tendremos:

       ↓
__  1 33  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

o

       ↓
__ 33  1  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

Es posible que espere que el 33 sea el desplazado porque el 1 ya estaba allí, pero debido al cambio de tamaño que ocurre a medida que se construye el conjunto, este no es realmente el caso. Cada vez que se reconstruye el conjunto, los elementos ya agregados se reordenan de manera efectiva.

Ahora puedes ver por qué

{7,5,11,1,4,13,55,12,2,3,6,20,9,10}

Podría estar en orden. Hay 14 elementos, por lo que la tienda de respaldo es al menos 21 + 1, lo que significa 32:

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

1 a 13 hash en los primeros 13 espacios. 20 va en la ranura 20.

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ __ __ __ __ __ __ __ __ __

55 va en la ranura hash(55) % 32que es 23:

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ 55 __ __ __ __ __ __ __ __

Si elegimos 50 en su lugar, esperaríamos

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ 50 __ 20 __ __ __ __ __ __ __ __ __ __ __

Y he aquí y he aquí:

{1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 20, 50}
#>>> {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 50, 20}

pop se implementa simplemente por el aspecto de las cosas: atraviesa la lista y aparece la primera.

Todo esto es detalle de implementación.

"Arbitrario" no es lo mismo que "no determinado".

Lo que dicen es que no hay propiedades útiles del orden de iteración del diccionario que estén "en la interfaz pública". Es casi seguro que hay muchas propiedades del orden de iteración que están completamente determinadas por el código que implementa actualmente la iteración del diccionario, pero los autores no te las prometen como algo que puedes usar. Esto les da más libertad para cambiar estas propiedades entre versiones de Python (o incluso en diferentes condiciones de funcionamiento, o completamente al azar en tiempo de ejecución) sin preocuparse de que su programa se rompa.

Por lo tanto, si escribe un programa que depende de cualquier propiedad en el orden del diccionario, entonces está "rompiendo el contrato" de usar el tipo de diccionario, y los desarrolladores de Python no prometen que esto siempre funcionará, incluso si parece funcionar. por ahora cuando lo pruebes. Básicamente es el equivalente a confiar en un "comportamiento indefinido" en C.

Las otras respuestas a esta pregunta son excelentes y están bien escritas. El OP pregunta "cómo", que yo interpreto como "cómo se salen con la suya" o "por qué".

La documentación de Python dice que los diccionarios no están ordenados porque el diccionario de Python implementa la matriz asociativa de tipos de datos abstractos . Como ellos dicen

el orden en que se devuelven los enlaces puede ser arbitrario

En otras palabras, un estudiante de informática no puede asumir que se ordena una matriz asociativa. Lo mismo es cierto para series en matemáticas

el orden en que se enumeran los elementos de un conjunto es irrelevante

y ciencias de la computación

un conjunto es un tipo de datos abstracto que puede almacenar ciertos valores, sin ningún orden en particular

La implementación de un diccionario utilizando una tabla hash es un detalle de implementación interesante porque tiene las mismas propiedades que las matrices asociativas en lo que respecta al orden.

Python usa la tabla hash para almacenar los diccionarios, por lo que no hay orden en los diccionarios u otros objetos iterables que usan la tabla hash.

Pero con respecto a los índices de elementos en un objeto hash, python calcula los índices en función del siguiente código dentrohashtable.c :

key_hash = ht->hash_func(key);
index = key_hash & (ht->num_buckets - 1);

Por lo tanto, como el valor hash de los enteros es el propio entero ^*, el índice se basa en el número ( ht->num_buckets - 1es una constante), por lo que el índice calculado por Bitwise-and entre (ht->num_buckets - 1)y el número en sí ^* (se espera que -1, que es hash, sea -2 ) y para otros objetos con su valor hash.

considere el siguiente ejemplo con set ese uso de tabla hash:

>>> set([0,1919,2000,3,45,33,333,5])
set([0, 33, 3, 5, 45, 333, 2000, 1919])

Para el número 33 tenemos:

33 & (ht->num_buckets - 1) = 1

Que en realidad es:

'0b100001' & '0b111'= '0b1' # 1 the index of 33

Nota en este caso(ht->num_buckets - 1) es 8-1=7o 0b111.

Y para 1919 :

'0b11101111111' & '0b111' = '0b111' # 7 the index of 1919

Y para 333 :

'0b101001101' & '0b111' = '0b101' # 5 the index of 333

Para más detalles sobre la función hash de Python, es bueno leer las siguientes citas del código fuente de Python :

Principales sutilezas por delante: la mayoría de los esquemas hash dependen de tener una función hash "buena", en el sentido de simular aleatoriedad. Python no: sus funciones hash más importantes (para cadenas e ints) son muy regulares en casos comunes:

>>> map(hash, (0, 1, 2, 3))
  [0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
  [-1658398457, -1658398460, -1658398459, -1658398462]

¡Esto no es necesariamente malo! Por el contrario, en una tabla de tamaño 2 ** i, tomar los bits i de orden inferior como el índice de la tabla inicial es extremadamente rápido, y no hay colisiones en absoluto para los dictados indexados por un rango contiguo de ints. Lo mismo es aproximadamente cierto cuando las claves son cadenas "consecutivas". Entonces, esto da un comportamiento mejor que al azar en casos comunes, y eso es muy deseable.

OTOH, cuando ocurren colisiones, la tendencia a llenar segmentos contiguos de la tabla hash hace que una buena estrategia de resolución de colisiones sea crucial. Tomar solo los últimos i bits del código hash también es vulnerable: por ejemplo, considere la lista [i << 16 for i in range(20000)]como un conjunto de claves. Dado que los ints son sus propios códigos hash, y esto cabe en un dict de tamaño 2 ** 15, los últimos 15 bits de cada código hash son todos 0: todos asignan al mismo índice de tabla.

Pero atender casos inusuales no debería retrasar los habituales, por lo que de todos modos solo tomamos los últimos bits. Depende de la resolución de colisión hacer el resto. Si usualmente encontramos la clave que estamos buscando en el primer intento (y resulta que generalmente lo hacemos, el factor de carga de la tabla se mantiene por debajo de 2/3, por lo que las probabilidades están sólidamente a nuestro favor), entonces tiene más sentido mantener barato el cálculo inicial del índice.

_{* La función hash para la clase int:}

class int:
    def __hash__(self):
        value = self
        if value == -1:
            value = -2
        return value

Comenzando con Python 3.7 (y ya en CPython 3.6 ), los elementos del diccionario permanecen en el orden en que fueron insertados .