java.lang.String 의 hashCode 구현에 대해 고찰해 봅시다. 왜 그런 구현일지, 문제점은 없을지 이야기해주세요.
String 클래스는 아래와 같이 모든 문자에 대한 해시 함수를 계산하는 게 아니였다.
skip을 통해 일정 간격의 문자를 건너가면서 해시 함수를 계산했다.
아래 코드를 보면 문자열의 길이가 16을 넘으면 최소 하나의 문자가 건너뛰어지며 해시 함수가 계산된다.
public int hashCode() {
int hash = 0;
int skip = Math.max(1, length() / 8);
for (int i = 0; i < length(): i+= skip)
hash = s[i] + (37 * hash);
return hash;
}이 방식은 심각한 문제를 얘기한다. 웹상의 URL은 앞부분이 동일한 경우가 많은데 서로 다른 URL에 대해서 동일한 해시 값이 나오는 문제가 생겼기 때문이다. HashSet, HashMap과 같이 HashCode를 사용하여 해시 버킷에 데이터를 저장할 때 중복되는 hashCode는 해시 버킷에 데이터를 LinkedList 형식으로 연결해서 저장하기 때문에 hashCode가 중복될 수록 성능에 영향을 준다.
Java 8에서는 String 클래스의 hashCode 메서드에도 성능 향상을 위해 31을 사용한다. 이 방식은 연산을 빠르게 처리할 수 있다. 31 * N = 32N - N으로서 32는 2^5이니 어떤 수 N에 대해 32를 곱한 값은 시프트연산으로 쉽게 구현할 수 있다. 따라서 N에 31을 곱한 값은 (N << 5) - N이다. 31을 곱하면 이렇게 쉬프트 연산을 통해 빠른 계산이 가능하기 때문에 31을 사용한다.
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}hashCode 자체가 고르게 사용되고 빠른 계산이 가능하더라도
실제 HashMap, HashSet에서의 해시 버킷의 개수 M은 2^a의 형태가 되기 때문에
해시 버킷 index = x.hashCode() % M을 계싼할 때 x.hashCode()의 하위 a개의 비트만 사용하게 된다. 즉, hashCode가 아무리 고르게 분포되도 해시 값을 2의 승수로 나누면 해시 충돌이 발생할 수 있다.
