Ordenamiento 'extraño' de conjuntos en python

Cuando convierto una lista de Python 3.8.0 en un conjunto, la ordenación del conjunto resultante * está altamente estructurada de una manera no trivial. ¿Cómo se extrae esta estructura de la lista pseudoaleatoria?

Como parte de un experimento que estoy ejecutando, estoy generando un conjunto aleatorio. Me sorprendió ver que trazar el set de repente mostraba una estructura lineal inesperada en el set. Entonces, hay dos cosas que me desconciertan: ¿por qué la conversión a un resultado establecido tiene un orden * que termina resaltando esta estructura? y, en menor medida, ¿por qué el conjunto pseudoaleatorio tiene esta estructura "oculta"?

El código:

X = [randrange(250) for i in range(30)]
print(X)
print(set(X))

qué salidas, por ejemplo

[238, 202, 245, 94, 111, 106, 148, 164, 154, 113, 128, 10, 196, 141, 69, 38, 106, 8, 40, 53, 160, 87, 85, 13, 38, 147, 204, 50, 162, 91]

{128, 8, 10, 141, 13, 147, 148, 154, 160, 162, 164, 38, 40, 50, 53, 196, 69, 202, 204, 85, 87, 91, 94, 106, 238, 111, 113, 245}

Un gráfico ** de la lista anterior parece bastante aleatorio, como se esperaba:

mientras que el trazado del conjunto (como se ordena en la salida) exhibe la estructura presente en el conjunto:

Este comportamiento es 100% coherente en mi máquina (más ejemplos a continuación) con los valores 250 y 30 utilizados en el código anterior (el ejemplo que utilicé no está seleccionado, es el último que ejecuté). Ajustar estos valores a veces da como resultado una estructura ligeramente diferente (por ejemplo, un subconjunto de tres progresiones aritméticas *** en lugar de dos).

¿Es esto reproducible en las máquinas de otras personas? Por supuesto, que tal estructura exista parece indicar una generación de números pseudoaleatorios no tan grande, pero esto no explica cómo la conversión a un conjunto de alguna manera "extraería" esta estructura. Hasta donde sé, no existe una garantía formal de que el orden de un conjunto (cuando se convierte de una lista) sea determinista (e incluso si lo es, no se realiza un ordenamiento sofisticado en segundo plano). Entonces, ¿cómo está pasando esto?

(*): Lo sé, los conjuntos son colecciones desordenadas, pero quiero decir "ordenadas" en el sentido de que, al llamar a la printdeclaración, el conjunto se emite en un orden que resalta constantemente la estructura subyacente del conjunto.

(**): Estas parcelas son de Wolfram Alpha. Dos ejemplos más están a continuación:

(***): Dos gráficos al cambiar el rango de los números aleatorios de 250 a 500:

Básicamente, esto se debe a dos cosas:

• Un conjunto en Python se implementa usando una tabla hash ,
• El hash de un entero es el entero mismo.

Por lo tanto, el índice de que aparezca un número entero en la matriz subyacente estará determinado por el valor del entero, módulo de la longitud de la matriz subyacente. Entonces, los enteros tenderán a permanecer en orden ascendente cuando colocas un rango contiguo de ellos en un conjunto:

>>> list(set(range(10000))) == list(range(10000))
True # this can't be an accident!

Si no tiene todos los números de un rango contiguo, entonces entra en juego la parte "módulo de la longitud de la matriz subyacente":

>>> r = range(0, 50, 4)
>>> set(r)
{0, 32, 4, 36, 8, 40, 12, 44, 16, 48, 20, 24, 28}
>>> sorted(r, key=lambda x: x % 32)
[0, 32, 4, 36, 8, 40, 12, 44, 16, 48, 20, 24, 28]

La secuencia es predecible si conoce la longitud de la matriz subyacente y el algoritmo (determinista) para agregar elementos. En este caso, la longitud de la matriz es 32, porque inicialmente es 8 y se cuadruplica mientras se agregan elementos.

Excepto por un blip cerca del final (porque los números 52 y 56 no están en el conjunto), el rango se divide en dos secuencias 0, 4, 8, ...y se 32, 36, 40, ...alternan porque los hashes, que son los valores de los números, se toman en el módulo 32 para elegir índices en la matriz. Hay colisiones; por ejemplo, 4 y 36 son iguales al módulo 32, pero primero se agregó 4 al conjunto, por lo que 36 termina en un índice diferente.

Aquí hay una tabla para esta secuencia. La estructura en sus gráficos es solo una versión más ruidosa, porque generó sus números aleatoriamente en lugar de un rango con un paso.

El número de secuencias intercaladas dependerá del tamaño del conjunto en proporción a la longitud del rango del que se toman muestras de los números, ya que eso determina cuántas veces la longitud del rango "envuelve" el módulo de la longitud de la matriz subyacente de la tabla hash. Aquí hay un ejemplo con tres secuencias intercaladas 0, 6, 12, ..., 66, 72, 78, ...y 36, 42, 48, ...:

>>> set(range(0, 90, 6))
{0, 66, 36, 6, 72, 42, 12, 78, 48, 18, 84, 54, 24, 60, 30}