item-11-equals-hashcode.md

description	Overriding hashCode

item 11 : equals를 재정의하려거든 hashCode도 재정의하라

equals를 재정의한 클래스는 hashCode도 재정의 해야 한다.

그렇지 않으면 인스턴스를 HashMap이나 HashSet 같은 컬렉션의 원소로 사용할 때 문제가 발생한다.

1. hashCode 일반 규약

✔️ 일관성 : equals 비교에 사용되는 정보가 변경되지 않았다면, hashCode도 변하면 안 된다. (애플리케이션을 다시 실행한다면 이 값이 달라져도 상관 없음)

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

-> ⭐ 논리적으로 같은 객체는 같은 해시코드를 반환해야 한다.

✔️ equals가 두 객체를 다르다고 판단했더라도, hashCode는 꼭 다를 필요는 없다. 하지만, 다른 객체에 대해서는 다른 값을 반환해야 해시테이블의 성능이 좋아진다.

2. 논리적으로 같은 객체는 같은 해시코드를 반환해야 한다.

equals가 물리적으로 다른 두 객체를 논리적으로 같다고 할 때, hashCode 메서드는 이 둘이 완전히 다른 거라고 판단 서로 다른 값을 반환한다.

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

이 코드에 map.get(new PhoneNumber(010,1234,5678))를 실행하면 "리치"가 아닌 null을 반환한다.

PhoneNumber 클래스는 hashCode를 재정의하지 않았기 때문에, 논리적 동치인 두 객체가 서로 다른 해시코드를 반환하여 get 메서드는 엉뚱한 해시 버킷에 가서 객체를 찾으려 한 것이다.

HashMap은 해시코드가 서로 다른 엔트리끼리는 동치성 비교를 시도조차 않도록 최적화 되어있다.

이 문제는 PhoneNumber에 적절한 hashCode 메서드만 작성해주면 해결된다.

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

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

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

3. 좋은 해시 함수라면 서로 다른 인스턴스에 다른 해시코드를 반환해야 한다(good)

좋은 hashCode를 구현하는 방법

이상적인 해시 함수는 주어진 (서로 다른) 인스턴스들을 32비트 정수 범위에 균일하게 분배해야 한다.

1. int 변수인 result를 선언한 후 값 c로 초기화한다.
   • 이 때, c는 해당 객체의 첫번째 핵심 필드를 단계 2.1 방식으로 계산한 해시코드이다.
   • 여기서 핵심 필드는 equals 비교에 사용되는 필드를 말한다.
2. 해당 객체의 나머지 핵심 필드인 f 각각에 대해 다음 작업을 수행한다.
   1. 해당 필드의 해시코드 c 를 계산한다.

      • i. 기본 타입 필드인 경우:

        • 해당 타입의 박싱 클래스의 hashCode() 메서드를 사용한다.
        • 예: Short.hashCode(f), Integer.hashCode(f) 등.

      • ii. 참조 타입 필드인 경우:

        • 해당 클래스의 equals() 메서드가 이 필드의 equals()를 재귀적으로 호출하여 비교한다면, 이 필드의 hashCode()를 재귀적으로 호출한다.
        • 계산이 복잡해질 것 같으면, 그 필드의 표준형(canonical representation)¹을 만들어 그 표준형의 hashCode()를 호출한다.

        예시 1: 정렬되지 않은 컬렉션 필드

        • 필드가 Set<String> 타입이고, 이 집합의 요소들은 순서가 없다.
        • Set 자체의 해시코드를 사용하면 요소의 순서에 따라 해시코드가 달라질 수 있어, equals()와 일관성이 없어질 수 있다.
        • 해결 방법:
          • 이 Set을 표준형으로 변환한다. 예를 들어, 요소들을 정렬하여 List<String>으로 만든다.
          • 이렇게 하면 항상 같은 순서로 요소들이 정렬되므로, hashCode()를 호출해도 일관된 결과를 얻을 수 있다.

        @Override
        public int hashCode() {
            List<String> sortedList = new ArrayList<>(stringSet);
            Collections.sort(sortedList);
            return sortedList.hashCode();
        }

      • 예시 2: 복잡한 객체 필드

        • 필드가 복잡한 객체인데, 그 객체의 hashCode() 구현이 없거나 믿을 수 없다고 가정
        • 또는 그 객체의 상태 중에서 우리 클래스의 equals()에서 사용하는 부분만 해시코드에 반영하고 싶을 때가 있다.
        • 해결 방법:
          • 해당 필드에서 우리가 관심 있는 부분만 추출하여 새로운 객체(표준형)를 만든다.
          • 예를 들어, 중요한 필드들만 모아서 List나 String 등으로 표현
          • 그런 다음 그 객체의 hashCode()를 호출

        @Override
        public int hashCode() {
            // 복잡한 객체 complexField에서 중요한 부분만 추출
            String canonicalForm = complexField.getImportantPart();
            return canonicalForm.hashCode();
        }

        • 필드의 값이 null이면 0을 사용한다.

      • iii. 배열인 경우:

        • 핵심 원소 각각을 별도의 필드처럼 다룬다.
        • 위의 규칙을 재귀적으로 적용하여 각 핵심 원소의 해시코드를 계산한 다음, 아래의 방법으로 result를 갱신한다.
        • 배열에 핵심 원소가 하나도 없다면 상수 0을 사용한다.
        • 모든 원소가 핵심 원소라면 Arrays.hashCode()를 사용할 수 있다.
   2. 단계 2.1에서 계산한 해시코드 c로 result를 갱신한다.
      • result = 31 * result + c;
3. result를 반환한다.

• 필드를 곱하는 순서에 따라 result 값이 달라지므로, 필드 순서를 변경하면 해시코드가 달라진다.

코드 예제: PhoneNumber 클래스의 hashCode()

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

• 이 메서드는 PhoneNumber 인스턴스의 핵심 필드 3개(areaCode, prefix, lineNum)를 사용하여 해시코드를 계산한다.
• 동등한 PhoneNumber 인스턴스들은 동일한 해시코드를 가진다.

Objects.hash() 메서드 사용

• Objects 클래스의 hash() 메서드를 사용하면 한 줄로 hashCode()를 구현할 수 있다.

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

• 간결하지만, 성능 면에서 조금 느릴 수 있다.
  • 배열 생성과 기본 타입의 박싱/언박싱이 발생하기 때문이다.
• 성능에 민감하지 않은 상황에서 사용을 권장한다.

4. 해시 코드 캐싱(지연 초기화)

• 클래스가 불변이고 해시코드 계산 비용이 큰 경우, 해시코드를 매번 계산하지 않고 캐싱하는 방법을 고려할 수 있다.
• 해시의 키로 주로 사용되는 객체라면 인스턴스 생성 시 해시코드를 계산해 둘 수 있다.
• 지연 초기화(Lazy Initialization)를 사용하여 처음 hashCode()가 호출될 때 계산하는 방법도 있다.
  • 이 경우 스레드 안전성을 고려해야 한다.

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;
}

• 처음 호출될 때 해시코드를 계산하고 hashCode 필드에 저장한다.
• 이후에는 저장된 값을 반환하여 계산 비용을 줄인다.
• 주의: 필드 hashCode의 초기값은 일반적으로 사용되는 해시코드 값과 달라야 다.

5. 주의할 점

🌱핵심 필드를 생략하지 말 것

• equals비교에 사용되는 필드에 대해서만 해시코드²를 계산한다. (파생 필드는 제외해도 됨)
  • 두 번째를 어기게 될 수 있음
• 성능을 높인답시고 해시코드³를 계산할 때 핵심 필드를 생략해서는 안 된다.
  • 예를 들어, 특정 영역의 인스턴스들이 몇 개의 해시코드로 집중될 수 있다.
• 실제로 자바 2 이전의 String 클래스는 최대 16개의 문자만 사용하여 해시코드를 계산하여 문제를 일으켰다.

31을 곱하는 이유는 비슷한 필드가 여러개일 때 해시효과를 크게 높여주기 위해서다.
비슷한 값들이 여러개 있을때 그냥 더하면 같은 값이 나올 확률이 높다. 소수이면서 홀수로 해시코드의 분포를 더 균일하게 만든다. 그래서 31을 곱해 큰수로 만들어 해시효과를 증가시킨다.

(만약 짝수라면 오버플로가 발생시 정보를 잃게 됨. 2를 곱하는 것은 시프트 연산과 같은 결과를 내기 때문)

🌱 API 사용자에게 해시코드 생성 규칙을 상세히 공표하지 말 것

• String과 Integer를 포함해, 자바 라이브러리의 많은 클래스에서 hashcode 메서드가 반환하는 정확한 값을 알려준다.
• 나중에 문제 생겼을 때 고치기 위함

6. 추가 질문

🤔 왜 해시 코드 계산에서 31을 곱하고, 짝수나 2를 곱하지 않나요?

해시 코드 계산 시 다음과 같은 공식을 많이 사용합니다:

java코드 복사result = 31 * result + c;

31을 사용하는 이유:

1. 홀수이자 소수(prime number)이기 때문입니다:
   • 정보 손실 방지: 짝수를 곱하면 오버플로우 시 최상위 비트가 손실되어 중요한 정보가 사라질 수 있습니다.
   • 홀수를 곱하면: 오버플로우가 발생해도 비트 패턴이 더 잘 섞여 정보 손실이 줄어듭니다.
2. 소수를 곱하면 해시 분포가 좋아집니다:
   • 충돌 감소: 소수를 사용하면 해시 코드 값이 더 균일하게 분포되어 충돌 가능성이 낮아집니다.
3. 효율적인 연산:
   • 최적화 가능: 31은 25−12^5 - 125−1이므로, 곱셈을 비트 시프트와 뺄셈으로 최적화할 수 있습니다.
     • 31 * i는 (i << 5) - i와 같습니다.
   • 성능 향상: 이러한 최적화로 인해 계산 속도가 빨라집니다.
4. 전통적인 관례:
   • 역사적인 이유: 자바의 String 클래스 등에서 이미 31을 사용해 왔으며, 실무에서 좋은 성능을 보여주었습니다.

짝수나 2를 곱하지 않는 이유:

• 비트 패턴의 단순화:
  • 2를 곱하는 것은 비트 시프트 연산과 동일: i << 1과 같습니다.
  • 비트 혼합 부족: 비트 시프트만으로는 비트 패턴이 충분히 섞이지 않아 해시 코드의 다양성이 줄어듭니다.
• 정보 손실 위험:
  • 짝수 곱셈 시 오버플로우 문제: 오버플로우 발생 시 최상위 비트가 사라져 해시 코드의 고유성이 감소합니다.

예시:

두 정수 a와 b가 있다고 가정합니다:

• a = 4 (이진수 0100)
• b = 8 (이진수 1000)

2를 곱할 때:

• 2 * a = 8 (이진수 1000)
• 2 * b = 16 (이진수 10000)

비트가 왼쪽으로 이동하여 상위 비트가 손실될 수 있습니다.

31을 곱할 때:

• 31 * a = 124
• 31 * b = 248

결과 값이 더 넓게 퍼지고, 비트 패턴이 더 복잡해져 충돌 가능성이 줄어듭니다.

---

2. 해시 코드를 계산할 때 핵심 필드를 생략하면 왜 안 되나요? 🤔

핵심 필드를 생략할 경우의 문제점:

• 해시 분포의 불균형: 중요한 필드를 제외하면 다양한 객체들이 동일한 해시 코드를 가질 수 있습니다.
• 해시 코드의 집중: 특정 값에 해시 코드가 몰리게 되어 해시 테이블의 버킷이 불균형해집니다.
• 성능 저하: 충돌이 많아지면 해시 테이블의 성능이 O(1)에서 O(n)으로 떨어집니다.

예시:

Person 클래스가 있다고 가정합시다:

public class Person {
    private String firstName; // 이름
    private String lastName;  // 성
    private int age;          // 나이

    // equals()는 모든 필드를 사용
}

해시 코드를 firstName만 사용하여 구현하면:

@Override
public int hashCode() {
    return firstName.hashCode();
}

결과:

• 해시 코드 충돌 증가: 동일한 이름을 가진 사람들이 많으므로, 그들의 해시 코드가 동일하게 됩니다.
  • 예: "홍길동"이라는 이름을 가진 많은 객체들이 동일한 해시 코드를 가집니다.
• 버킷의 불균형: 해시 테이블에서 동일한 해시 코드를 가진 객체들이 한 버킷에 몰리게 됩니다.
• 성능 문제: 해시 테이블의 해당 버킷이 연결 리스트처럼 동작하여 검색 시간이 길어집니다.

시각적 설명:

1,000명의 Person 객체 중 100명이 "홍길동"이라고 합시다.

• 핵심 필드를 생략한 경우:
  • 100명의 "홍길동" 객체들이 동일한 해시 코드를 가져 동일한 버킷에 저장됩니다.
• 핵심 필드를 모두 사용한 경우:
  • firstName, lastName, age를 모두 사용하면 해시 코드가 다양해져 객체들이 해시 테이블에 고르게 분포됩니다.

---

3. 파생 필드란 무엇이며, 핵심 필드와의 구분 기준은 무엇인가요? 🤔

파생 필드란?

• 정의: 다른 필드의 값으로부터 계산되거나 유도된 필드입니다.
• 특징:
  • 객체의 고유한 상태를 나타내지 않습니다.
  • 객체의 핵심 정보와는 독립적이지 않습니다.
  • 값을 변경해도 객체의 정체성에 영향을 주지 않습니다.

핵심 필드란?

• 정의: 객체의 고유한 속성을 나타내며, equals() 메서드에서 객체의 동등성 비교에 사용되는 필드입니다.
• 특징:
  • 객체의 본질적인 상태를 표현합니다.
  • 값을 변경하면 객체의 정체성이 변합니다.

구분 기준:

1. equals() 사용 여부:
   • equals() 메서드에서 비교에 사용되는 필드는 핵심 필드입니다.
   • 비교에 사용되지 않는 필드는 해시 코드 계산에서 제외해야 합니다.
2. 값의 독립성:
   • 다른 필드로부터 계산되지 않는 필드는 핵심 필드입니다.
   • 다른 필드로부터 계산되는 필드는 파생 필드입니다.
3. 객체의 정체성에 대한 영향:
   • 필드의 값이 객체의 동등성에 영향을 미치면 핵심 필드입니다.
   • 그렇지 않으면 파생 필드입니다.

예시:

Circle 클래스가 있다고 가정합시다:

public class Circle {
    private double radius;        // 반지름 (핵심 필드)
    private Point center;         // 중심 좌표 (핵심 필드)
    private double area;          // 면적 (파생 필드)

    @Override
    public boolean equals(Object o) {
        // radius와 center를 비교
    }
}

• 핵심 필드:
  • radius, center는 equals()에서 비교하므로 핵심 필드입니다.
• 파생 필드:
  • area는 radius로부터 계산되므로 파생 필드이며, 해시 코드 계산에서 제외합니다.

hashCode() 구현:

@Override
public int hashCode() {
    int result = Double.hashCode(radius);
    result = 31 * result + center.hashCode();
    // area는 제외합니다.
    return result;
}

---

4. 동등한 모든 객체에서 동일한 해시 코드를 반환하면 왜 안 되나요? 🤔

동일한 해시 코드를 반환하는 문제점:

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

• 모든 객체가 동일한 해시 코드(42)를 반환합니다.
• 결과적으로 해시 테이블의 하나의 버킷에 모든 객체가 저장됩니다.
• 해시 테이블이 연결 리스트처럼 동작하여 성능이 O(n)으로 떨어집니다.

도표를 통한 설명:

해시 테이블이 10개의 버킷(인덱스 0~9)을 가진다고 가정합시다.

정상적인 경우(좋은 해시 코드):

• 객체들이 다양한 해시 코드를 가집니다.

버킷 0: [ ]
버킷 1: [ ]
버킷 2: [객체 D]
버킷 3: [객체 C]
버킷 4: [ ]
버킷 5: [객체 A]
버킷 6: [ ]
버킷 7: [객체 B]
버킷 8: [ ]
버킷 9: [ ]

• 객체들이 버킷에 고르게 분포됩니다.
• 검색 및 삽입 작업이 빠릅니다(O(1)).

문제의 경우(모든 해시 코드가 동일):

• 모든 객체의 해시 코드가 42입니다.
• 버킷 인덱스는 42 % 10 = 2로 계산됩니다.

버킷 0: [ ]
버킷 1: [ ]
버킷 2: [객체 A, 객체 B, 객체 C, 객체 D, 객체 E, 객체 F, 객체 G, 객체 H, 객체 I, 객체 J]
버킷 3: [ ]
버킷 4: [ ]
버킷 5: [ ]
버킷 6: [ ]
버킷 7: [ ]
버킷 8: [ ]
버킷 9: [ ]

• 모든 객체가 버킷 2에 몰려 있습니다.
• 버킷 2는 연결 리스트처럼 동작하며, 검색 시간이 O(n)으로 증가합니다.

결과 및 영향:

• 성능 저하:
  • 해시 테이블의 이점이 사라지고, 데이터 구조가 배열이나 리스트와 같은 수준으로 느려집니다.
• 사용 불가:
  • 실무에서 해시 테이블을 사용하는 의미가 없어지므로, 이러한 해시 코드는 바람직하지 않습니다.

핵심 요점:

• 고유한 해시 코드 생성: 객체들을 해시 테이블에 고르게 분포시키기 위해 해시 코드를 잘 구현해야 합니다.
• equals()와의 일관성 유지: 동등한 객체는 동일한 해시 코드를 가져야 하지만, 비동등한 객체는 가능하면 다른 해시 코드를 가져야 합니다.
• 상수 해시 코드 지양: 해시 코드에서 항상 같은 값을 반환하면 안 됩니다.

---

위의 내용을 통해 각 질문에 대한 해설과 예시를 제공하였습니다. 이를 통해 해시 코드 구현 시 주의해야 할 점과 그 이유를 이해할 수 있습니다.

✨ 결론

equals를 재정의할 때는 hashCode도 반드시 재정의해야 한다. 그렇지 않으면 프로그램이 제대로 동작하지 않을 것이다.
재정의한 hashCode는 Object의 API 문서에 기술된 일반 규약을 따라야 하며, 서로 다른 인스턴스라면 되도록 해시코드도 서로 다르게 구현해야 한다. AutoValue 프레임워크르 사용하면 멋진 equals와 hashCode를 자동으로 만들어준다.

Footnotes

1. 가독성을 높이기 위해 ↩

2. 해시코드의 역할:

   • 객체를 해시 테이블과 같은 자료구조에서 빠르게 검색하기 위해 사용됩니다.
   • equals() 메서드와 함께 객체의 동등성을 판단하는 데 중요합니다.

   해시코드 규약:

   • equals()가 두 객체를 같다고 판단하면, 두 객체의 hashCode()는 동일한 값을 반환해야 합니다.
   • 반대로, equals()가 다르다고 판단하는 두 객체의 hashCode()가 반드시 다른 값을 반환할 필요는 없지만, 해시 테이블의 성능을 위해 서로 다른 해시코드를 반환하는 것이 좋습니다.
   ↩
3. ↩