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

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

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

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

그래서 쓰는 글.

해시함수는 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인지는... 잘 모르겠다^^ 하하

 

 

 

 

참조

java - Why do we use number 31 while calculating hashcode - Stack Overflow

해시 테이블의 크기를 소수로 정하는 이유, hashCode() 에서 31을 쓰는 이유 (tistory.com)

java - Why does HashMap require that the initial capacity be a power of two? - Stack Overflow