[JAVA] equals와 hashcode

언제 equals와 hashcode를 재정의(Override) 해야 하는가?

• 사용자 정의 객체의 동등성을 비교하기 위해 equals와 hashCode를 재정의 해야함

  • Set, Map과 같은 컬렉션내에 객체의 동등성을 비교하여 중복을 판단

• String, ArrayList, LinkedList, Set등 사전에 정의된 객체나 컬렉션은 equals와 hashCode가 재정의 되어 있다.
  

• 원시타입은 객체가 아닌 값이기에 동일성 비교를(==) 통해 중복을 판단한다.

왜 equals와 hashCode를 같이 재정의 해야 하는가?

1. equals만 재정의 했을 경우

   서로 같은 객체가 서로 다른 해시값을 가질 수 있기 때문

   • equals를 사용하는 클래스는 주로 해시기반 자료구조에서 사용되기 때문에(HashSet, HashMap)
     hashCode를 재정의 하지 않으면 equals를 통해 두 객체가 동등하다는 것을 판단했지만 서로 다른 해시값을 갖게되어 해시기반 자료구조에서 제대로 동작하지 않는다.

2. hashCode만 재정의 했을 경우

   서로 같은 해시값이지만 동등한 객체가 아닐 수 있음

   • 해시 기반 자료구조에서 두 객체가 같은 해시값을 가지지만 equals에서 동등하지 않다는 결과를 얻을 수 있음

예시

class EqualsTest{
	//      이너 클래스에 equals와 hashCode 재정의 한 경우
		main(){
            Set<Location> hs = new HashSet<>();
            hs.add(new Location(1, 2));
            hs.add(new Location(1, 2));
            System.out.println(hs.size());

    //      이너 클래스에 equals와 hashCode 재정의 안한 경우
            Set<Loc> hs2 = new HashSet<>();
            hs2.add(new Loc(1, 2));
            hs2.add(new Loc(1, 2));
            System.out.println(hs2.size());
       	}
        class Location{
          int y;
          int x;
          public Location(int y, int x) {
              this.y = y;
              this.x = x;
          }
          @Override
          public boolean equals(Object o) {
  //            두 객체의 주소가 같으면 서로 같은 객체
              if (this == o) return true;
  //            비교하려는 객체 o가 null이거나
  //            두 객체가 서로 다른 클래스인경우
  //            서로 다른 객체
              if (o == null || getClass() != o.getClass()) return false;
  //            Object 클래스에서 자식 클래스로 형변환
              Location location = (Location) o;
  //            두 객체가 같은 값을 갖는지 체크
              return y == location.y && x == location.x;
          }
          @Override
          public int hashCode() {
              return Objects.hash(y, x);
          }
        }
        class Loc{
            int y;
            int x;

            public Loc(int y, int x) {
                this.y = y;
                this.x = x;
            }
        }
}

출력: 1
         2

---

참고2: 동등성과 동일성의 차이는?

동등성 (equals 매소드로 비교)

• 두 객체의 주소가 다르더라도 객체가 갖는 값이 같은 객체

동일성 (== 연산으로 비교)

• 객체의 값 뿐만 아니라 주소까지 같은 객체

예시

List<Integer> ls = new ArrayList<>();
List<Integer> equality = new ArrayList<>();
List<Integer> different = new ArrayList<>();
List<Integer> identity = ls;

ls.add(1);
ls.add(2);

equality.add(1);
equality.add(2);

different.add(2);
different.add(1);

/* 
	ls = [1, 2]
	equality = [1, 2]
	different = [2, 1]
    identity = [1, 2]
*/

• 동등성 비교 (equals 메서드):

  • ls.equals(equality): ls와 equality의 내용이 같으므로 true를 반환
  • ls.equals(different): ls와 different의 내용이 다르므로 false를 반환
  • ls.equals(identity): ls와 identity는 동일한 객체를 참조하므로 내용이 같으므로 true를 반환

• 동일성 비교 (== 연산자):

  • ls == equality: ls와 equality는 서로 다른 객체이므로 false를 반환
  • ls == different: ls와 different는 서로 다른 객체이므로 false를 반환
  • ls == identity: ls와 identity는 동일한 객체를 참조하므로 true를 반환

---

참고: 해시충돌과 그 해결법

hash 충돌이란?

• hash 충돌이란 서로 다른 데이터가 같은 hashcode값을 갖는 문제이다.

hash 충돌이 발생하는 이유

• hash table의 크기가 작아서
• 입력 데이터 양이 너무 많아서
  -> 비둘기집의 원리에 의해 발생한다.

일반적인 hash 충돌 해결방법

1. Separate chaining: 충돌 발생시 해당 해시코드에 연결된 버킷에 저장하는 방식
   • Linked List
   • Red-Black Tree(생소하다면 java의 TreeMap을 떠올리면 된다.)
2. Open addressing: 충돌 발생시 다른 빈 버킷을 찾아 저장하는 방식
   • Linear probing
     • 순차적으로 빈 버킷 탐색
   • Quadratic probing
     • 각 해시코드의 제곱을 하여 빈 버킷을 탐색

JAVA에서의 hash 충돌 해결법

• 기본적으로 Java에서는 separate chaining 방식으로 충돌을 해결한다.
• 아래 버전에 따른 성능 개선이 존재한다.
  • Java 8 이전: Linked List: O(n)
  • Java 8 이후: Red-Black tree: O(logn)

ps. comapreTo는 언제 구현해야 하는가?

• PQ와 같은 정렬기능이 있는 Collection에서 사용자 정의 객체를 저장할 경우 compareTo 구현