HashCode

해당 글은 Effective Java Item11을 기반으로 합니다.

Equals 재정의시 HashCode도 재정의하라

 

equals 재정의 내용이 상당히 알찬데, 전 되도록이면 책 내용처럼 equals 재정의는 하지 않을 것이기 때문에 일단은 생략했습니다.

그럼 hashCode 재정의도 일단은 필요 없겠지만, 둘이 어떤 연관관계가 있는지 살펴보는 것은 재밌을 듯 합니다.

 

내용에 들어가기전 Hash에 대해 모르신다면, 아래 포스팅을 참고해주세요.

11. Hash

 

 

 

equals를 재정의한 클래스에서 hashCode를 재정의하지 않는다면, 아래의 hashCode 일반 규약을 어기게됩니다.

• equals 비교에 사용되는 정보가 변경되지 않았다면, app이 실행되는 동안 그 객체의 hashCode 메서드는 몇 번을 호출해도 같은 값을 반환해야한다.
• equals가 두 객체를 같다고 판단한 경우, 두 객체의 hashCode는 같은 값을 반환해야한다.
• equals가 두 개체를 다르다고 판단하더라도, 두 객체의 hashCode가 서로 다른 값을 반환할 필요는 없다. 단, 다른 값을 반환해야 해시 테이블의 성능이 좋아진다.

 

hashCode를 잘못 재정의시 발생할 수 있는 문제는 논리적으로 같은 객체를 서로 다르게 판단할 위험이 있다는 것입니다.

자바에서 물리적 동치는 '==', 논리적 동치는 'equals'로 비교하는데요. 아시다시피 equals는 물리적으로 다른 객체를 논리적으로 같다고 나타낼 수 있습니다. 하지만, Object 클래스의 기본 hashCode 매서드는 이 둘을 전혀 다르다 판단하기 때문에 규약과는 달리 서로 다른 값을 반환합니다.

 

import common.Point;

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Point, String> map = new HashMap<>();
        map.put(new Point.Builder(0, 0).build(), "원점");

        System.out.println(map.get(new Point.Builder(0, 0).build()));	// null
    }
}

 

위와 같은 경우를 많이 겪어보셨을겁니다.

물론 equals 마저 재정의 하지 않는다면 아래의 두 인스턴스는 equals에서도 false를 반환하게 됩니다.

Point p1 = new Point.Builder(0, 0).build();
Point p2 = new Point.Builder(0, 0).build();

p1.eqauls(p2); // false

이 두 인스턴스가 equals를 재정의한 채로 map에 저장되어 사용한다 가정을 해도 결과는 같습니다. 왜냐하면, 논리적으로 동치인 두 객체라해도 서로 다른 해시코드를 반환하기 때문에 엉뚱한 버킷에서 각각의 객체를 찾으려 하기 때문입니다.

물론, 두 인스턴스가 같은 버킷에 있더라도 null을 반환하는데요. HashMap은 해시코드가 다른 엔트리끼리는 동치성 비교를 시도조차 하지 못하도록 최적화 되어있기 때문입니다.

 

해당 문제는 hashCode 메서드를 적절하게 재정의하면 해결됩니다. 물론 아래와같이 정신나간척 정의해도 문제는 해결됩니다.

@Override
public int hashCode() {
	return 42;
}

 

 

그러나 이 방식은 자바에서 HashMap 사용시 계속 같은 버킷으로 데이터가 저장되는 해시 충돌로 인해 Separate chaining이 발생하게되고, 연결리스트로 버킷 뒤로 데이터가 저장되므로 수행시간이 O(1) -> O(N)으로 증가하게 됩니다.

 

따라서, 좋은 해시 함수라면 서로 다른 인스턴스에 다른 해시 코드를 반환해야합니다. (3번째 규약)

좋은 hashCode() 구현하는 방법

1. int 변수 result를 선언한 후 c로 초기화, 이때 c는 해당 객체의 첫번째 핵심 필드(equals 비교에 사용되는 필드)를 단계 [2.1] 방식으로 계산한 해시코드다.
2. 해당 객체의 나머지 핵심 필드 f 각각에 대해 다음 작업을 수행한다.
   1. 해당 필드의 해시코드 c를 계산한다.
      1. 기본타입 필드라면 Type.hashCode(f)를 수행한다. Type: 해당 기본 타입(f)의 박싱 클래스
      2. 참조 타입 필드면서, 이 클래스의 equals 메서드가 이 필드의 equals를 재귀적으로 호출해 비교한다면 이 필드의 hashCode를 재귀적으로 호출한다. 계산이 복잡한 경우 이 필드의 표준형를 만들어 그 표준형의 hashCode를 호출한다. 필드의 값이 null인 경우 0 사용.
      3. 필드가 배열이면, 핵심 원소 각각을 별도 필드처럼 다룬다. 이상의 규칙을 재귀적으로 적용해 각 핵심 원소의 해시코드를 계산한 다음, 단계 [2.2] 방식으로 갱신한다. 배열에 핵심 원소가 없는 경우 단순 상수(0 추천)를 사용한다. 모든 원소가 핵심 원소인 경우 Arrays.hashCode 사용한다.
   2. 단계 [2.1]에서 계산한 해시코드 c로 result를 갱신한다. result = 31 * result + c;
3. result를 반환한다.

 

구현을 완료한 후 이 메서드가 동치인 인스턴스에 대해 같은 hashCode를 반환하는지 확인해보시길 바랍니다. 책에선 테스트 코드를 짜서 확인을 하는데, 다음에 시간나면 해볼게요. ㅎㅎ

어쨌든 위의 방법을 기반으로해서 전형적인 hashCode를 구성해보면 아래와 같습니다. (핵심 필드가 3개인 경우)

@Override
public int hashCode() {
    int result = Short.hashCode(field1);
    result = 31 * result + Short.hashCode(field2);
    result = 31 * result + Short.hashCode(field3);
    return result;
}

 

 

뭐 여러가지 방법이 있는데, 굳이 다른거 보면서 고생하지 말고 기본적인 것부터 잘하는 것이 좋겠죠. ^^

성능을 높히겠다고 핵심 필드를 연산에서 제외시키면 연산에선 빠른 속도를 자랑할 수 있겠으나 향후 해시 품질에 심각한 영향을 주겠죠..

뭐 비둘기집 원리에 의해 어찌됐든 충돌은 난다해도 충돌의 도가 지나치게될 수 있습니다. (충돌 나나박박..) 굳이 뼈를 주고 살을 취하는 변태스러운 행동도 자제하는게 좋을 것 같습니다. ㅎㅎ

 

참고로 Lombok에선 equals(), hashCode()를 자동으로 생성해주는 @EqualsAndHashCode 어노테이션을 제공해줍니다.

여윽시 킹 갓 복..

 

 

이외의 내용들도 알면 좋겠지만, 직접 책을 보시는 것을 추천드립니다. 그리고 자바의 HashMap을 예시로 들었기 때문에 Separate chaining이라는 점 명심해주세요.

 

 

 

 

 

참고 자료

Effective Java - 조슈아 블로크