Warum Tupel (set ([1, "a", "b", "c", "z", "f"])) == tuple (set (["a", "b", "c") , "z", "f", 1])) 85% der Zeit mit Hash Randomisierung aktiviert?

Question

Given Zero Piraeus' answer to another question, haben wir, dass

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

Drucke True etwa 85% der Zeit mit hash randomization aktiviert. Warum 85%?

Answer 1

ich alle Leser dieser Frage anzunehmen, werde beide gelesen haben:

• Zero Piraeus' answer und

• My explanation of CPython's dictionaries.

Das erste, was zu beachten ist, dass Hash-Randomisierung auf Dolmetscher Start-up entschieden wird.

Der Hash eines jeden Buchstabens ist für beide Sets gleich, es kann also nur auf eine Kollision ankommen (wenn die Reihenfolge betroffen ist).

---

Durch den Abzug dieser zweiten Verbindung kennen wir die Trägeranordnung für diese Sätze bei Länge beginnt 8:

_ _ _ _ _ _ _ _ 

Im ersten Fall setzen wir 1:

_ 1 _ _ _ _ _ _ 

und dann den Rest einfügen:

α 1 ? ? ? ? ? ? 

Dann wird auf Größe rehashed 32:

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

Im zweiten Fall, legen wir den Rest:

? β ? ? ? ? ? ? 

Und dann versuchen 1 einzufügen:

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

Und dann wird es wieder aufgepeppt:

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

Ob die Iterationsreihenfolge unterschiedlich ist, hängt also nur davon ab, ob β existiert.

---

die Wahrscheinlichkeit eines β ist die Chance, dass eine der 5 Briefe 1 modulo 8 und Hash 1 modulo 32.

Da etwas hash wird, die 32 ebenfalls auf 1 modulo Hashes Hashes zu 1 modulo 8, wollen wir die Möglichkeit finden, dass die 32 Slots, einer der fünf in Slot 1:

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

5/32 sind 0,15625, so ein 15.625% Chance¹ der Aufträge sind unterschiedlich zwischen den beiden festgelegten Konstruktionen.

---

Nicht sehr seltsam, das ist genau, was Zero Piraeus gemessen hat.

---

_{¹Technically auch das ist nicht offensichtlich. Wir können jeden der 5 Hashes aufgrund der Umschichtung eindeutig vorgeben, aber aufgrund von linearem Sondieren ist es wahrscheinlicher, dass "gebündelte" Strukturen auftreten ... aber weil wir nur schauen, ob ein einzelner Slot besetzt ist, ist dies nicht der Fall Das betrifft uns nicht wirklich.}