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

[tonykang22]

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

핵심 정리: hashCode 규약

• equals 비교에 사용하는 정보가 변경되지 않았다면 hashCode는 매번 같은 값을 리턴해야 한다. (변경되거나, 애플리케이션을 다시 실행했다면 달라질 수 있다.)
• 두 객체에 대한 equals가 같다면, hashCode의 값도 같아야 한다.
• 두 객체에 대한 equals가 다르더라도, hashCode의 값은 같을 수 있지만 해시 테이블 성능을 고려해 다른 값을 리턴하는 것이 좋다.
  • 큰 문제가 발생하는 것은 아니지만 성능이 O(N)으로 떨어질 수 있다.

예시 코드

같은 인스턴스인데 다른 hashCode를 갖는 경우

number1.hashCode()와 number2.hashCode()는 다르다. 그렇기 때문에 System.out.println(s);에서는 콘솔에 null이 찍히게 된다.

• hash를 이용할 때 어떻게 동작하는지를 생각해볼 필요가 있다.
  • 넣을 때는 hash bucket을 통해 hashCode 만든다.
  • 꺼낼 때는 hashCode를 먼저 가져오고, hash에 해당하는 bucket에 들어있는 Object를 꺼내온다.
  • 예시의 Map의 key에 해당하는 인스턴스의 hashCode가 다르기 때문에 없는 것으로 나온다.

public class HashMapTest {

    public static void main(String[] args) {
        Map<PhoneNumber, String> map = new HashMap<>();

        PhoneNumber number1 = new PhoneNumber(123, 456, 7890);
        PhoneNumber number2 = new PhoneNumber(123, 456, 7890);

        // true
        System.out.println(number1.equals(number2));

        System.out.println(number1.hashCode());
        System.out.println(number2.hashCode());

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

        String s = map.get(new PhoneNumber(123, 456, 7890));

        // null
        System.out.println(s);
    }
}

다른 인스턴스인데 같은 hashCode를 갖는 경우

number1.hashCode()와 number2.hashCode()는 동일한 값을 갖는다.

• Hash collision이 일어나게 될 것이고,

  • 넣을 때는, hash bucket에 linked list로 넣게 된다.
  • 꺼낼 때도 linked list로 꺼내와서 equals로 전부 비교하게 된다.
    • hash 를 사용하는 이점이 사라진다. (O(1) -> O(N))

      
      public class HashMapTest {

  public static void main(String[] args) { Map<PhoneNumber, String> map = new HashMap<>();

  PhoneNumber number1 = new PhoneNumber(123, 456, 7890);
  PhoneNumber number2 = new PhoneNumber(456, 789, 1111);
  
  // false
  System.out.println(number1.equals(number2));
  
  System.out.println(number1.hashCode());
  System.out.println(number2.hashCode());
  
  map.put(number1, "keesun");
  map.put(number2, "whiteship");
  
  String s = map.get(number2);
  
  // whiteship
  System.out.println(s);

  } }

  
  <br>

핵심 정리: hashCode 구현 방법

1. 핵심 필드 하나의 값의 해쉬값을 계산해서 result 값을 초기화 한다.
2. 기본 타입은 Type.hashCode 참조 타입은 해당 필드의 hashCode 배열은 모든 원소를 재귀적으로 위의 로직을 적용하거나, Arrays.hashCode result = 31 * result + 해당 필드의 hashCode 계산값
3. result를 리턴한다.

예시 코드

전형적인 hashCode()

• 왜 31인가? (일반적으로 사용하는 31)
  • 홀수를 사용해야한다. (짝수를 사용하면 0이 생기면서 왼쪽으로 밀리며 수가 많이 날아갈 수 있기 때문이다.)
  • 어느 두 사람(?)이 사전에 들어있는 모든 단어를 hash collision 을 알아보기 위해 실험을 해서 얻은 최적의 결과였기 때문이다.
• 그러나 이런 방식으로 직접 사용하지는 않는다.
  • Object.hash()만 사용해도 되기 때문이다.
  • 그럼에도 이러한 방법은 성능이 조금 아쉽기는 하다.

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

핵심 정리: hashCode 구현 대안

• 구글 구아바의 com.google.common.hash.Hashing
• Objects 클래스의 hash 메서드
• 캐싱을 사용해 불변 클래스의 해시 코드 계산 비용을 줄일 수 있다.
  • 불변 클래스인 경우 필드에 hash 값을 둘 수 있다.
  • 처음 hashCode()가 호출될 때 계산을 해두는 방식
  • 그러나 주의할 점은 스레드 안정성을 고려해야 한다.
• Lombok의 @EqualsAndHashCode를 사용할 수 있다.
  • 한 줄이라도 직접 작성했다면 당연히 test도 해야한다.
  • Lombok을 사용한다면 직접 test까지 할 필요가 없어진다.

예시 코드

Guava Library

• 성능을 더 끌어올릴 수 있도록 도와주는 라이브러리

  • 오직 hashCode()를 위해 라이브러리를 추가하는 것은 고민이 필요할 것으로 생각된다.

    
    @Override
    public int hashCode() {
    return Hashing.goodFastHash(32)
            .hashObject(this, PhoneNumberFunnel.INSTANCE)
            .hashCode();
    }

  private static class PhoneNumberFunnel implements Funnel {

  private static final PhoneNumberFunnel INSTANCE = new PhoneNumberFunnel();
  
  @Override
  public void funnel(PhoneNumber from, PrimitiveSink into) {
      into.putShort(from.areaCode).putShort(from.prefix).putShort(from.lineNum);
  }

  }

핵심 정리: 주의 할 것

• 지연 초기화 기법을 사용할 때 스레드 안전성을 신경써야 한다. (아이템 83)
• 성능 때문에 핵심 필드를 해시코드 계산할 때 빼면 안 된다.
• 해시코드 계산 규칙을 API에 노출하지 않는 것이 좋다.

완벽 공략

• p68, 연결 리스트
• p70, 해시 충돌이 더욱 적은 방법을 꼭 써야 한다면...
• p71, 클래스를 스레드 안전하게 만들도록 신경 써야 한다.

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

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

• 자바 8에서 해시 충돌시 성능 개선을 위해 내부적으로 동일한 버켓에 일정 개수 이상(8개로 알고 있음)의 엔트리가 추가되면, 연결 리스트 대신 이진 트리(Red-Black-Tree)를 사용하도록 바뀌었다.
  • https://dzone.com/articles/hashmap-performance
• 연결 리스트에서 어떤 값을 찾는데 걸리는 시간은?
  • O(N)
  • 추가 (ArrayList도 있는데 LinkedList를 사용한 이유가 있을까?)
    • 어차피 탐색에 걸리는 시간은 동일하기 때문에
    • 공간이라도 줄이기 위해 선택한게 아닐까?
• 이진 트리에서 어떤 값을 찾는데 걸리는 시간은?
  • O(logN)

완벽 공략 28. 스레드 안전

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

• 가장 안전한 방법은 여러 스레드 간에 공유하는 데이터가 없는 것!
• 공유하는 데이터가 있다면:
  • Synchronization
  • ThreadLocal
    • 스레드 내에서만 공유할 수 있는 로컬 데이터
    • 스프링에서 트랜젝션을 사용할 때 ThreadLocal을 사용한다.
  • 불변 객체 사용
    • 다른 스레드에서 바뀔 여지가 없기 때문에 안전하다.
  • Synchronized 데이터 사용
    • Synchronized한 Collection 사용
      • e.g. HashMap(Thread safe하지 않다), HashTable(Thread safe하다)
  • Concurrent 데이터 사용
    • e.g. 값을 읽어가기만 하는 경우이고 동시에 스레드들이 접근해도 문제가 없는 경우
  • ...

예시 코드

사실 아래의 코드에서는 멀티스레드에 안전하지는 않으나, 계산 값이 언제나 동일하기 때문에 크게 문제는 일어나지는 않으나, 여전히 문제는 문제이기 때문에 예시 코드에서 접하게 되었다.

   private int hashCode;

    @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);
                this.hashCode = result;
            }
            return result;
        }
    }

• 공유되는 코드를 synchronized 키워드로 감싸는 방법으로 안전하게 사용할 수 있다.

  • 동시 다발적으로 여러 스레드가 접근하는 경우, 즉 많이 호출되는 경우에는 성능 문제가 생길 수 있다.
  • synchronized 범위를 작게 가져가면 성능 문제를 그나마 최소화 할 수 있다.
    • public synchronized int hashCode() 가 아니라, 아래와 같이 메소드 내 걸게 된다면 성능 문제가 해소될 수 있다.
    • double checked locking : synchronized 밖에서 한번, 안에서 한번, 총 두번 확인하는 방법
  • volatile : 캐시에 저장된 데이터를 불러올 때, 다른 스레드가 업데이트 했지만, 예전의 데이터(유효하지 않은 데이터)를 가져오는 경우가 있을 수 있는데, volatile을 사용하면 메인 메모리에 저장된 데이터를 가져오기 때문에 가장 최근의 데이터를 가져올 수 있다.
    • synchronized와 함께 자주 쓰인다.

      
      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);
          this.hashCode = result;
      }
      return result;
  }

  }