Java, Kotlin 등에서 쓰이는 hashCode() function은 hash function을 구현한 것이다.
이 글은 hashCode()의 쓰임새 보다는 java, kotlin에 구현된 hashCode() function은 왜, 31 이라는 숫자를 이용해 hashCode()를 만드는 것일까 에 대한 의문을 해결하기 위한 글이다.
왜? 왜? 대부분의 hashCode() function은 31이라는 숫자를 곱해 hashCode 값을 생성하고 있는 걸까?
인터넷을 찾아보니, 31이 많이 쓰이는 이유는 크게 아래 3가지가 나오더라.
- 홀수이다
- 소수이다
- '곱하기 31'은 shift 연산과 뺄셈 연산으로 표현이 가능하다
하나씩 그 이유를 살펴보자.
31은 홀수이다
요약: 곱하는 수가 홀수이면, hash 충돌을 최소화할 수 있다.
어떤 숫자에 짝수를 곱하게 되면, 최하위에 있는 비트부터 서서히 0으로 채워지게 된다. 그렇게 되면 아래 두가지 현상을 만나게 된다.
1. hashCode로 쓰일 수 있는 숫자의 가지수가 줄어든다.
이 말은 즉, hashCode로 쓰일 수 있는 숫자의 가지수가 줄어든다는 얘기이고 궁극적으로 hashCode의 충돌이 빈번해질 수 밖에 없다.
2. overflow 발생 시, 정보의 손실이 커진다.
처음엔 이해가 안됐다. overflow가 발생해서 hashCode 값이 000...000 이 되는 거나, 101...111 이런 값이 되는거나 어차피 정보의 손실 정도는 똑같은거 아닌가? 라는 생각이 들었다(overflow가 난 101...111 은 그냥 숫자의 조합일 분, 무의미한 정보라고 생각했기 때문).
그런데? hashCode라 생각해보면, overflow가 나더라도 그대로 hashCode 만들기를 계속한다고 하면, 짝수를 곱하다가 overflow가 난 경우 모두 그 이후로부터는 모두 000...000 으로 hashCode가 만들어질 것이고, 홀수를 곱하다가 overflow가 난 경우는 그래도 각기 다른 hashCode가 만들어지기 때문에 '정보의 손실이 최소가 된다' 라고 말하는게 아닐까? 라는 생각이 들어서 이렇게 이해하고 넘어가려고 한다.
정보의 손실 최소화 보다는, overflow가 나도 hashCode 값이 다양하게 만들어질 수 있다 정도로 이해하면 좋지 않을까? 하는 생각을 해본다!
31은 소수이다
요약: 사실 소수여서 좋은 점은 없다.
hashCode와 31을 검색하면 많은 곳에서 31이 홀수이면서 소수이기 때문에 사용하고 있다고 말한다. 그런데 사실 31이 소수여서 좋은 점은 없다. 그냥 관용처럼 소수를 사용하는 것 뿐이라고 한다. 그럼 여기서 궁금한 점은, 왜 이런 관용이 생겼을까? 하는 것이다.
내 생각에 이러한 관용이 생긴 이유는 hash table의 크기로 보통 소수를 채택하기 떄문이지 않을까 싶다. Hash table의 크기를 소수로 정하면 hash collision을 최소화 가능하다는 확실한 이점이 있다. 그래, 이럴 때나 소수가 이점이 있지...! java나 kotlin에서 사용하는 hashCode는 hashTable에 그 값을 배치하는 것과는 큰 상관이 없다.
곱하기 31 연산은 shift 연산과 뺄셈 연산으로 대체 가능하다
요약: a * 31 은 더 효율적인 shift, +/- 연산을 사용해서 a << 5 - a 로 대체가 가능하다.
JVM은 홀수의 곱셈을, shift와 +/- 연산으로 바꿔 최적화한다고 한다. 31을 곱하는 연산을, shift 연산과 - 연산으로 대체해 더 효율적으로 hashCode 값을 구할 수 있다.
결국 hashCode를 구할 때 곱하기 31을 사용하는 이유는, 31이 홀수이면서 shift 연산과 뺄셈 연산으로 대체할 수 있기 때문이라고 할 수 있겠다.
이 두가지 조건은 사실 모~든 홀수의 공통점이기 때문에 hashCode를 만들 때 홀수 어떤 걸 써도 무방할 듯 싶다.
참고1. 실제로 Lombok에서 만들어주는 hashCode()는 31이 아니라 59를 사용하고 있다.(참고)
참고2. Java는 hashCode를 만들 때 31을 사용한다.
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
hash = h = isLatin1() ? StringLatin1.hashCode(value)
: StringUTF16.hashCode(value);
}
return h;
}
// StringLatin1.hashCode()
public static int hashCode(byte[] value){
int h = 0;
for (byte v: value){
h = 31 * h + (v & 0xff);
}
return h;
}
// StringUTF16.hashCode()
public static int hashCode(byte[] value){
int h = 0;
int length = value.length >> 1;
for (int i = 0; i < length; i++){
h = 31 * h + getChar(value, i);
}
return h;
}이 외에도, 대부분의 모듈에서는 31을 관용처럼 사용하고 있는 것 같다!
