Hypothesis

Chi squared test를 수행하기에 앞서 Hash Table에 대한 전제 조건을 설명하겠습니다.

1. Hash Table에 존재하는 bin의 개수는 m
2. Hash Table에 넣을 Key의 개수는 k

이를 전제로 하나의 bin에 이상적으로 들어갈 key의 개수는 k / m 개입니다(Uniform Distribution).

또한 k가 카이제곱분포의 자유도로 설정됩니다.

Chi squared Value

bin의 Index를 i라고 표현할 때, i는 0에서 m-1로 나타낼 수 있습니다.

bi를 i번째 bin에 들어있는 key의 개수라고 가정한다면 카이제곱값은 다음과 같습니다.

χ2 = Σ (bi - k / m)^2 / (k / m)

주어진 모든 k개의 key들을 Hash Function으로 계산하고 이를 토대로 bi값을 결정합니다.

Get the p-value

위와 같이 카이제곱값을 구한 것으로 토대로, 자유도가 m인 카이제곱분포 상에서 p-value를 구합니다.

이 p-value값이 너무 작거나, 너무 큰 경우 Uniform Distribution을 나타낸다는 가정을 기각하게 됩니다.