아이템[11] - equals를 재정의 하려거든 hashCode도 재정의하라

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

• HashMap이나 HashSet같은 컬렉션의 원소로 사용할 때 문제가 발생한다.
• 해쉬코드 재정의 조건
  • equals 비교에 사용되는 정보가 변경되지 않는다면, hashCode는 변하면 안된다.
  • equals가 두 객체가 같다 판단한다면, 두 객체의 hashCode는 똑같은 값을 반환한다.
  • equals가 두 객체가 다르다고 판단해도, hashCode는 꼭 다를 필요는 없다. 하지만 성능을 챙기려면 hashCode값이 달라야 한다.

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
 }


static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}


final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) { 
            if (first.hash == hash && // 찾은 hash값이 맞는지 비교하고 맞다면 equals를 통해 값을 준다.
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) { // 같은 해쉬값이고 equals의 결과가 다른경우 다음노드를 조회
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

 

위 코드는 HashMap의 조회 함수이다. 이 함수를 보면 2번째 조건을 이해할 수 있다.

HashMap은 들어온 키 객체를 hash값으로 바꾸고 이걸 주소값으로 쓰는 값을 찾아 hash값 키값 equals를 비교하여 다 통과하면 해당 노드를 반환한다.. 

PhoneNumber라는 객체가 equals만 재정의 되어있고 hashCode가 재정의 안 되어있다고 생각해보자.

Map<PhoneNumber,Person> map = new HashMap();
map.put(new  PhoneNumber(010-3333), new Person("y"));
map.put(new  PhoneNumber(010-3333), new Person("z"));

 

 

이 맵에서 우린 전화번호가 같으면 같은 사람을 뽑고 싶을 것이다.

하지만 실제 조회해 보면 같은 전화번호인데 서로 다른 두명이 조회될 거다.

해쉬코드를 재정의 안해서다. 위 16번째 줄을 보면 table에서 객체를 찾을 때 hash값이 다르기 때문에 애초에 같은 PhoneNumber의 다른 해쉬값을 주소로 해서 Person객체를 각각 저장했을 것이다.

해시코드가 다르면 동치성을 비교조차 하지 않는다. 

 

* 두번째 조건을 만족시키려면 항상 같은 HashCode를 반환하면 되지않나?

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

 

안된다. 항상 같은 hashCode는 성능에 정말 좋지않다.

다시한번 조회함수를 보자.  20번째 줄은 hashCode로 찾은 첫번째 노드에 값이 실제로 equals를 만족하지 못해서 다음 노드를 찾는 조건이다.

즉 해쉬값이 같은데 실제 값은 다르면 해당 노드에 다음 노드의 주소를 저장해놓는 것이다.  이렇게 될경우 항상 같은 해쉬코드를 반환하도록 하면 그냥 연결리스트를 쓰는 것과 똑같은 시간복잡도를 갖게 될 것이다.

 

*올바른 해쉬코드를 만드는 법

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

자세한 순서는 이펙티브자바 69p를 참고

주의할 점

• equals에 논리적 동치를 확인하는데 사용하지 않는 필드는 빼고 해야한다.
• 만약 hash로 바꾸려는 필드가 기본 타입이 아니면 해당 필드의 hashCode를 불러 구현한다.
  * 계산이 복잡한 경우는 표준형을 만들어 구현한다. (아이템 10) 55p참고
• 참조 타입 필드가 null일 경우 0을 사용.
• 31을 곱하는 이유는 비슷한 필드가 여러개일 때 해시효과를 크게 높여주기 위해서다. 
  • 비슷한 값들이 여러개 있을때 그냥 더하면 같은 값이 나올 확률이 높다. 그래서 31을 곱해 큰수로 만들어 해시효과를 증가시킨다.
• 31인 이유
  • 짝수이고 오버플로가 발생한다면 정보를 잃게된다. -> 홀수를 곱해도 똑같은 상황이 발생하는 거 아닌가?
  • 소수여서 31이다. (책에도 소수를 곱해야하는 정확한 이유는 모른다고 했다.
  • 연산을 빠르게 처리할 수 있다. 31 * i는 jvm이 최적화해 (i << 5) - i로 바꿔 쉬프트 연산을 하도록 설계되어있다.
• 해쉬 충돌이 더 적은 방법은 구아바의 Hashing을 참고하자.
• Objects클래스에 있는 hash함수도 있지만 성능이 느리다. 인텔리제이의 자동완성 해쉬는 Objects의 해쉬를 사용한다.

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

 

2. 해쉬코드를 지연 초기화하자.

• 자주 해쉬의 키로 사용할 것 같으면 인스턴스가 만들어질 대 해시코드를 계산해 줘야 한다.
• 해쉬의 키로 사용되지 않는 경우이고 해쉬계산에 많은 시간이 걸린다면 지연초기화하면 좋다.

private int hashCode;

@Override
public int hashCode() {
      	int result = hashCode;
        if(result == 0) {
        int result = Integer.hashCode(areaCode);
        result = 31 * result + Integer.hashCode(areaCode);
        result = 31 * result + Integer.hashCode(areaCode);
        hashCode = result;
        }
        return result;
}

지연초기화 상황은 스레드 안정성을 고려해야 한다. 동시에 여러 쓰레드가 hashCode를 호출하면 여러 쓰레드가 동시에 계산하여 우리의 처음 의도와는 다르게 여러번 계산하는 상황이 발생할 수 있다. 그래서 지연 초기화를 하려면 동기화를 신경써주는 것이 좋다.

	private String name;
    private CountDownLatch latch;
    private int hashCode;


    @Override
    public int hashCode() {
        int result = hashCode;
        if (result == 0) {
            try {
                Thread.sleep(1000L);
                latch.countDown();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            hashCode = Objects.hash(name);
            result = hashCode;
        }
        return result;
    }
    
    
    
    @DisplayName("지연 초기화시 다수의 스레드가 동시에 접근하면 초기화 로직을 여러 쓰레드가 수행할 수 있다")
    @Test
    void test() throws InterruptedException {
        CountDownLatch latch = new CountDownLatch(5);
        MultiThreadJob job = new MultiThreadJob("processor", latch);

        new Thread(job::hashCode).start();
        new Thread(job::hashCode).start();
        new Thread(job::hashCode).start();
        new Thread(job::hashCode).start();
        new Thread(job::hashCode).start();

        latch.await();

        assertThat(job.getCount()).isEqualTo(0);
    }

 

hashCode를 계산하는데 1초가 걸린다고 가정해보자. CountDownLatch를 사용해 초기화 로직을 수행할때 countDown하도록 하고 테스트를 돌리면 다섯개의 쓰레드가 hashCode의 초기화 로직을 다 수행한 것을 확인할 수 있다.

 

3. 성능을 높인답시고 해시코드를 계산할 때 핵심 필드 생략을 하지말자.

• 핵심필드를 생략하고 적은 수의 필드만 쓰면 당연히 성능은 빨라지겠지만, 해시 품질이 나빠질것이다.
• 예를 들어 javabom.tistory.com/manage 와 javabom.tistory.com/manage/newpost 가 있다고 가정해 보자.  자바 2전의 String은 최대 16개의 문자만 뽑아내 사용해 hashCode를 사용했다. 그럴경우 위 url은 겹치는 문자가 많아 겹치는 해쉬코드 값들이 많아질 것이다.