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

해시 테이블이란?

해시 테이블은 (Key, Value)식으로 데이터를 저장하는 자료구조 중 하나로 key를 통해 평균 O(1)에 value를 검색할 수 있는 자료구조이다.

 

참고)

 

[자료구조] 해시 테이블(Hash Table) 이란? | 해시 알고리즘 | 해시 함수

 

 

해시 테이블의 크기를 소수로 정하는 이유

 

public int hashCode() {
     final int prime = 31;
     //...
}

 

Java에서 hashCode() 함수를 살펴보면 size가 31로 소수인 것을 확인할 수 있다. 이와 비슷하게 해시 테이블의 사이즈는 소수(prime number)인 경우가 많다. 해시 테이블의 크기가 소수여야 하는 이유가 뭘까?

 

해시 테이블의 크기에 소수를 사용하는 것은 전통적이다

일반적으로 해시 함수는  key값에서 정수 값을 계산한다. 이때 해시 테이블의 길이를 벗어나지 않기 위해서 테이블 길이를 모듈러(modulo) 연산하는 경우가 많다. 따라서 해시 함수의 결과 값은 0~length-1까지이다.

 

예를 들어 해시 테이블의 크기가 6이라고 해보자. 이때 특정 해시 함수를 사용했을 때 2의 배수를 반환한다고 하면, 해시 테이블의 값은 (해시 함수의 반환 값 % 6)에 들어간다. 따라서 아래와 같이 값들이 들어간다.

 

0	1	2	3	4	5
		2		4
6		8		10
12		14		16
...

 

물론 2의 배수를 반환하는 해시 함수 자체도 비효율적인 해시 함수지만, 어쨌든 매우 불균등하게 값이 들어가는 것을 확인할 수 있다. 

 

하지만 테이블의 크기를 소수인 5로 설정한다면 어떨까? 해시 테이블의 값들은 (해시 함수의 반환 값 % 5)에 들어간다.

 

0	1	2	3	4
	6	2	8	4
10	16	12	18	14
20	26	22	28	24
...

 

거의 모든 곳에 값이 균등하게 들어가는 것을 확인할 수 있다. 

 

수학적으로 생각해 봤을 때 소수는 1과 자기 자신으로 밖에 나누어지지 않기 때문에, 소수는 1과 자기 자신을 제외한 수의 배수가 될 수 없다. 따라서 모듈러 연산을 했을 때 배수가 나오게 되는 경우가 발생하지 않는다.

 

이처럼 소수를 사용하면 전통적으로 모든 버켓을 고르게 사용할 수 있는 가능성이 높아지게 된다. 따라서 해시 충돌의 가능성도 줄일 수 있다.

 

 

hashCode()에서 31을 사용하는 이유

자바에서 hashCode() 값에 31을 선택하는 이유는 31이 2^5보다 1이 작기 때문이다. 

 

31과 곱셈을 해야 할 때 곱셈을 아래와 같이 시프트(shift) 연산과 빼기로 대체할 수 있다.

 

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

 

일반적으로 곱셈 연산보다 시프트 연산과 뺄셈이 더 빠르기 때문에 이는 효율적이다. 

 

 

그럼 꼭 소수를 사용해야 할까?

 

해시 테이블의 크기나 hashCode()에서 소수를 사용하는 것은 위와 같은 이유가 있지만 꼭 소수를 사용해야 하는 것은 아니다. 소수를 사용하면 많은 이점이 있지만 그것을 강제할 필요는 없다. 합성수를 이용하거나 좋은 해시 함수를 사용하는 방법도 있기 때문이다. 

 

소수를 사용하는 것은 전통적으로 소수를 사용하는 면이 더 크다고 볼 수 있다.

 

 

 

 

---

참고

 

1. https://medium.com/swlh/why-should-the-length-of-your-hash-table-be-a-prime-number-760ec65a75d1