해시 테이블의 버켓 크기를 소수로 잡아야 하는 이유

수학적으로 설명하진 않도록 하겠습니다.

왜냐면 모르기 때문입니다.

버켓의 크기를 소수가 아닌 수로 적당히 잡아 봅시다. 대충 6이 좋겠군요.

0	1	2	3	4	5

그리고 어떤 해시 함수를 하나 가정해 보겠습니다.

이 해시 함수는 어떤 입력이 들어왔는지 상관하지 않고 0~11 까지의 수를 차례대로 반환합니다.

반환 값은 차례대로 0, 1, 2, 3, 4… 가 됩니다.

이 반환 값을 토대로 어떤 버켓에 값을 넣을지 결정하겠습니다. 0에서 5까지는 넣어보면 다음과 같이 넣을 수 있습니다.

0	1	2	3	4	5
0	1	2	3	4	5

이제 6에서 부터 11 까지의 수를 넣어야 하는데 버켓의 크기와 1대 1로 맞지 않습니다. 따라서 나머지 연산의 결과를 통해 어떤 버켓에 값을 넣을지 결정합니다.

해시 함수의 반환 값 % 버켓의 크기 = 넣어야 할 버켓

마저 넣어보면

0	1	2	3	4	5
0	1	2	3	4	5
6	7	8	9	10	11

최종적인 해시 테이블은 위와 같이 구성될 겁니다.

그런데 말입니다. 다른 해시 함수를 생각해 보도록 하겠습니다.

이 해시 함수는 0에서 22까지의 2의 배수를 차례대로 반환합니다.

반환 값은 차례대로 0, 2, 4, 6, 8… 가 됩니다.

버켓에 넣어보면

0	1	2	3	4	5
0		2		4
6		8		10
12		14		16
18		20		22

이전과는 다르게 사용되지 않는 버켓이 보입니다. 전체 버켓의 50%밖에 사용하지 못하는 것입니다.

이번에는 소수로 버켓 크기를 잡아 봅시다. 6보다 작은 소수인 5로 하겠습니다.

0	1	2	3	4
0	6	2	8	4
10	16	12	18	14
20		22

소수가 아닌 수로 버켓의 크기를 잡았을 때와 다르게 모든 버켓을 고르게 사용하고 있는 것을 살펴볼 수 있습니다.

이전과 비교했을 때 버켓 크기가 작음에도 충돌 횟수는 적습니다.

소수가 아닌 수로 버켓의 크기를 잡았을 때는 해시 함수의 반환 결과가 편향되어 있으면 해시 충돌이 발생할 가능성이 더 높습니다. 따라서 버켓의 크기를 소수로 잡아야 합니다.

해시 테이블의 크기를 2의 거듭제곱으로 잡지 말아야 하는 이유

여기서는 비트의 세계로 돌아가 볼 필요가 있습니다.

우선 적당한 2의 거듭제곱인 테이블 크기를 정하겠습니다. 8로 할까요.

비트로 표현하면 다음과 같습니다.

6	5	4	3	2	1	0
0	0	0	1	0	0	0

해시 함수가 2를 반환 했다고 생각해 봅시다. 들어가야 할 버켓은 2 mod 8로 2가 됩니다.

비트로 표현하면 다음과 같겠죠.

6	5	4	3	2	1	0
0	0	0	0	0	1	0

그 다음으로 18을 반환했다고 생각해 봅시다. 들어가야 할 버켓은 18 mod 8로 2가 됩니다.

다음은 34를 반환했다고 생각해볼까요? 마찬가지로 들어가야 할 버켓은 2입니다.

그럼 58은 어떤가요? 2입니다.

2 가 되는 수만 뽑은 게 아니냐? 맞습니다. 하지만 그 외에도 이 값들에는 공통점이 있습니다.

18, 34, 58을 차례대로 비트로 표현해 보겠습니다.

• 18

6	5	4	3	2	1	0
0	0	1	0	0	1	0

• 34

6	5	4	3	2	1	0
0	1	0	0	0	1	0

• 58

6	5	4	3	2	1	0
0	1	1	1	0	1	0

이 수들의 공통점이 보이시나요?

공통점은 바로 3번째 비트 이상의 비트만 변경됐다는 것입니다.

2의 거듭제곱으로 하는 나머지 연산은 아주 단순하게 변하게 됩니다.

8은 3번째 비트만 1인 값이지요? 8로 하는 나머지 연산의 경우에 3번쨰 비트 이상의 비트가 어떤 값이 됐던 아래의 2비트의 값으로 결정되게 됩니다.

즉 6비트 중에 2 비트만 버켓을 결정하는데 영향을 줍니다. 따라서 2의 거듭제곱 값으로 해시 테이블의 크기를 결정하는 것은 좋지 않습니다.