[Java] 해시함수의 충돌을 피하기 위해 테이블 사이즈를 소수, 홀수로 만들어야 하는 이유

CS공부/자료구조

반달bear 2022. 12. 8. 02:35

해시함수의 충돌을 피하기 위해서는

테이블 크기를 홀수로 만들거나, 소수로 설정하거나, 크기 자체를 늘리는 것이 좋다고 한다.

그런데 강의 해주시는 교수님은 왜 충돌이 발생하는지 설명만 하고 왜 테이블 크기를 늘려야 하는건지는 설명해주지 않으셨다.

그래서 쓰는 글.

해시함수는 key값에서 정수값을 계산하는데

이 때 해시 테이블의 길이를 벗어나지 않기 위해서

테이블 길이로 해시함수의 리턴값을 모듈러(%-나머지값) 연산한다고 한다.

예를 들어 테이블의 크기가 6이고 특정 해시 함수를 사용했을 때 2의 배수를 반환한다면

2, 4, 6, 8, 10 … 가 해시함수에서 반환되는데

이를 해시 테이블 사이즈에 맞게 조정(모듈러 사용)하면

2(2%6), 4(4%6), 0(6%6), 2(8%6), 4(10%4) … 로 변한다

딱봐도 0과 2와 4에 값이 계속 들어가기 때문에 충돌이 발생하기 너무 좋다는 것을 알 수 있다.

그런데 테이블을 소수로 만들면 상대적으로 값이 균등하게 들어간다.

소수는 1과 자기 자신을 제외한 수의 배수가 될 수 밖에 없다.

그래서 배수가 나오는 경우의 수를 최대한 줄이면 충돌을 최대한 방지할 수 있게 되는 것이다.

마찬가지로 짝수보다 홀수로 테이블 사이즈를 설정하면 좋은 이유는

모든 짝수는 최소공약수인 2를 공유하기 때문이다.

2와 4를 놓고 보자면 2와 4의 최대공약수는 4이고

4와 6의 최대 공약수는 2*2*3으로 12이다.

그에 비해 홀수는 최소공약수를 공유하지 않는다.

3과 5를 놓고 보자면 최대공약수가 15

5와 9를 놓고 보자면 최대 공약수가 45이기에

배수의 관점에서 짝수보다 홀수로 설정하는 것이 값이 좀 더 균등하게 들어갈 가능성이 높다.

테이블 사이즈가 클수록 좋은 이유는

애초에 테이블 사이즈가 크다면 모듈러를 사용했을때

<사이즈의 크기-1> 만큼 나머지가 나오기 때문이다.

마지막으로 자바의 해쉬함수의 사이즈는 final size = 31;로 설정되어 있다.

그 이유는 31이 마르센 소수(2^n-1꼴의 소수)이기 때문이라고 한다.

곱셈 연산보다 시프트 연산과 뺄셈이 더 빠르기 때문에

32가 아니라 마르센 소수로 시프트 연산과 마이너스로 표현할 수 있는 31을 사용하는 것이다.

31*i == (i<<5) - i

7이 아닌 이유는 기본 해시맵 사이즈가 16이기 때문이지 않을까 싶다.

+혹시 궁금하신 분들을 위해

해시맵의 기본 버킷 사이즈가 2의 거듭제곱인 16인 이유는 indexFor 메소드 때문이라고 한다.

해시맵의 항목을 배열 어느 위치에 저장할지 결정하는 메소드가 indexFor인데

static int indexFor(int h, int length) {
    return h & (length-1);
}

(이때 h값은 해시함수의 리턴값이다)

버킷 사이즈인 length가 2의 제곱값이 아니라면

return h % length; 이라는 코드를 써야 한다고 한다.

즉 비트연산자인 &보다 %가 더 느리기에 2의 거듭제곱으로 버킷의 크기를 유지하는 것이다.

왜 정확히 16인지는... 잘 모르겠다^^ 하하

참조