Division Hashing

Division Hashing이란 주어진 key를 bin의 개수로 나눠서 생긴 나머지를 bin의 Index로 사용하는 Hashing입니다.

int index = key % M;

bin의 개수가 M개일 때, key % M을 한 결과는 0에서 M - 1까지 생기기 때문에 bin의 Index로 사용할 수 있게 됩니다.

이번 페이지에서는 M의 값에 따라 어떤 점들이 달라지는 지 알아보겠습니다.

Contents

• Multiple of 2
• Power of 2
• Composite Number
• Prime Number

Multiple of 2

M을 2의 배수로 설정한 경우입니다.

key가 홀수라면 index도 홀수로 설정되고, key가 짝수라면 index도 짝수로 설정됩니다.

이것은 Uniform하지 않은 key의 분포가 index에 그대로 반영될 수 있는 상황이기 때문에 적절한 값으로 볼 수 없습니다.

Power of 2

2의 거듭제곱 또한 2의 배수와 같이 결과가 홀수와 짝수로 편향되어 나타납니다.

하지만 나머지를 구하는 과정이 %연산 대신 &연산으로 대신될 수 있다는 특징이 있습니다.

예를 들어 a라는 값을 2^b로 나눈 나머지를 구한다고 가정하겠습니다.

a의 bit들을 오른쪽으로 b칸 옮긴 것은 a / 2^b의 몫입니다. 이 값을 q라고 부르겠습니다.

그렇다면 나머지는 a - q * 2^b 입니다.

좀 더 쉽게 보면

x x x x ... x x | y y y y ... y y

위의 기호들이 나타내는 값을 a라고 보겠습니다. 그리고 | 는 2^b로 나눴을 때 남아있는 bit들을 구별한 것입니다.

즉 위의 값을 2^b로 나눴을 때 0 0 0 0 ... 0 0 | x x x x ... x x 와 같이 x로 표기된 bit들만 남게 되고 이 값이 q입니다.

이 때 2^b를 표현해보면 0 0 0 0 ... 0 1 | 0 0 0 0 ... 0 0 와 같이 표현되는 것을 알 수 있습니다.

그렇다면 q * 2^b는 x x x x ... x x | 0 0 0 0 ... 0 0 이고,

결국 a - q * 2^b은 0 0 0 0 ... 0 0 | y y y y ... y y 이므로

a % 2^b은 a의 0번째 bit부터 b - 1번째 bit까지의 bit들을 2^b - 1과 AND연산한 결과인 것을 알 수 있습니다.

이러한 성질을 이용하여 2의 거듭제곱은 % 연산보다 빠른 & 연산을 통해 나머지를 구할 수 있다는 특징을 가지게 됩니다.

key의 분포가 이미 Uniform하다면 bin의 개수를 2의 거듭제곱으로 하는 것이 더 나은 선택이라고 생각할 수 있습니다.

Composite Number

Composite Number란 Prime Number에 반대되는 용어로 소인수분해가 가능한 수를 의미합니다.

이 값을 M으로 설정할 경우 M의 소인수들에 대해서 편향된 결과가 나올 수 있습니다.

예를 들어 M이 15인 경우 15의 소인수인 3, 5의 배수들에 대해서 한정된 index들만 나타나게 됩니다.

3의 배수의 경우 0, 3, 6, 9, 12 index만 사용하게 되고, 5의 배수의 경우 0, 5, 15 index만 사용하게 됩니다.

3의 배수와 5의 배수가 아닌 경우 0 ~ 14까지의 index 모두를 사용하게 됩니다.

즉 key가 소인수의 배수에 대해서 다른 수들과 구별되는 특징을 가진다면 index 또한 편향된 결과가 나오게 됩니다.

Prime Number

Prime Number는 소인수분해한 결과가 1과 자기 자신만 남는 수를 의미합니다.

이 경우 Composite Number처럼 특정 수의 집단에 대해서 한정된 index만 도출되는 상황이 발생하지 않습니다.

그렇기 때문에 일반적인 Division Hashing은 M을 Prime Number로 설정하는 것이 좋은 선택이 될 것입니다.