Dada a resposta de Zero Piraeus a outra pergunta , temos que
x = tuple(set([1, "a", "b", "c", "z", "f"]))
y = tuple(set(["a", "b", "c", "z", "f", 1]))
print(x == y)Imprime Truecerca de 85% das vezes com a randomização de hash habilitada. Por que 85%?
Vou supor que qualquer leitor desta questão tenha lido ambos:
A primeira coisa a notar é que a randomização do hash é decidida na inicialização do interpretador.
O hash de cada letra será o mesmo para os dois conjuntos, então a única coisa que importa é se houver uma colisão (onde a ordem será afetada).
Pelas deduções desse segundo link, sabemos que a matriz de apoio para esses conjuntos começa no comprimento 8:
_ _ _ _ _ _ _ _No primeiro caso, inserimos 1:
_ 1 _ _ _ _ _ _e depois insira o resto:
α 1 ? ? ? ? ? ?Em seguida, é refeito para o tamanho 32:
1 can't collide with α as α is an even hash
↓ so 1 is inserted at slot 1 first
? 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?No segundo caso, inserimos o resto:
? β ? ? ? ? ? ?E então tente inserir 1:
Try to insert 1 here, but will
↓ be rehashed if β exists
? β ? ? ? ? ? ?E então será refeito:
Try to insert 1 here, but will
be rehashed if β exists and has
↓ not rehashed somewhere else
? β ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Portanto, se as ordens de iteração são diferentes depende apenas da existência de β.
A chance de um β é a chance de qualquer uma das 5 letras hash para 1 módulo 8 e hash para 1 módulo 32.
Uma vez que tudo que faz hash para 1 módulo 32 também faz hash para 1 módulo 8, queremos encontrar a chance de que, dos 32 slots, um dos cinco esteja no slot 1:
5 (number of letters) / 32 (number of slots)5/32 é 0,15625, então há uma chance de 15,625 %¹ dos pedidos serem diferentes entre os dois conjuntos de construções .
Não muito estranhamente, isso é exatamente o que Zero Piraeus mediu.
“Tecnicamente, até isso não é óbvio. Podemos fingir que cada um dos 5 hashes exclusivamente por causa do rehashing, mas por causa da sondagem linear é realmente mais provável que ocorram estruturas "agrupadas" ... mas porque estamos apenas observando se um único slot está ocupado, isso não realmente não nos afeta.