[Java] Java Object의 equals()와 hashcode()
Object 클래스 내 메소드
equals()
hashCode()
toString()
- …
equals : 논리적으로 동등하다
- 저장하고 있는 데이터가 동일한지 확인
- 번지값을 비교하는 것이 아니다.
- 두 객체가 같은 메모리 주소를 가리키는지 비교
- equals를 오버라이딩 할 때 주의해야할 점
- 데이터를 비교하기 전에 type이 같아야 하는데
instanceof
연산자로 type을 먼저 확인한다.
- 데이터를 비교하기 전에 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)
- 자바 8 이후로는 충돌 항목이 일정 개수를 초과하면
3. Red-Black Tree
Red-Black Tree는 균형 잡힌 이진 탐색 트리로, 노드의 삽입과 삭제가 반복되더라도 트리가 크게 불균형해지지 않아 빠른 탐색이 가능하다. (충돌에 유리)
참고 자료