Учитывая ответ Нуля Пирея на другой вопрос , мы имеем
x = tuple(set([1, "a", "b", "c", "z", "f"]))
y = tuple(set(["a", "b", "c", "z", "f", 1]))
print(x == y)
Печатает True
примерно 85% времени с включенной случайностью хеширования . Почему 85%?
Учитывая ответ Нуля Пирея на другой вопрос , мы имеем
x = tuple(set([1, "a", "b", "c", "z", "f"]))
y = tuple(set(["a", "b", "c", "z", "f", 1]))
print(x == y)
Печатает True
примерно 85% времени с включенной случайностью хеширования . Почему 85%?
Я предполагаю, что любой читатель этого вопроса прочитал оба:
Первое, что следует отметить, это то, что рандомизация хэша определяется при запуске интерпретатора.
Хеш каждой буквы будет одинаковым для обоих наборов, поэтому единственное, что может иметь значение, - это наличие коллизии (где это повлияет на порядок).
Судя по выводам этой второй ссылки, мы знаем, что резервный массив для этих наборов начинается с длины 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 хэшей уникален из-за повторного хеширования, но из-за линейного зондирования на самом деле более вероятно возникновение «сгруппированных» структур ... но поскольку мы смотрим только на то, занят ли один слот, это не на нас не влияет.