다른 질문에 대한 제로 피레 우스 ‘대답을 감안할 때 , 우리는이
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 % ¹입니다 .
전혀 이상하게도 이것이 바로 Zero Piraeus가 측정 한 것입니다.
¹ 기술적으로 이것조차도 분명하지 않습니다. 우리는 재해 싱 때문에 5 개의 해시를 모두 유일하게 가장 할 수 있지만, 선형 프로빙 때문에 실제로는 “번치”구조가 발생할 가능성이 더 높습니다. 실제로 우리에게 영향을주지는 않습니다.
