Slightly different FillFactor - minseok127/HashSimulator GitHub Wiki

Introduce

Distribution wiki 및 FillFactor wiki에서는 root-square-mean을 통해 FillFactor를 유도했습니다.

하지만 직접 root-square-mean을 통해 수식을 전개해봤을 때, 같은 f를 유도하지 못하였습니다.

그래서 위의 페이지들과는 다른 방식으로 FillFactor와 비슷하지만 다른 수식을 유도해보겠습니다.

어떤 bin에 5개의 data가 들어있다고 생각해보겠습니다.

Hash Table이 Chaining Rule을 사용한다고 가정했을 때,

Linked List의 1번째 Data에 접근하기 위해서는 1개의 노드를 확인하면 됩니다.

Linked List의 2번째 Data에 접근하기 위해서는 2개의 노드를 확인해야 합니다.

Linked List의 3번째 Data에 접근하기 위해서는 3개의 노드를 확인해야 합니다.

...

이처럼 bin에 들어있는 어떠한 data에 접근하기 위해서는 그 data가 Linked List에 위치한 index만큼의 확인을 해야합니다.

그리고 bin에 들어있는 모든 data에 접근하기 위해서는 등차수열의 합만큼의 확인이 필요합니다.

주어진 모든 key들에 대해서 이에 대응하는 data들을 찾기 위해 필요한 모든 확인의 수를 Work라고 정의하겠습니다.

이전 페이지와 같은 변수들을 사용합니다.

Hash Table에서 Ideal Distribution은 Uniform Distribution입니다.

Uniform Distribution의 Work를 Ideal Work(IW)라고 정의하겠습니다.

그리고 이러한 이상적인 table이 F개의 bins만 사용한다고 가정하면 IW는 다음과 같습니다.

double c = k / f  // f개의 bins에 각각 분배될 data 수
double IW = f * (c * (c + 1) / 2) // 사용하는 bins의 개수 * 각 bins마다 기대되는 work

Test할 Hash Function으로부터 만들어진 Distribution의 Work를 Real Work(RW)라고 정의하겠습니다.

double RW = 0;
for (int i = 0 ; i < N; i++) {
    RW += (bin[i] * (bin[i] + 1)) / 2 // bin[i]는 i번째 bin에 들어있는 data의 수
}

그런데 이 계산을 수식으로 나타내보면

Σ bi * (bi + 1) / 2 = (Σ bi^2 + Σ bi) / 2

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

그런데 Σ bi = k 로 표현할 수 있기 때문에(모든 bin에 들어있는 data의 수는 전체 key의 개수와 같음)

RW = (Σ bi^2) / 2 + (k / 2) 로 표현할 수 있습니다.

주어진 k개의 key들에 대해서 Real Distribution과 f개의 bin을 사용하는 Ideal Distribution의 Work가 같다고 가정해보겠습니다.

(Σ bi^2) / 2 + (k / 2) = f * (k/f)((k/f) + 1)/2
=> (Σ bi^2) + k = k * k / f + k
=> (Σ bi^2) = k * k / f
=> f = k * k / (Σ bi^2)

이와 같이 f를 유도할 수 있습니다.

그리고 r은 bins들의 root-square-mean이기 때문에

r = ( (b1^2 + b2^2 + ... + bn^2) / n )^(1/2)
n * r * r = b1^2 + b2^2 + ... + bn^2

이므로 f = k * k / (n * r * r) 으로 표현할 수 있습니다.

double f = (k*k - 1) / (n*r*r - k); // smhasher's f
double f = k * k / (n * r * r); // my f

이번 프로젝트에서는 유도 과정을 이해한 두 번째 f를 이용하여 FillFactor를 계산하겠습니다.