JAVA

객체 판별

whyWhale 2021. 10. 18. 19:38

Equals를 재정의하려거든 Hashcode도 재정의하라

🔎hash table 간략 설명
- 해쉬 테이블이란 ? - key,value 쌍으로 이루어진 자료구조
  • 충돌 처리 방식에 따른 알고리즘
    • Separate Chaining 방식
      • : 충돌이 발생하면 LinkedList에 노드를 추가하는 방식으로 삽입 삭제 가 간편하고 문제가 없다.(추가적 메모리 사용)
        • LinkedList 뿐만 아니라 Tree를 사용함으로 탐색 성능을 높일 수 있다.
          • 노드가 8개 이하일 경우 LinkedList를 사용하고 8개 이상으로 늘어날 때 Tree구조로 데이터 자료구조를 변경한다.
    • Open Addressing 방식
      • 고정 크기의 배열을 사용하는 방식으로 Separate Addressing 에 반해 메모리가 덜 사용된다
      • Linear Probing
        • 고정크기의 배열 크기로 모듈로(%)연산을 사용한 해시 함수 충돌시 해당 버킷뒤로 순차 탐색을 하면서 비어있는 공간에 삽입하는 방식
        • *삭제시 유의점
          • 삭제를 할 경우 충돌에 의해서 뒤로 저장된 데이터 검색이 안될 수 있다. 그래서 이런 문제를 방지하기 위해 데이터 삭제후 Dummy Node 를 삽입함으로써 실제 데이터가 없더라도 연속적으로 검색이 가능하도록 문제를 해결 할 수 있다. 하지만 Dummy Node의 개수가 무한히 늘어난다면 비효율적인 문제가 발생한다. 그래서 일정 개수를 넘었을 때 새로운 고정 크기의 배열을 만들어 Hash를 리빌딩함으로써 Dummy Node를 주기적으로 없애 성능을 유지 할 수 있다.

  • 좋은 해시함수란?

    - 데이터를 고르게 분포하여 충돌을 최소화 할 수 있는 함수.
- 종류
    - String 
    - Char [] ch
    ....

  • Cache를 이용한 성능 향상

    자주 hit하는 데이터에 대해서 바로 데이터를 찾게함으로써 성능을 간단하게 향상 시킬 수 있다.

  • java에서의 HashMap 은 실제로 Map 클래스에서도 array resize를 사용하고 있다.

해쉬 코드를 재정의 하지 않을 때

  • 해쉬 코드를 정의 하지 않으면 계속 새로운 데이터의 삽입이 발생한다.
  • 결국 조회해야할 대상이 전혀 존재하지 않는 NULL 값이 반환된다.
  • 해쉬 코드 재정의( 동일한 상수값 반환 )
    • 모든 객체에 대해 똑같은 해시코드를 반환할 시 모든 객체가 같은 버킷에 담겨 LinkedList 처럼 동작
    • 평균 수행시간 O(1) 에서 O(N)으로 느려져 성능이 매우 낮아지고 overFlow 위험이 존재하여 데이터의 누락이 발생할 수 있다.

hashcode를 편하게 만들어 주는 모듈

1. Objects.hash() : 내부적으로 AutoBoxing이 일어나 성능이 떨어진다.
2. Lombok의 @EqualsAndHashCode
3. Google의 @AutoValue

hashcode를 재정의 할 때 주의 할 점!

  • 불변 객체에 대해서는 hashcode 생성비용이 많이 든다면, hashcode를 캐싱하는 것도 고려한다
    • 스레드 안전성까지 고려해야 한다.
  • 성능을 높인답시고 hashcode를 계산할 떄 핵심필드를 생략해서는 안된다.
    • 속도는 빨라지겠지만, hash품질이 나빠져 해시테이블 성능을 떨어뜨릴 수 있다 (Hashing Collision)
  • hashcode 생성규칙을 API사용자에게 공표하지 말자
    • 그래야 클라이언트가 hashcode값에 의지한 코드를 짜지 않는다.
    • 다음 릴리즈 시, 성능을 개선할 여지가 있다.