Perché tupla (set ([1, "a", "b", "c", "z", "f"])) == tupla (set (["a", "b", "c" , "z", "f", 1])) 85% delle volte con la randomizzazione dell'hash abilitata?

Question

Given Zero Piraeus' answer to another question, abbiamo che

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

Stampe True circa l'85% del tempo con hash randomization abilitato. Perché l'85%?

Answer 1

ho intenzione di assumere tutti i lettori di questo problema di aver letto entrambe:

• Zero Piraeus' answer e

• My explanation of CPython's dictionaries.

La prima cosa da notare è che hash randomizzazione è deciso interprete di start-up.

L'hash di ogni lettera sarà uguale per entrambi i set, quindi l'unica cosa che può avere importanza è se c'è una collisione (in cui l'ordine sarà interessato).

---

Con le deduzioni di tale secondo collegamento sappiamo che la matrice di supporto per questi insiemi inizia lunghezza 8:

_ _ _ _ _ _ _ _ 

Nel primo caso, inseriamo 1:

_ 1 _ _ _ _ _ _ 

e quindi inserire il resto:

α 1 ? ? ? ? ? ? 

Poi è rehashed alle dimensioni 32:

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

Nel secondo caso, inseriamo il resto:

? β ? ? ? ? ? ? 

E quindi provare ad inserire 1:

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

E poi verrà rielaborato:

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

Quindi, se gli ordini di iterazione sono diversi dipende esclusivamente dal fatto che β esista.

---

La possibilità di un β è la probabilità che una qualsiasi delle 5 lettere saranno hash per 1 modulo 8 e hash per 1 modulo 32.

Da tutto ciò che gli hash per 1 modulo 32 hash anche per 1 modulo 8, vogliamo trovare la probabilità che dei 32 slot, uno dei cinque è nello slot 1:

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

5/32 è 0,15625, quindi c'è un 15.Il 625% di probabilit๠degli ordini è diverso tra le due costruzioni.

---

Non molto stranamente, questo è esattamente ciò che ha misurato Zero Pireo.

---

_{¹Technically anche questo non è evidente. Possiamo fingere ognuno dei 5 hash in modo univoco a causa del rehashing, ma a causa del sondaggio lineare è in realtà più probabile che si verifichino strutture "raggruppate" ... ma poiché stiamo controllando solo se un singolo slot è occupato, questo non funziona in realtà ci influenzano}