Почему tuple(set([1,"a","b","c","z","f"])) == tuple(set(["a","b","c","z","f",1])) 85% времени с включенной рандомизацией хеша?

Question

Учитывая ответ Зеро Пирея на другой вопрос, мы имеем

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

Печать True около 85% времени с включенной рандомизацией хеша. Почему 85%?

Answer 1

Я предполагаю, что все читатели этого вопроса прочитали оба:

• Нулевой ответ Пирея и

• Мое объяснение словарей CPython.

Первое, на что следует обратить внимание, - это то, что рандомизация хеша определяется при запуске интерпретатора.

Хэш каждой буквы будет одинаковым для обоих наборов, поэтому единственное, что может иметь значение, - это столкновение (где будет затронут порядок).

---

По выводам этой второй ссылки мы знаем, что резервный массив для этих наборов начинается с длины 8:

_ _ _ _ _ _ _ _

В первом случае мы вставляем 1:

_ 1 _ _ _ _ _ _

а затем вставьте остальные:

α 1 ? ? ? ? ? ?

Затем перефразируется до размера 32:

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

Во втором случае мы вставляем остальное:

? β ? ? ? ? ? ?

А затем попробуйте вставить 1:

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

И тогда это будет перефразировано:

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

Таким образом, отличаются ли порядки итераций только от того, существует ли β.

---

Вероятность β - это вероятность того, что любая из 5 букв будет хэшировать до 1 по модулю 8 и хэшировать до 1 по модулю 32.

Поскольку все, что хэширует до 1 по модулю 32, также хэширует до 1 по модулю 8, мы хотим найти вероятность того, что из 32 слотов один из пяти находится в слоте 1:

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

5/32 - это 0,15625, поэтому вероятность того, что ордера между двумя конструкциями сетов различаются, составляет 15,625%.

---

Совсем не странно, это именно то, что измерял Зеро Пирей.

---

_{"Технически даже это не очевидно. Мы можем притвориться, что каждый из 5 хэшей уникален из-за перефразирования, но из-за линейного зондирования, на самом деле, более вероятно, что "сгруппированные" структуры возникнут… но поскольку мы только смотрим, занят ли один слот, это не на самом деле не влияет на нас.}