python - ¿Por qué tuple(set([1, “a”, “b”, “c”, “z”, “f”]))== tuple(set([“a”, “b”, “c”, “Z”, “f”, 1])) ¿85% del tiempo con la aleatorización hash habilitada?

cpython python-internals

Question

Dada la respuesta de Zero Piraeus a otra pregunta , tenemos que

x = tuple(set([1, "a", "b", "c", "z", "f"]))
y = tuple(set(["a", "b", "c", "z", "f", 1]))
print(x == y)

Imprime True aproximadamente el 85% de las veces con la aleatorización hash habilitada. ¿Por qué el 85%?

Answer 1

Asumiré que cualquier lector de esta pregunta haya leído ambos:

• La respuesta de Zero Piraeus y

• Mi explicación de los diccionarios de CPython .

Lo primero a tener en cuenta es que la aleatorización de hash se decide al iniciar el intérprete.

El hash de cada letra será el mismo para ambos conjuntos, por lo que lo único que puede importar es si hay una colisión (donde el orden se verá afectado).

Por las deducciones de ese segundo enlace, sabemos que la matriz de respaldo para estos conjuntos comienza en la longitud 8:

_ _ _ _ _ _ _ _

En el primer caso, insertamos 1 :

_ 1 _ _ _ _ _ _

y luego inserte el resto:

α 1 ? ? ? ? ? ?

Luego se vuelve a colocar en el tamaño 32:

    1 can''t collide with α as α is an even hash
  ↓ so 1 is inserted at slot 1 first
? 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

En el segundo caso, insertamos el resto:

? β ? ? ? ? ? ?

Y luego intente insertar 1:

    Try to insert 1 here, but will
  ↓ be rehashed if β exists
? β ? ? ? ? ? ?

Y luego se volverá a compartir:

    Try to insert 1 here, but will
    be rehashed if β exists and has
  ↓ not rehashed somewhere else
? β ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

Entonces, si los órdenes de iteración son diferentes depende únicamente de si β existe.

La posibilidad de un β es la posibilidad de que cualquiera de las 5 letras se divida en 1 módulo 8 y se divida en 1 módulo 32.

Dado que todo lo que se convierte en 1 módulo 32 también lo hace en 1 módulo 8, queremos encontrar la posibilidad de que de las 32 ranuras, una de las cinco esté en la ranura 1:

5 (number of letters) / 32 (number of slots)

5/32 es 0.15625, por lo que hay un 15.625% de posibilidades¹ de que las órdenes sean diferentes entre las dos construcciones de conjuntos .

No es muy extraño en absoluto, esto es exactamente lo que midió Zero Piraeus.

_{¹ Técnicamente incluso esto no es obvio. Podemos fingir que cada uno de los 5 hashes es único debido a la repetición, pero debido al sondeo lineal, en realidad es más probable que ocurran estructuras "agrupadas" ... pero como solo estamos viendo si una sola ranura está ocupada, esto no En realidad no nos afecta.}