[Java] Java Object의 equals()와 hashcode()

Object 클래스 내 메소드

• equals()
• hashCode()
• toString()
• …

equals : 논리적으로 동등하다

• 저장하고 있는 데이터가 동일한지 확인
  • 번지값을 비교하는 것이 아니다.
• 두 객체가 같은 메모리 주소를 가리키는지 비교
• equals를 오버라이딩 할 때 주의해야할 점
  • 데이터를 비교하기 전에 type이 같아야 하는데 instanceof 연산자로 type을 먼저 확인한다.

hashCode

• 객체의 메모리 번지를 이용해 해시코드를 만들어서 리턴
• 해시코드 : 객체를 식별할 하나의 정수값
  • 메모리 주소를 리턴하는 것이 아님
  • 해시 기반 컬렉션에서 객체를 빠르게 조회하고 관리

꼬리질문

• 자바에서는 개발자가 직접 메모리에 접근해서 해싱할 수 있는지?
  • 일반적으로 자바는 메모리에 직접 접근할 수 없다.
    • 이는 안전성과 플랫폼 독립성을 위해 자바가 제공하는 특성이다
  • 해싱은 hashCode 메서드를 오버라이드하여 제어해야 하며, 객체의 데이터 필드를 바탕으로 직접 해시 값을 계산해 반환할 수 있다.

hashCode를 잘못 오버라이딩 하는 경우

• HashMap 과 같은 해시 기반 콜렉션에서 버킷에 객체들이 고르게 분배되지 않게 되어 성능이 저하될 수 있다. 모든 객체가 같은 해시 코드를 반환하면 HashMap은 모든 객체를 단일 버킷에 저장(해싱 충돌)하게 된다.
• ⇒ 조회 성능 O(1) → O(n)

꼬리질문

• 잘못 오버라이딩 하는 경우에는 어떤 경우가 있나요?

  • 모든 객체가 동일한 해시 값을 반환하는 경우 → O(n)

      @Override
      public int hashCode() {
          return 1; // 잘못된 hashCode 구현 - 모든 객체가 동일한 해시 값을 가짐
      }
    

  • 필드 값이 변할 수 있는 경우를 hashCode 계산에 포함한 경우 → car 객체를 찾을 수 없다.

      @Override
      public int hashCode() {
          return model.hashCode() + year; // year 필드는 바뀔 수 있음
      }
    

  • 고유하지 않은 값을 해시코드로 사용한 경우 (name, age)

HashMap의 내부 데이터 관리 자료구조

• HashMap의 빠른 탐색 성능은 내부 구조가 해싱을 활용하여 해시 버킷과 LinkedList, Red-Black Tree로 이루어져 있기 때문이다.

1. 해시 버킷(Hash Bucket)

HashMap은 저장할 값의 키를 해싱 함수로 변환해 해시 버킷이라는 배열의 인덱스로 매핑한다. 이때 키의 hashCode() 메서드를 호출해 나온 해시 값을 배열 인덱스로 매핑하여 빠르게 해당 위치를 찾을 수 있다.

충동 해결 방식

2. LinkedList

해시 함수는 다수의 키를 동일한 인덱스로 매핑할 수 있어 충돌이 발생할 수 있습니다. 이를 해결하기 위해 동일한 인덱스에 여러 개의 항목(next)을 연결 리스트로 관리한다. 충돌이 발생한 경우 해당 버킷에 LinkedList를 두어 값들을 저장하게 되며, 이 LinkedList를 탐색하여 올바른 값을 찾는다.

• LinkedList의 한계 : 저장되는 항목이 많아지면 LinkedList 탐색 속도가 느려진다.
  • 자바 8 이후로는 충돌 항목이 일정 개수를 초과하면 LinkedList 대신 Red-Black Tree로 전환한다.
  • 특정 버킷의 노드 개수가 8개 이상이 되면 자동으로 Red-Black Tree로 변환하여 탐색 속도를 O(log n)으로 유지한다. O(n) → O(log n)

3. Red-Black Tree

Red-Black Tree는 균형 잡힌 이진 탐색 트리로, 노드의 삽입과 삭제가 반복되더라도 트리가 크게 불균형해지지 않아 빠른 탐색이 가능하다. (충돌에 유리)

---

참고 자료

자바 기술 면접 대비하기 - 1편

2. Java 자바 [API] - Object 클래스, Object 클래스의 메소드 1

[자료구조] HashMap 파헤치기 1 (Linked List + Red Black Tree)