[Effective Java] 아이템11. equals를 재정의한다면 hashCode도 재정의하라

 

1. HashCode 일반규약(Object)

- hashCode: 주소값을 기반으로 생성된 정수 값.

- 참고 자료: https://preamtree.tistory.com/20

[IT 기술면접 준비자료] 해시(Hash)와 해시충돌(Hash Collision)

 

1. equals 비교에 사용되는 정보가 변경되지 않았다면, 애플리케이션이 실행되는 동안 그 객체의 hashCode 메서드는 몇 번을 호출해도 일관되게 항상 같은 값을 반환해야 한다. (단, 애플리케이션을 다시 실행한다면 이 값이 달라져도 상관없다.)

2. equals(Object)가 두 객체를 같다고 판단했다면, 두 객체의 hashCode는 똑같은 값을 반환해야 한다.

3. equals(Object)가 두 객체를 다르다고 판단했더라고, 두 객체의 hashCode가 서로 다른 값을 반환할 필요는 없다.

단, 다른 객체에 대해서는 다른 값을 반환해야 해시테이블 성능이 좋아진다.

 

 

 

2. 일반규약을 지키지 못했을 때

equals를 재정의하여 사용하고, hashCode를 재정의하지 않으면, hashcode 일반규약을 깨게 된다.

-> 이는 해당 클래스의 인스턴스를 컬렉션(HashSet, HashMap)의 원소로 사용할 때 문제가 된다. (아래 예시)

 

 

 

[예시] equals를 재정의, hashCode는 그대로 사용했을 때 문제상황

Map<PhoneNumber, String> m = new HashMap<>();

m.put(new PhoneNumber(707, 867, 5309), "제니");
m.get(new PhoneNumber(707, 867, 5309), "제니"); // "제니"가 나와야할 것 같지만 null이 나옴

put에 넣은 객체와 get에서 사용한 객체가 논리적으로 동치인 상황이지만,

 

hashCode가 다르기 때문에 객체를 찾지 못한다. (1. HashCode 일반규약 2번 위배)

 

 

3. hashCode 구현

 

[BAD] 1. 인스턴스에 상수를 넣어 항상 같은 값을 반환하도록 한다.

@Override public int hashCode(){return 42;} // 임의의 숫자를 넣어 같은 값을 반환하도록 한다.

최악의 방법으로 따라해서도 안된다!!!!

왜냐하면 해시테이블 성능(O(1))을 낮추게 되기 때문이다!!

모든 인스턴스가 같은 해시값을 반환하므로, 똑같은 해시테이블 버킷에 담기게 되어 연결리스트 처럼 동작한다.

때문에 평균 수행시간이 O(1)인 해시테이블이 O(n)으로 느려진다.

 

 

[GOOD] 2. 서로 다른 인스턴스들을 32비트 정수 범위에 균일하게 분배 (을 비슷하게 구현한 전통적인 기법을 활용)

가장 이상적인 방법으로 실현하기 어렵지만 아래와 같이 비슷하게는 만들 수 있다!

*핵심 필드: equals에서 사용되는 필드들

 

1. int 변수 result를 선언한 후 값 c로 초기화한다. 이 때 c는 해당 객체의 첫번째 핵심 필드를 단계 2.a 방식으로 계산한 hashCode이다.
2. 해당 객체의 나머지 핵심 필드 f 각각에 대해 다음 작업을 수행한다.     a. 해당 필드의 해시 코드 c를 계산한다	1) 기본 타입 필드라면: Type.HashCode(f)를 수행한다. (Type: 해당 기본 타입의 박싱 클래스)
	2) 참조 타입 필드 && 이 필드의 equals를 재귀적으로 호출해 비교한다면: 이 필드의 hashCode를 재귀적으로 호출한다.                 - 계산이 더 복잡해질 것 같으면, 이 필드의 표준형을 만들어서 그 표준형의 hashCode를 호출하도록 한다.                 - 필드 값이 null이라면 0을 사용한다. (MUST는 아니다. 다른 상수도 괜찮지만 전통적으로 0을 사용함)
	3) 필드가 배열이라면: 핵심 원소 각각을 별도의 필드처럼 다룬다.                 - 재귀적으로 핵심 원소의 해시코드를 계산한 다음, 2.b 방식으로 갱신한다.                 - 배열에 핵심 원소가 없다면 상수(0을 추천)를 사용한다.                 - 반대로 모든 원소가 핵심 원소라면 Arrays.hashCode를 사용한다.
2. 해당 객체의 나머지 핵심 필드 f 각각에 대해 다음 작업을 수행한다.     b. 단계 2.a에서 계산한 해시코드 c로 result를 갱신한다.	result = 31 * result + c;
3. result를 반환한다.

 

 

[유의사항]

- 파생필드는 해시코드 계산에서 제외해도 된다. (파생필드: 다른 필드로부터 계산해낼 수 있는 필드)

- equals비교에 사용되지 않은 필드는 반드시 제외해야 한다.  (추가하게 되면 규약2를 위배하게 됨)

 

[2.b 해석]

- 31을 곱하는 이유는 소수이면서 홀수이기 때문이다. 짝수는 스택오버플로우를 발생시킬 수 있고, 발생한다면 정보를 잃게 된다. 

- 만약 곱셈이 없다면 String의 hashCode를 구현할 때 애너그램이 같다면 같은 해시코드를 반환하게 된다. (ex: abc, acb, bca, ... 같은 해시코드를 반환)

 

- 숫자를 곱하는 것은 시프트 연산과 같은 결과를 내기 때문이다. 

결과적으로 31을  이용하면, 이 곱셈을 시프트 연산과 뺄셈으로 대체해 최적화할 수 있다.

(31*i 는 i << 5 - 5와 같다.)

 

[예시]

@Ovveride public int hashCode(){
	int result = Short.hashCode(areaCode);
    result = 31 * result + Short.hashCode(prefix);
    result = 31 * result + Short.hashCode(lineNum);
   	return result;
}

 

[GOOD] 3. Objects 클래스의 hash() 메서드 활용

임의의 개수만큼 객체를 받아 해시코드를 계산해주는 적적 메서드.

장점) hashCode를 단 한 줄로 작성할 수 있다.

단점) 속도는 2)보다 더 느리다. (입력 인수를 담기 위한 배열이 만들어지고, 입력 중 기본 타입이 있다면 박싱과 언박싱도 거쳐야 하기 때문이다.) 

 

@Override public int hashCode(){
    return Objects.hash(lineNum, prefix, areaCode);
}

 

4. 지연 초기화(lazy initialization)

클래스가 불변이고 해시코드를 계산하는 비용이 크다면, 매번 새로 생성하는 방법은 적절하지 않다.

특히 이 타입의 객체가 주로 해시의 키로 사용될 것 같다면 인스터스가 만들어질 때 해시코드를 계산해둬야 한다. 

해시 키로 사용되지 않는 경우라면, hashCode가 처음 불릴 때 계산하는 지연 초기화(lazy initialization) 전략도 있다. 

 

private int hashCode; // 0

@Override public int hashCode(){
    int result = hashCode;
    if(result == 0){
        result = Short.hashCode(areaCode);
        result = 31*result + SHort.hashCode(prefix);
        result = 31*result + Shrot.hashCode(lineNum);
        hashCode = result;
    }
    return result;
}