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

핵심 정리1 - hashCode 규약

- equals 비교에 사용하는 정보가 변경되지 않았다면 hashCode는 매번 같은 값을 리턴해야 한다.

   ( 변경되거나, 애플리케이션을 다시 실행했다면 달라질 수 있다. )

- 두 객체에 대한 equals가 같다면, hashCode의 값도 같아야 한다.

- 두 객체에 대한 equals 가 다르더라도, hashCode의 값은 같을 수 있지만 해시 테이블 성능을 고려해 다른 값을 리턴하는 것이 좋다.

 

해시충돌

// 다른 인스턴스인데 같은 hashCode를 쓴다면? - 해시충돌 
System.out.println(number1.equals(number2));	// false
System.out.println(number1.hashCode());
System.out.println(number2.hashCode());

map.put(number1, "keesun");
map.put(number2, "whiteship");

String s = map.get(number2);
System.out.println(s);

- 해시 충돌이 일어나면 해시 버킷에 들어 있는 링크드 리스트를 꺼내서 get을 할 때 equals 로 비교해서 값을 들고 온다.

- 해시 코드가 같다면 알고리즘의 효율성이 떨어지게 된다.

 

핵심 정리2 - hashCode 구현 방법

@Overrid public int hashCode() {
    int result = Short.hashCode(areaCode);	// 1
    result = 31 * result + Short.hashCode(prefix);	// 2
    result = 31 * result + Short.hashCode(lineNum);	// 3
    return result;
}

1. 핵심 필드 하나의 값을 해쉬값을 계산해서 result 값을 초기화 한다.

2. 기본 타입은 Type.hashCode

    참조 타입은 해당 필드의 hashCode

    배열은 모든 원소를 재귀적으로 위의 로직을 적용하거나, Arrays.hashCode

    result = 31 * result + 해당 필드의 hashCode 계산값

3. result 를 리턴한다.

 

- 롬복의 @EqualsAndHashCode를 사용하는 것을 선호한다. - 따로 테스트를 코드를 짜지않아도 되는 검증된 방법

 

 

완벽  공략

- p68, 연결 리스트

- p70, 해시 충돌이 더욱 적은 방법을 꼭 써야 한다면...

- p71, 클래스를 스레드 안전하게 만들도록 신경 써야 한다.

완벽 공략27 - 해시맵 내부의 연결 리스트

내부 구현은 언제든지 바뀔 수도 있다.

- 자바 8에서 해시 충돌시 성능 개선을 위해 내부적으로 동일한 버켓에 일정 개수 이상의 엔트리가 추가되면, 연결 리스트 대신 이진 트리를 사용하도록 바뀌었다.

- 연결 리스트에서 어떤 값을 찾는데 걸리는 시간은?

    ㆍO(N)

- 이진 트리에서 어떤 값을 찾는데 걸리는 시간은?

    ㆍO(logN)

 

완벽 공략28 - 스레드 안전

멀티 스레드 환경에서 안전한 코드, Thread-safety

- 가장 안전한 방법은 여러 스레드 간에 공유하는 데이터가 없는 것!

- 공유하는 데이터가 있다면:

    ㆍSynchronization

// 해시코드를 지연 초기화하는 hashCode 메서드 - 스레드 안정성까지 고려해야 한다. (71쪽)
private int hashCode;   // 자동으로 0으로 초기화된다.

@Override
public synchronized 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;
}

private volatile int hashCode;   // 자동으로 0으로 초기화된다.	// 메인메모리 참조

@Override
public int hashCode() {
    if(this.hashCode != 0) {
        return hashCode;
    }

    synchronized (this) {	// 이 순간에 쓰레드가 두개이면 하나씩
        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;
    }
}

    ㆍThreadLocal

    ㆍ불변 객체 사용

    ㆍSynchronized 데이터 사용

    ㆍConcurrent 데이터 사용

    ㆍ...