Effective Java - Item 11. equals를 재정의하려거든 hashCode도 재정의하라

eqauls를 재정의한 클래스는 hashCode 또한 재정의 해야 한다.

이는 HashMap이나 HashSet과 같은 컬렉션의 원소 비교방법 때문이다.

 

public final class PhoneNumber {
    private final short areaCode, prefix, lineNum;

    public PhoneNumber(int areaCode, int prefix, int lineNum) {
        this.areaCode = rangeCheck(areaCode, 999, "area code");
        this.prefix   = rangeCheck(prefix,   999, "prefix");
        this.lineNum  = rangeCheck(lineNum, 9999, "line num");
    }

    private static short rangeCheck(int val, int max, String arg) {
        if (val < 0 || val > max)
            throw new IllegalArgumentException(arg + ": " + val);
        return (short) val;
    }

    @Override public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof PhoneNumber))
            return false;
        PhoneNumber pn = (PhoneNumber)o;
        return pn.lineNum == lineNum && pn.prefix == prefix
                && pn.areaCode == areaCode;
    }
    
    public static void main(String[] args) {
        Map<PhoneNumber, String> m = new HashMap<>();
        m.put(new PhoneNumber(707, 867, 5309), "제니");
        System.out.println(m.get(new PhoneNumber(707, 867, 5309)));
    }
}

아래의 main문에서 Value 값으로 "제니"가 나올 것 같지만 그렇지 않다.

Object의 hashCode는 인스턴스의 레퍼런스를 기준으로 해쉬 값을 계산하기 때문에

PhoneNumber의 서로 다른 인스턴스를 사용하여 이 두 객체는 다른 hash 값을 반환한다.

 

HashMap은 내부적으로 두 객체의 HashCode를 비교하고 이것이 다르면 eqauls 메소드는 실행되지 않는다.

이런 최적화 방식을 채택했기 때문에 논리적으로 동치인 객체를 표현하기 위해 HashCode를 재정의 해주어야 한다.

 

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

 

 

위와 같이 hashCode를 구현할 수 있다. 이는 훌륭하게 동작하지만

동치인 객체뿐이 아닌 모든 객체에 대해 같은 값을 반환한다. 

 

이렇게 작성하면 모든 객체가 하나의 해쉬 테이블 버킷에 담겨 linked list와 같이 동작해
O(1)의 복잡도가 아닌 O(n)의 복잡도로 느려져 쓸 수 없어진다.

 

 

그렇다면 hashCode를 어떻게 작성하면 좋을까?

다음은 hashCode를 작성하는 간단 요령은 다음과 같다.

 

equals에서 필수적으로 비교해야 한다고 선언한 필드들에 대해 다음을 수행한다.

int result = 0;

// 반복
result = 31 * result + c;

 // c = 필드 f의 해시코드 값

필드 f의 타입에 따라 hash 값 c를 계산하는 법은 다음과 같다.

• 타입이 premitive type이라면 해당 타입의 Wrapper 클래스의 Type.hashCode(f)를 호출한다.
• 타입이 레퍼런스 타입이라면 이 클래스의 hashCode를 호출한다.
  만약 이 계산이 복잡하다면 이 필드의 표준형(Canonical representation)의 hashCode를 호출한다.
  -> 표준형이라는 이야기가 또 나왔다. 다시 찾아보니 선형대수의 Canonical form 이야기는 아닌 것 같고
  스택 오버플로우에서 유니코드에 대한 이야기가 있었다.
  UTF-8는 가변길이의 인코딩은 일반 문자에 대해 인코딩하는 방식이 둘 이상 있는 경우가 많은데,
  이를 전부 고려하면서 코드를 설계해 두긴 어렵다.
  따라서 소프트웨어가 문자열이 정규화되었는지 여부를 확인한 다음
  정규화되지 않은 경우 거부하는 것입니다.
  이 경우 클라이언트/서버 컨텍스트에서 정규화는 클라이언트의 책임입니다.
  
  데이터를 나타내는 표준형식을 정해두고 너가 이를 맞춰 바꿔서 넣으라는 뜻 같다.
  어떤 클래스의 hashCode를 구할 때 모든 경우를 생각하면서 검사하는 게 아니라
  정해 둔 표준형으로 변환하여 hashCode를 구하라는 뜻 같다.
  • 레퍼런스가 null 이면 0을 반환하기를 추천한다.
• 필드가 배열이라면 배열 내부의 핵심원소 각각을 별도 필드처럼 다룬다.
  배열 내부의 값에 대한 hashCode를 구하고 이에 대해 각각 31을 곱해주는 것이다.
• 모든 필드에 대한 계산이 끝나면 result를 반환한다.

 

 

총필드의 개수를 n개라고 했을 때

result = 31^(n-1) * C1 + 31 ^ (n-2) * C2 + ······ + 31^1 *Cn-1 + 31^0 * Cn의 값을 가지게 된다.

 

이렇게 계산하면 필드를 곱하는 순서에 따라 다른 hashCode를 반환한다.
String의 hashCode를 곱셈 없이 구현하게 되면 "apple"과 "papel"과 같이

철자가 같고 순서가 다른 문자열에 대해 같은 hashCode를 반환하게 된다.
곱셈을 이용하여 구현하자.

31을 쓰는 이유는 적당한 소수이면서 2의 제곱수인 32에서 1을 뺀 수로 bit 연산이 가능해진다.
(i << 5) - i로 원래의 수를 5번 left shift 하면 32를 곱한 것과 같고 여기서 원래의 수를 빼면 31을 곱한 것과 같아진다.
이는 31을 곱하는 것보다 빠르다. 요즘의 JVM은 이런 최적화를 알아서 해준다고 한다.
맘 편히 31을 곱하도록 하자.

 

// 코드 11-2 전형적인 hashCode 메서드 (70쪽)
@Override public int hashCode() {
    int result = Short.hashCode(areaCode);
    result = 31 * result + Short.hashCode(prefix);
    result = 31 * result + Short.hashCode(lineNum);
    return result;
}

// 코드 11-3 한 줄짜리 hashCode 메서드 - 성능이 살짝 아쉽다. (71쪽)
@Override public int hashCode() {
    return Objects.hash(lineNum, prefix, areaCode);
}

위를 토대로 PhoneNumber 클래스의 hashCode를 구현한 모습이다.
11-2 코드와 달리 11-3 코드에서 Object가 제공해 주는 hash 함수를 사용할 수도 있다.
그러나 이는 각 원소를 담을 배열을 생성하고

Boxing과 UnBoxing을 하는 등 오버헤드가 있어 수행 시간이 더 오래 걸린다.

 

 

클래스가 immutable 하고 hashCode를 계산하는 비용이 크다면 캐싱하는 방식을 고려해 볼 수 있다.

이때 싱글톤에 대해 이야기할 때 설명한 지연 초기화(lazy initialization) 방식을 사용할 수 있다.

처음 불린 이후부터 캐싱하는 것이다.

// 해시코드를 지연 초기화하는 hashCode 메서드 - 스레드 안정성까지 고려해야 한다. (71쪽)
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 + Short.hashCode(lineNum);
        hashCode = result;
    }
    return result;
}

내 생각으론 PhoneNumber 클래스가 immutable 하게 설계되었다면

thread safe를 고려하지 않아도 될 것 같다. context switching이 발생해 초기화가 중복해서 발생해도
어차피 똑같은 값이 기록될 것이기에 이후 캐싱된 값을 사용함에 지장이 없을 것 같다.

 

 

 

새롭게 알게 된 사실

/** Cache the hash code for the string */
private int hash; // Default to 0
    
public int hashCode() {
	int h = hash;
	if (h == 0 && value.length > 0) {
    	hash = h = isLatin1() ? StringLatin1.hashCode(value)
                   	       : StringUTF16.hashCode(value);
	}
	return h;
}

String도 hash 값을 lazy initialization을 통해 캐싱해 사용한다.

 

서비스 로직에서 HashMap과 같은 자료구조의 사용이나 문자열의 비교가 빈번히 발생한다.

HashMap을 사용해 hash 값이 캐싱되어 있고 문자열을 비교해야 하는 상황이라면

String t = "김치", s = "김치";
Map<String, String> m = new HashMap<>();
m.put(t,"찌개");
if(t.hashCode() == s.hashCode() && t.equals(s)){
    //Hash 친구들의 최적화 방식
}

이런 식으로 최적화할 수 있지 않을까

Hash가 말이 O(1)이지 문자열의 길이가 길어지면

문자열 전체를 순회하며 hashCode, equals를 계산하는 상수가 상당히 커진다.

 

equals를 실행하기 이전 캐싱된 hash 값이 있으면 두 문자열의 리터럴이 다를 때 빠르게 도망칠 수 있을 것 같다.

 

코드 - https://github.com/WegraLee/effective-java-3e-source-code/tree/master/src/effectivejava/chapter3/item11

GitHub - WegraLee/effective-java-3e-source-code: 『이펙티브 자바, 3판』(인사이트, 2018)

 

Canonical form - https://stackoverflow.com/questions/280107/what-does-the-term-canonical-form-or-canonical-representation-in-java-mean

What does the term "canonical form" or "canonical representation" in Java mean?