[ 이펙티브 자바 ] 아이템 11 equals를 재정의하려거든 hashCode도 재정의하라

equals를 재정의한 클래스는 hashCode도 재정의해야한다.
그렇지 않으면 인스턴스를 HashMap이나 HashSet 같은 컬렉션의 원소로 사용할 때 문제가 발생한다.

hashCode 일반 규약

• equals 비교에 사용되는 정보가 변경되지 않았다면, hashCode 도 변하면 안 된다.(애플리케이션을 다시 실행한다면 이 값이 달라져도 상관 없음)
• equals가 두 객체가 같다고 판단했다면, 두 객체의 hashCode는 똑같은 값을 반환한다.→ 논리적으로 같은 객체는 같은 해시코드를 반환해야 한다.
• equals가 두 객체를 다르다고 판단했더라도, hashCode는 꼭 다를 필요는 없다.하지만, 다른 객체에 대해서는 다른 값을 반환해야 해시테이블의 성능이 좋아진다.

HashMap, HashSet과 HashCode

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
 }


static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}


final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) { //hash값으로 인덱스 계산하여 실제 값 가져옴
            if (first.hash == hash && // 찾은 hash값이 맞는지 비교하고 맞다면 equals를 통해 값을 준다.
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) { // 같은 해쉬값이고 equals의 결과가 다른경우 다음노드를 조회
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

내부적으로 HashMap의 get메서드를 보면

들어온 Key 객체를 hashCode를 통해 hash값으로 바꾸고

이 hash값을 인덱스로 쓰는 실제 값을 찾아서 찾은 값과 인자의 해시 값, key 값이 모두 equals를 통해 일치하여야 해당 노드를 반환한다.

Map<PhoneNumber, String> map = new HashMap<>();
map.put(new PhoneNumber(010,1234,5678), new Person("리치"));

map.get(new PhoneNumber(010,1234,5678)) //이 명령어를 실행하면 null반환!!

equals를 재정의하여 논리적으로 같다고 했음에도 hashCode를 재정의하지 않았다면 논리적으로 동일한 두 객체여도 HashMap, HashSet에서의 get 조회가 불가능하다. 왜냐하면 get은 내부적으로 equals, hashCode가 모두 사용되며 두 객체의 equals, hashCode 모두 일치해야 조회가 가능하다. 하지만 현재는 재정의되있지 않아 둘의 객체의 HashCode가 달라 조회가 안된다.애초에 두 PhoneNumber 객체는 각각 HashMap에 저장되어있을 것이다.

동치인 모든 객체에서 똑같은 hashCode를 반환하는 코드

그럼 hashCode 를 적당하게 아무렇게나 재정의해도 되는 것일까? 절대 안된다!!

//사용금지
@Override
	public int hashCode() {
		return 42;
	}

위코드는 모든 객체에서 똑같은 해시 코드를 내어주므로 모든 객체가 해시테이블의 버킷 하나에 마치 연결리스트linked list처럼 동작한다. 그 결과 평균 수행 시간이 O(1)인 해시 테이블이 O(n)으로 느려져서, 객체가 많아지면 도저히 쓸 수 없게 된다.

따라서 좋은 해시함수라면 서로 다른 인스턴스에 대해 다른 해시코드를 반환해야 한다. 논리적으로 동일한 관계인 객체들만 해시코드가 같아야 한다.

주의할 점

• equals비교에 사용되는 필드에 대해서만 해시코드를 계산한다. equals비교에 사용되지않는 필드까지 해시코드계산에 사용하면 hashCode 규약 두번째를 어기게 될 수 있다.

• Objects 클래스의 hash 메서드가 있지만 성능이 느리다.

  • 입력 인수를 담기 위한 배열이 만들어지고, 입력 중 기본 타입이 있다면 박싱과 언박싱도 거쳐야하기 때문이다. 자기도 모르는 auto boxing에서 불필요한 객체 생성과 박싱 / 언박싱이 이뤄질 수 있다.

• 클래스가 불변이고 해시코드 계산비용이 크다면 매번 새로 해시코드 계산보다는 캐싱방식을 고려해라.

  • 이 타입의 객체가 주로 해시의 키로 사용될 것 같다면 인스턴스 만들어질때 미리 해시코드를 계산하여 캐싱하자.
  • 만약 해시키로 자주 안사용된다면 hashCode가 처음 불릴 때 계산하는 지연 초기화lazy initialization전략을 써라. 필드를 지연초기화하려면 그 클래스를 스레드 안전하게 만들어야한다.

• 성능을 높인답시고 해시코드를 계산할 때 핵심 필드를 절대 생략해서는 안 된다.

  • 계산 속도는 빨라지겠지만, 해시 품질이 나빠져 해시 테이블의 성능이 심각하게 떨어질 수 있다. 특히 어떤 필드는 특정 영역에 몰린 인스턴스들의 해시코드를 넓은 범위로 고르게 퍼트려주는 효과가 있을지도 모른다. 해시코드를 넓은 범위로 고르게 퍼트려주는 필드를 만약 생략한다면, 해당 영역의 수많은 인스턴스가 단 몇개의 해시코드로 집중되어 해시테이블의 속도가 선형으로 느려질 것이다.

해시코드를 지연 초기화하는 hashCode 메서드

스레드 안전성까지 고려해야 한다.

private int hashCode; //기본값 0

@Override
public int hashCode() {
      	int result = hashCode; // 초기값 0을 가진다.
        if(result == 0) {
          int result = Integer.hashCode(areaCode);
          result = 31 * result + Integer.hashCode(areaCode); //31곱함
          result = 31 * result + Integer.hashCode(areaCode); //31곱함
          hashCode = result;
        }
        return result;
}

동시에 여러 쓰레드가 hashCode를 호출하면 여러 쓰레드가 동시에 계산하여 우리의 처음 의도와는 다르게 여러번 계산하는 상황이 발생할 수 있다.그래서 지연 초기화를 하려면 동기화를 신경써주는 것이 좋다.

31을 곱하는 이유

연산을 빠르게 처리할 수 있다. 31 * N = 32N - N으로서 32는 2^5이니 어떤 수 N에 대해 32를 곱한 값은 시프트연산으로 쉽게 구현할 수 있다. 따라서 N에 31을 곱한 값은 (N << 5) - N이다. 31을 곱하면 이렇게 쉬프트 연산을 통해 빠른 계산이 가능하기 때문에 31을 사용한다.

현재의 String 클래스의 hashCode 메서드에도 성능 향상을 위해 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;
    }

이전의 String의 HashCode

이전의 String 클래스는 아래와 같이 모든 문자에 대한 해시 함수를 계산하는 게 아니였다.
skipt을 통해 일정 간격의 문자를 건너가면서 해시 함수를 계산했다.

아래 코드를 보면 문자열의 길이가 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에 대해서 동일한 해시 값이 나오는 문제가 생겼기 때문이다.

결론

equals를 재정의할 때는 hashCode도 반드시 재정의해야 한다. 그렇지 않으면 프로그램이 제대로 동작하지 않을 것이다.

참고

이펙티브 자바

자바봄 블로그
https://javabom.tistory.com/3?category=833277

Naver d2 - Java HashMap 동작원리
https://d2.naver.com/helloworld/831311