Dlaczego tuple (set ([1, „a”, „b”, „c”, „z”, „f”])) == tuple (set ([„a”, „b”, „c”, „Z”, „f”, 1])) w 85% przypadków z włączoną randomizacją hash?

Biorąc pod uwagę odpowiedź Zero Piraeus na inne pytanie , mamy to

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

Drukuje Trueokoło 85% czasu z włączoną losowością mieszania . Dlaczego 85%?

— Veedrac
źródło

128

Zakładam, że wszyscy czytelnicy tego pytania przeczytali oba:

Pierwszą rzeczą, na którą należy zwrócić uwagę, jest to, że o losowaniu skrótu decyduje się przy uruchomieniu interpretera.

Skrót każdej litery będzie taki sam dla obu zestawów, więc jedyną rzeczą, która może mieć znaczenie, jest kolizja (gdzie wpłynie to na kolejność).

Z dedukcji tego drugiego łącza wiemy, że tablica podstawowa dla tych zestawów zaczyna się od długości 8:

_ _ _ _ _ _ _ _

W pierwszym przypadku wstawiamy 1:

_ 1 _ _ _ _ _ _

a następnie wstaw resztę:

α 1 ? ? ? ? ? ?

Następnie jest ponownie zawijany do rozmiaru 32:

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

W drugim przypadku wstawiamy resztę:

? β ? ? ? ? ? ?

A następnie spróbuj wstawić 1:

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

A potem zostanie powtórzony:

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

Zatem to, czy rzędy iteracji są różne, zależy wyłącznie od tego, czy istnieje β.

Szansa β to szansa, że którakolwiek z 5 liter będzie mieszać do 1 modulo 8 i hash do 1 modulo 32.

Ponieważ wszystko, co ma hash do 1 modulo 32, również hashuje do 1 modulo 8, chcemy znaleźć prawdopodobieństwo, że z 32 gniazd jeden z pięciu znajduje się w slocie 1:

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

5/32 to 0,15625, więc istnieje 15,625% prawdopodobieństwa¹, że zamówienia będą różne w obu zestawach konstrukcji .

Nie jest to wcale dziwne, dokładnie to zmierzył Zero Piraeus.

_{¹ Technicznie nawet to nie jest oczywiste. Możemy udawać, że każdy z 5 skrótów jest wyjątkowy z powodu ponownego haszowania, ale z powodu liniowego sondowania jest bardziej prawdopodobne, że pojawią się struktury „grupowe” ... ale ponieważ patrzymy tylko na to, czy jedno miejsce jest zajęte, to nie działa tak naprawdę na nas nie wpływa.}

— Veedrac
źródło