equals를 재정의할 때는 hashCode도 같이 재정의하자

* 이펙티브 자바 2/E를 읽고 공부하기 위해 기록한 게시글입니다.

 

9. equals를 재정의할 때는 "반드시" hashCode도 재정의하라

equals 메서드를 재정의(오버라이딩)하는 클래스는 "반드시" hashCode 메서드도 재정의 해야한다.

그렇지 않으면 Object.hashCode의 일반 규약을 어기게 되어 HashMap, HashSet, HashTable과 같은 해시 기반 컬렉션과 함께 사용할 시 문제가 발생한다

 

Object.hashCode 클래스의 일반 규약이 뭐길래 그럴까?

1. 응용프로그램 실행 중 같은 객체의 hashCode를 여러번 호출하는 경우, equals가 사용하는 정보들이 변경되지 않았다면 언제나 동일한 값이 반환되어야 한다. 당연한 이야기. (단 프로그램이 재시작 된 경우에는 다를 수 있다)

 

2. equals 메서드가 같다고 판정한 두 객제의 hashCode 값은 동일해야 한다.   <<<< "위반사항"

 

3. equals 메서드가 다르다고 판정한 두 객체의 hashCode 값은 반드시 다를 필요는 없다.

(다만 다른 경우가 해시 테이블의 성능을 더 향상시킬 수 있다.)

 

 

# hashCode 정의를 따로 하지 않으면

- 기본적으로 주소값을 기반으로 한 정수값을 갖는다

- 동일한 객체가 아니면 (동등한 객체라도) 해시 테이블에서 값을 찾아올 수가 없다 (주소값이 다르기 때문에)

 

# hashCode를 전부 아예 같은 상수값으로 때려박으면

- 같은 객체는 같은 해시코드를 갖게 된다 => "충돌" 발생 -- 아래 참고

- 좋은 해시 함수는 다른 객체에는 다른 해시 코드를 반환하는 경향이 있다.

서로 다른 객체들을 가능한 해시값에 균등하게 배분하는 것이 이상적인 해시 테이블.

 

그럼 어떻게?

=> IDE가 만들어주는거 갖다쓰자

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        return Objects.equals(getId(), user.getId()) 
            && Objects.equals(getName(), user.getName()) 
            && Objects.equals(getTel(), user.getTel());
    }

    @Override
    public int hashCode() {
        return Objects.hash(getId(), getName(), getTel());
    }

이를 보면 Objects.hash 메서드를 이용하는 것을 확인할 수 있다!

 

책에서는 어떻게 했을까

1. 0이 아닌 상수를 int result 변수에 저장한다

2. 객체 안에 있는 모든 중요 필드 f (equals 메서드에 사용되는 필드) 각각마다 쿵짝 연산을 거쳐 해시코드 c를 얻는다

3. 계산된 해시코드 c를 아래와 같이 연산한다.

result = 31 * result + c;

4. 최종 result를 객체의 해시코드로 갖는다.

 

 

* 근데 왜 하필 31을 곱해주는 것일까?

- 홀수이면서 소수이기 때문. 왜 그 많은 소수 중 31이냐고 물으면 그냥 관례상 그렇다고 한다.

- 31 * i 는 (i << 5) - i 와 같다

 

* 해시코드 c 연산 과정에서 equals 메서드에 사용되는 필드를 계산과정에서 빼면 안된다

- 해시 값 품질이 떨어지기 때문에 해시테이블의 성능을 저하시킬 수 있다.

 

 

========

 

해시테이블은 버켓 배열과 해시함수로 구성된다.

- 항목들의 키를 주소로 매핑하여 인덱스를 생성하고, 이 인덱스를 활용해 버켓 배열에 값을 저장하거나 검색.

- 기대 시간은 O(1), 최악 시간은 O(N)

 

* 대개 버켓 배열의 사이즈 M은 소수가 되게 만든다.

 

(+ 고오급 정보) 해시 테이블이 충돌을 해결하는 전략을 알아보자!

* 충돌: 두 개 이상의 원소들이 동일한 셀로 매핑되는 것.

 

1. 분리연쇄법(seperate chaining)

- 버킷 배열을 연결리스트 배열로 만들어서 동일한 원소들이 매핑되는 경우 연결리스트로 연결하는 방법.

- 단순하고 빠르지만, 별도의 저장공간이 필요하다

2. 개방주소법(open addressing)

- 충돌 항목을 테이블의 다른 셀에 저장하는 방법

- 분리연쇄법에 비해 공간 사용은 절약되지만, 삭제가 어렵고 군집화(cluster) 현상이 발생

- 3가지 방법(선형 조사법, 2차 조사법, 이중 해싱)이 존재한다!

2-1. 선형조사법(linear probing)

- 충돌 항목은 바로 다음의 비어있는 셀(+0, 1, 2, 3...)에 저장하는 방법.

- A[(h(k) + f(i)) % M], f(i) = i, i = 0, 1, 2...

- 충돌 항목들이 군집화되는 현상 발생 (1차 군집화, primary clustering)

 

2-2. 2차조사법(quadratic probing)

- 충돌 항목을 제곱의 순서 뒤에 저장하는 방법(+0, 1, 4, 9....)

- A[(h(k) + f(i)) % M], f(i) = i * i, i = 0, 1, 2...

- 1차 군집화는 피하지만, 그보다는 덜한 2차 군집화(secondary clustering)가 발생

- M이 소수가 아니거나 버켓 배열이 반 이상 차면, 빈 버켓이 있더라도 자리를 찾지 못할 수 있다!!

 

2-3. 이중 해싱(double hashing)

- 해시 함수를 두번 적용하는 방법

- 군집화 현상을 최소화할 수 있다.

 

 

* 적재율(load factor): 말 그대로. 버켓 배열에 원소가 차있는 비율.

- α = n / M

- 낮게 유지될 수록 좋다(1 아래로)

- 분리연쇄법의 경우는 α <= 1, 개방주소법의 경우 α <= 0.5 이면 기대 실행시간이 O(1)에 수렴한다

- 적재율이 해시테이블의 성능을 좌우한다!!

 

* 재해싱(rehashing): 해시테이블의 적재율을 특정 값 이하로 유지하기 위해서는 원소를 삽입할 때 마다 한계점을 넘기지 않기 위해 추가적인 작업을 거침. 버켓 배열의 크기를 증가시켜 적재율을 낮추는것 (약 2배 증가, 소수)

-> 1. 적재율의 최적치를 초과했을 때 / 2. 삽입에 실패했을 때 / 3. 너무 많은 비활성 셀들로 인해 성능이 떨어졌을 때