크기가 m 인 해시 테이블에 n 개의 항목을 삽입 할 때 각 항목의 대상이 독립적으로 일정하게 랜덤하다고 가정 할 때 충돌이 발생하지 않을 확률은 얼마입니까? 해시 테이블의 충돌 확률
임의의 주어진 위치에 대해 주어진 쌍에 대해 두 항목이 해당 위치에 해시되지 않을 확률은 (m-1)/m입니다.
그런 다음 모든 주어진 위치에 대해 위 쌍이 ALL 일 확률은 ((m-1)/m)^(nC2)입니다.
그러면 모든 위치에 대해 이것이 사실 일 확률은 [((m-1)/m)^(nC2)]^(m)입니다.
당신은 그러한 추론에서 몇 가지 실수를했습니다. 주된 것은 당신이 함께 해쉬하지 않는 쌍에 대한 확률이 독립적이라고 가정한다는 것입니다, 그래서 당신은 그것들을 함께 곱할 수 있습니다. 당신은 그것이 사실 인 것을 나타내지 않았으며, 사실 그것은 사실이 아닙니다. 세 요소 a, b 및 c를 고려하십시오. a와 b가 모두 c와 충돌하지 않는다는 것을 안다면, 처음 m 장소가 아닌 m-1 장소로 제한되며 c를 무시한 경우보다 서로 충돌 할 가능성이 더 큽니다.
여기에 원하는 확률을 찾는 간단한 방법이 있습니다. 충돌을 무시한 총 가능성을 살펴보면, n 개의 항목 각각에는 m 개의 위치가 있습니다. 이러한 게재 위치는 독립적이므로 전체 주문 가능성은 m^n (또는 Python의 경우 m ** n)입니다.
충돌이 없다는 것을 알고 있으면 해당 항목은 교체하지 않고 m 위치에서 선택하는 방법입니다. 따라서 우리가 고려할 때 mPn 가능성이 생깁니다. 대체 할 수없고 순서 (순열)없이 m 개의 항목 중에서 n 개의 항목을 선택할 수있는 방법입니다. 따라서 원하는 확률은
mPn/m^n = (m!)/(mn)! * m^n) = m/m * (m-1)/m * (m-2)/m * ... * (m-n + 1)/m
마지막 표현식에는 n 가지 요인이 있습니다. (이것은 MathJax에서 훨씬 더 좋을 것입니다!) 당신은 당신의 목적에 가장 적합한 3 가지 표현식 중 어느 것을 선택할 수 있습니다.
물론 이러한 표현식을 제시 할 수있는 다른 방법이 있습니다. 그 마지막 것은 아무런 충돌이 없을 확률, m 슬롯에 1 개의 아이템을 놓고 이전의 충돌 시간이 주어지지 않은 제 2 아이템을 놓을 조건부 확률, 이전의 충돌 시간이 주어지지 않은 제 3 아이템을 배치하는 조건부 확률로 생각할 수있다.
이러한 표현식은 매우 쉽게 테스트 할 수 있습니다. m과 n의 특정 작은 값을 선택하고, m 중에서 n 개 항목의 가능한 모든 선택을 생성하고 충돌이없는 경험적 확률을 찾으십시오. 위의 수식에 동의해야합니다. 프로그래밍 언어와 코딩의 선택을 맡길 것입니다. 결국 이것은 프로그래밍 사이트입니다. 방금 파이썬에서 n과 m의 다중 선택을 위해이 작업을 수행했습니다.