Fibonacci Hashing

Fibonacci Hashing은 Multiplicative Hashing을 사용할 때 어떤 상수를 사용할 것인지에 대한 질문에서 시작됩니다.

이번 페이지에서는 Fibonacci라는 개념이 Multiplicative Hashing과 어떤 연관이 있는 지 알아보겠습니다.

Contents

• The three distance theorem
• Bad Break
• Fibonacci ratio
• Constant
• Sequential data

The three distance theorem

{x} = x - |_x_| 이고, θ를 irrational number라고 가정하겠습니다.   

만약 0에서 시작하고 1에서 끝나는 선분 위에 각각 {θ}, {2θ}, ... , {nθ} 의 길이를 가지는 점들이 존재한다면

현재 이 선분 위에는 n + 1개의 선분들이 형성되어있는 상황입니다.

The three distance theorem에 따르면 이러한 n + 1개의 선분들은 최대 3개의 서로 다른 길이로 구성됩니다.

또한 {(n + 1)θ}에 해당하는 점은 현재까지 만들어진 가장 긴 선분 중 하나에 찍히게 됩니다.

θ와 n에 따라 어떤 방식으로 선분이 변화하는 지는 Wolfram에서 확인할 수 있습니다.

Bad Break

The three distance theorem의 성질에는 새로운 점이 기존의 선분 중 가장 긴 것을 나눈다는 것이 있습니다.

The Art of Computer Programming, vol. 3 by Donald Knuth는 이렇게 나뉘어진 선분에 대해서

한 쪽이 다른 쪽보다 2배 이상 큰 상황을 Bad Break이라 정의했습니다.

예를 들어 θ가 0.9999...라고 가정해본다면 한 쪽은 다른 쪽에 비해 매우 작은 크기를 가지게 됩니다.

이러한 상황에서는 새롭게 추가되는 점들이 0에서 1 사이에 무작위하게 위치하지 않고, 한쪽 끝에 몰려서 나타나게 됩니다.

Fibonacci ratio

Fibonacci ratio는 (√5 - 1) / 2 로 대략 0.6180339887... 이라는 값을 나타냅니다.

θ를 Fibonacci ratio로 설정할 경우 Bad Break가 발생하지 않는 다는 특징이 있습니다.

즉 새로운 점들이 0과 1 어느 한쪽에 편향되어 나타나지 않고, 무작위하게 나타납니다.

Constant

그렇다면 이러한 비율들이 Constant와 어떤 연관이 있을까요?

Multiplicative Hashing을 나타내는 수식을 다시 적어보면

h(k) = |_ M * ( (A / w) * K mod 1 ) _|  // ex) |_ x _| : x보다 크지 않은 정수, A mod B : A를 B로 나눈 나머지

이와 같이 나타낼 수 있습니다.

여기서 (A / w)를 θ로 생각해본다면 (A / w) * K mod 1은 {Kθ}로 표현할 수 있습니다.

즉 key에 따라서 변화하는 (A / w) * K mod 1의 움직임은 Wolfram에서 확인했던 점들의 움직임으로 생각할 수 있습니다.

예를 들어 A를 w * Fibonacci ratio 라고 생각한다면 (A / w) * K mod 1 은 0과 1 사이에서 Random하게 결정된다고 볼 수 있습니다.

반대로 (A / w)를 Bad Break가 크게 발생하는 값으로 생각한다면 (A / w) * K mod 1 은 0 혹은 1 쪽에 편향될 것입니다.

이것은 hash code가 좁은 구간에서 높은 빈도로 발생한다는 것을 의미합니다.

Sequential data

일반적으로 Multiplicative Hashing에서 A를 Fibonacci ratio에 따라 결정하면 충분히 Random한 결과를 얻을 수 있습니다.

하지만 만약 주어진 key들이 일정한 패턴을 가진다면 어떻게 될까요?

예를 들어 key들 간에 간격이 1이 아니라 100이라면 선분에 찍히는 점들을

{kθ}, {(k + 100)θ}, {(k + 200)θ} ... 이렇게 생각할 수 있습니다.

그런데 Fibonacci ratio는 0.61803398...이고, 여기에 100을 곱한다면 0.803398...임을 알 수 있습니다.

즉 이처럼 100단위로 변하는 key set은 0.803398...이라는 큰 값에 의해 상수가 결정되고, 이는 Bad Break가 커진 상황입니다.

또 다른 예로 1000000단위로 변한다면 0.9887...이라는 큰 값에 의해 상수가 결정됩니다.

그래서 위와 같은 key set에 대해서도 Random한 결과를 유지하기 위해 Fibonacci ratio를 그대로 쓰지 않고

0.6161... 과 같이 어떤 패턴이 있더라도 Bad Break가 심해지지 않는 값을 쓰고자 합니다.

그런데 0.6161... 과 같은 값을 사용하면 ABCD, CDAB와 같이 순서만 바뀐 key들에 대해서 같은 결과가 나온다는 특징이 있습니다.

그렇기 때문에 Fibonacci ratio만큼은 아니지만 적절하게 Bad Break를 피할 수 있는 값들로 책에서는 다음과 같은 값들이 소개되었습니다.

1/4 < θ < 3/10,    1/3 < θ < 3/7,    4/7 < θ < 2/3,    7/10 < θ < 3/4

ratio의 각 자리를 위의 4개의 구역에서 골고루 뽑아서 A를 결정합니다.

예를 들어 0.61 25 42 33 71 .. 과 같이 각 구역에서 골고루 값을 뽑은 후 w * 0.6125423371... = A로 결정합니다.