equals를 재정의하려거든 hashCode도 재정의하라!
앞에서 equals를 재정의했다. 이제 대부분의 Collection에서 내가 새로 만든 클래스를 잘 사용할 수 있다. 문제는 '대부분'이라는 것이다. 전부가 아니라!
HashMap을 떠올려 보자. 이 친구는 값을 어떻게 삽입하고, 삭제하고, 탐색할까? 바로 해시다. 그런데 우리는 equals만 재정의 했기 때문에 equals로 같은 인스턴스라 할 지라도 hashCode 상에선 다른 인스턴스로 취급 될 수 있다! (사실 Object에서 정의된 hashCode를 보면 물리적으로 다른 객체는 모두 hashCode도 다르다.)
기본적인 규약
Object 명세의 규약을 잠시 살펴보자.
- equals 비교에 사용되는 정보가 변경되지 않았다면, 애플리케이션이 실행되는 동안 그 객체의 hashCode 메소드는 몇 번을 호출해도 일관되게 항상 같은 값을 반환해야 한다. 단, 애플리케이션을 다시 실행한다면 이 값이 달라져도 상관 없다.
- equals(Object)가 두 객체를 같다고 판단했다면, 두 객체의 hashCode는 똑같은 값을 반환해야 한다.
- equals(Object)가 두 객체를 다르다고 판단했더라도, 두 객체의 hashCode가 서로 다른 값을 반환할 필요는 없다. 단 다른 객체에 대해서는 다른 값을 반환해야 해시테이블의 성능이 좋아진다.
HashMap과 연관지어서 생각해보면 다 말이 되는 소리다. 처음이야 애플리케이션 실행 중 값이 변경된다면 HashMap에 넣은 데이터를 아예 찾을 수 없을 것이고, 두번째도 마찬가지다. 물론 해시는 해시충돌이 있기 때문에 원래도 자연적으로 다른 객체에 대해 hashCode 값이 같아질 수 있다. 물론 이런 Collusion을 피해야 성능이 올라갈 것은 확실하지만.
다음 예시는 세 가지를 모두 충족한다. 그래서 이게 좋아보이나?
@Override public int hashCode() { return 1; }뭘까... 어쨌든 일관된 값이 나오고, 같은 객체는 같은 결과가 나오고, 다른 객체여도 hashCode 값이 다를 필요는 없으니 만족이네? 그렇지만 이러면 성능이 기어간다...
자료구조 수업을 열심히 들었다면 알겠지만, 해시 충돌의 경우 다양한 처리 방법이 있는데, 어떤 방법을 써도 충돌이 잦으면 시간이 비효율적이 된다는 것은 모두 알 것이다. (참고로 자바의 경우 Linked List 처럼 동작하는 방식을 사용한다. 즉 O(n)!)
hashCode의 리턴값이 int인 만큼, 최대한 값을 int 범위 내에서 넓게 분포시켜야 이상적인 해시 함수가 될 것이다.
hashCode 잘 Override 하기
조금만 검색해보면 다양한 hashCode Override 방식을 소개하고 있고, 사실 IDE에서 자동 생성도 해준다. 그래도 직접 활용해볼 줄 아는게 좋으니, 책에서 소개하는 방법을 알아보자.
- result 변수를 선언하고 c로 초기화한다. c는 해당 객체의 핵심 필드 (equals 재정의할 때 사용했던 필드! 만약 사용하지 않거나 사용하지 않았던걸 가져다 쓸 경우 위에서 소개한 원칙을 무시하는 꼴이 된다!) 이다.
- 나머지 핵심 필드 f에 대해...
- 해당 필드의 해시코드 c를 계산하고, result = 31 * result + c;로 계속 갱신해준다.
- 이때, f가 기본 타입 필드라면 Wrapper Class에 존재하는 hashCode를 수행한다.
- 참조 타입 필드이면서 이 클래스의 equals 메소드가 이 필드의 equals를 재귀적으로 호출한다면, hashCode 또한 재귀적으로 호출한다. (필드의 값이 null인지 체크하고, null이면 0을 던져주면 좋다.)
- 필드가 배열이라면 원소 각각을 별도 필드처럼 다루고 각각을 재귀처럼 구한다. 다만 배열에 아무 원소도 없다면 0을 쓰고, 모든 원소가 전부 핵심 원소라면 그냥 Arrays.hashCode를 사용한다.
음 좋다. 근데 왜 31을 쓸까? 이유는 소수면서 홀수이고, (즉 2같은 소수가 아니고) 시프트 연산과 뺄셈으로 최적화하기 쉽기 때문이다. (31 * i는 (i << 5) - 1 로 최적화 가능하다.)
근데 이걸로 만족해야 할까? 대체 왜 짝수는 쓰면 안되고, 왜 합성수는 쓰면 안되는걸까??
31, 넌 뭐냐?
짝수는 결국 비트 Shift이다. 즉 가장 오른쪽 값이 무조건 0으로 기록되게 되므로 동일한 범위의 숫자라 해도 사용하지 않는 숫자가 많아지기 때문에 피해야 한다.
문제는 왜 소수여야 하는가? 이다.
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;
}String은 내부 hashCode 연산을 수행할 때, 해당 문자열이 Latin 문자열인지에 따라 StringLatin1.hashCode() 또는 StringUTF16.hashCode() 중 하나를 실행하는데, 결과적으로 계산 과정은 유사하다.
이 부분에 대해, 이펙티브 자바에는 다음과 같은 말이 적혀있다.
곱할 숫자를 31로 정한 이유는 31이 홀수이면서 소수이기 때문이다.
그럼 왜 짝수면 안되고, 합성수면 안 될까?
숫자를 비트로 바꾸면, 짝수를 곱하는 것은 Shift 연산과 동일하다. 즉, 맨 우측 숫자는 반드시 0으로 고정되게 되고, 이는 잠재적으로 가능한 숫자 범위에서 절반을 그냥 날려먹는 것과 동일한 결과를 낸다. 따라서 충돌 가능성이 높아질 수 밖에 없다.
그럼 합성수는 왜 안 될까? 사실 결론만 말하면 상관 없다! 다만 이전부터 소수를 사용하려는 '경향'이 있기 때문에 (이른바 편견이다!. 실제로는 성능 차이는 거의 없지만 홀수에서 최적화를 하려면 소수를 사용해야 한다는 신념 같은 것....) 사용하려고 한다. 여기를 보면, 다음과 같은 내용이 있다.
First, the superstition: People who write code having to do with hash tables apparently recall that prime numbers are particularly "good" for them. It seems they don't always remember just what the "goodness" was or in what connection, but they'll throw prime numbers into the mix whenever they can.
결국 소수를 사용하는 것은 일종의 신념 같은 거라고 이해하면 될 것이다.
음.... 소수도 그렇고 짝수도 그렇고 좀 이해할 것 같은데, 그럼 왜 31일까? 결론만 말하면 이전 어셈블러에서 최적화가 되기 때문이다! 어찌보면 이것도 옛날 관행을 따르다 보니 이렇게 된 기분...
RSB r1, r0, r0, ASL #5 ; r1 := - r0 + (r0<<5) 이런 식으로 표현되는데, 이는 일반적인 연산과 비교해서 횟수가 적기 때문에 시간이 적게 소모된다.
다만 이것도 옛 말이다. 요즘은 컴파일러 최적화가 잘 되어서 31을 곱하는 것 보다 다른 소수를 곱하는게 더 빠른 경우도 있다! 하지만 충분히 무시할 수 있는 성능인 만큼 그냥 31 쓰는게 마음이 편할 것아이다.. (사실 31을 곱하는 것 이외에도 다양한 라이브러리에는 수많은 방법을 소개하고 있다. 심지어 Lombok 어노테이션도 다른 소수를 쓰고 있다!)
마지막으로, 명저 중 하나인 Introduction to Algorithm 3rd Edition (Thomas H. Cormen 외) 에는 다음과 같이 적혀 있다.
As Exercise 11.3-3 asks you to show, choosing m D 2p | 1 when k is a character string interpreted in radix 2p may be a poor choice, because permuting the characters of k does not change its hash value. A prime not too close to an exact power of 2 is often a good choice for m.
여기를 따라 가면 오히려 31은 좋지 않은 수다. 흠... 역시 해시는 다양한 방법이 있는 것 같다.
추가 유의사항
Object.hash
Object는 임의의 개수만큼 객체를 받아 해시코드를 계산해주는 메소드를 제공하는데, 이는 갯수를 판단해 배열을 생성하고, 기본 타입에 대한 박싱과 언박싱이 발생하므로 성능 측면에선 조금 아쉽다. hashCode를 길게 오버라이딩 하기 싫고, 성능 측면에서 민감하지 않다면 활용해보자.
비용 아끼기
만약 클래스가 불변임이 분명하면? 굳이 hashCode를 호출할 때 마다 일일히 만들 필요 없이 캐싱하는 방식이 괜찮을 것이다. 특히 클래스가 불변인데 hashCode도 자주 사용하지 않다면 처음 호출될 때 계산하는 지연 초기화 (Lazy Initialization) 방식으로 접근하는 것도 괜찮을 것이다.
다만 비용 아끼겠다고 핵심 필드를 생략해서는 안된다! 이전 자바의 경우 String의 hashCode를 구하기 위해 앞 16글자만 활용했는데, "https://www...." 으로 구성된 URL 집합이라면 어쩌려고 그러는 건지... 아무튼 이런 경우엔 충돌 가능성이 높아지고, 비용 아끼려다가 오히려 비용이 급격하게 올라갈 수 있다.
의존성 회피
hashCode의 생성규칙을 알려주지 말자. API 사용자가 코드를 hashCode 생성과정에 맞춰 종속되게 짠다면 문제가 생길 수 있다. 만약 hashCode에 대해 수정할 일이 생겼는데 이미 다른 코드가 종속되어 있다면? 레거시 문제 때문에라도 변경할 수 없는 상황이 올 것이다.