나는 n 키와 크기가 n 인 해시 테이블을 가지고 있습니다.예상되는 해싱 할 빈 슬롯 수
예상되는 빈 슬롯 수를 계산하려고합니다.
나는 모든 키가 똑같이 슬롯에 들어가기 쉽다는 Hashing Assumption 유니폼을 알고 있습니다.
지금까지 n 슬롯을 n 슬롯으로 동일한 기회가있는 n 키를 사용하여 n^2 개의 가능한 조합을 만들었습니다.
여기에서 어디로 가야할지 모르겠다. 올바른 방향으로 향한 어떤 점도 인정 될 것이다! 감사합니다. .
첫째, 가능한 조합의 수는 각 키 n 보낸 n^2하지만 n^n없는 것은 슬롯 착륙 n 가능성이있다. 인해 모든 슬롯에 대칭 인
다음, P 각 단일 슬롯이 비어 끝 확률 인 E = n * P 빈 슬롯의 예상 수. 이는 임의의 값이 종속 된 경우에도 보유하는 linearity of expectation 때문입니다.
키이이 슬롯에 착륙 할 가능성이 Q 인 경우 Q = (n - 1)/n입니다.
n 키가 있기 때문에 고정 슬롯에 키가 도달하지 않을 확률은 PQ^n입니다.
이 모두를 요약하면 E = n * ((n - 1)/n)^n입니다. (n - 1/n)^n의 한계는 1/e (see here)이므로 예상되는 빈 슬롯 수는 n/e입니다.
먼저 해시 테이블의 유형을 지정해야합니다 (슬롯 당 여러 요소가 가능합니까? 그렇지 않은 경우 오버플로 처리, 즉 대체 슬롯을 결정하는 전략 또는 그와 유사한 방법) 및 실제 해시 함수 (데이터 유형 포함 요소의). – deviantfan
문제는 순전히 이론에 기초한 것이며 이것이 내가 작업하게 된 전부입니다. – user3196347