Introduce

smhasher의 Distribution wiki 및 FillFactor wiki에 나온 내용을 정리한 페이지입니다.

Contents

• Relative Work
• Flaw
• Assume
• FillFactor

Relative Work

Key들이 Hash Table의 bins에 효율적으로 분포했는 지를 파악하기 위해서 Test Distribution과 Ideal Distribution을 비교합니다.

특정 분포에서 기대되는 work의 크기를 Expected Work(EW)라고 표현할 때

Test Distribution의 EW / Ideal Distribution의 EW = Relative Work(RW)를 통해서 이상적인 분포와 비교할 수 있습니다.

Flaw

하지만 여기에는 문제가 있는데

첫 번째로 RW가 Hash Table의 크기와 key의 개수에 너무 영향을 많이 받기 때문에 다른 table에서 구해진 RW끼리 비교하는 것이 어렵다는 것이고,

두 번째로 RW는 lower bound는 있지만 upper bound는 table의 크기와 key의 개수에 따라 매우 커질 수 있다는 것입니다.

세 번째로 RW는 통계적으로 결함이 있는 분포에서도 괜찮은 값이 나올 수 있다는 것입니다.

그리하여 RW의 단점을 가지지 않는 새로운 지표인 FillFactor를 만들었습니다.

이 지표는 0에서 1사이의 값을 가지기 때문에 중간값에 대한 의미있는 해석을 할 수 있고, 다른 table의 값과도 비교할 수 있습니다.

Assume

Hash Table에 N개의 bins, K개의 key가 있다고 가정합니다.

각 bin들에 들어간 key의 개수를 Bi라고 부를 때 Bi의 기대값은 K / N입니다.

그리고 각 Bi들에 대해서 root-square-mean을 계산하고 이를 R로 부르겠습니다.

R = { (B1^2 + B2^2 + ... + BN^2) / N }^(1/2)

Ideal Distribution에서 사용하는 bins의 개수를 F라고 정의하겠습니다.

즉 Ideal Distribution이 0번부터 F번까지만 사용하고 F + 1번부터 N - 1번까지는 비어있는 bins로 사용한다고 가정하겠습니다.

이 경우 F가 1이라면 가장 효율이 안좋은 것이고, F가 N이라면 가장 효율이 좋은 상황입니다.

FillFactor

root-square-mean을 구하는 함수를 MR이라고 하면 Ideal Distribution의 root-square-mean은 MR(F,N,K)로 표현할 수 있습니다.

이 값을 Test Distribution의 root-square-mean인 R값과 비교하여 F를 역으로 구합니다.

즉 R = MR(F,N,K)라는 식을 세우고 이를 변형하여 F = ~ 와 같은 방식으로 표현합니다.

FillFactor wiki에 따르면 F라는 값은

double f = (k*k - 1) / (n*r*r - k); // k : total key count, n : total bin count, r : root-square-mean of test

이와 같이 표현할 수있습니다.

그리고 이 F값을 통해서 FillFactor를 표현합니다.

return 1 - (f / n);

결국 FillFactor가 의미하는 것은 모든 key들이 F개의 bins에 이상적으로 분포하였을 때, 사용되지 않는 bins의 비율입니다.

즉 Test Distribution이 FillFactor만큼을 waste하는 Ideal Distribution과 같은 효율을 보인다는 의미입니다.