장장 3.5시간동안 고민하고 찾아봤던 나의 기록을 정리하고자 한다.
알고리즘 문제를 풀던 도중, 의문이 생겨 레퍼런스를 조사하고 정리한 내용이다.
가장 큰 의문의 시발점은 다음과 같았다.
"기본형 및 String은 ==나 equals로 참 거짓을 판단할 수 있는데, 내가 만든 Class 객체들도 이걸 사용할 수 있을까?"
결론부터 말하자면 가능하다. Object에서 기본적으로 지원하는 equals 메서드를 자체적으로 Override하면 된다.
HashSet -> HashMap -> contains~() -> getNode() -> equals and Hash을 통해 비교하기 때문
내가 궁금했던 HashSet이나 HashMap의 자료구조에서 사용하는 contains도 결국에는 equals와 hashcode를 기반으로 동작한다.
메서드를 확인해본 결과, HashSet도 내부 구조에서 자체적으로 HashMap을 가지고 있었고, HashMap은 ContainsKey 메서드를 통해 비교하며, 해당 메서드 내부에는 이를 판단하는 'getNode'가 존재함을 확인할 수 있었다.
/**
* Implements Map.get and related methods.
*
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & (hash = hash(key))]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
/**
* Returns {@code true} if this map contains a mapping for the
* specified key.
*
* @param key The key whose presence in this map is to be tested
* @return {@code true} if this map contains a mapping for the specified
* key.
*/
public boolean containsKey(Object key) {
return getNode(key) != null;
}
동작 구조 : HashSet
HashMap, Set 등에서 객체를 Key로 사용할 때, Java에서는 두 가지 중요한 메소드인 equals()와 hashCode()를 기반으로 객체의 동등성을 판단한다.
기본적으로 Java에서 제공하는 Object 클래스의 equals() 메소드는 두 객체가 동일한 메모리 주소를 가리키는지를 확인한다.
즉, 두 객체가 정확히 같은 인스턴스인지를 equals로 검사하며, Hash- 구조에서 hashCode() 메소드는 객체의 해시 코드를 더해 동시에 판단하는 것이다.
다음과 같은 예제를 만들어 테스트해보았다.
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws Exception {
//1. Hash 비교
HashSet<Pos> hashSet = new HashSet<>();
Pos pos = new Pos(1, 1); //Custom 객체 선언
hashSet.add(pos);
if(hashSet.contains(pos)) System.out.println("equals and hash compare"); //정상적으로 동작
Pos anotherPos = new Pos(1, 1); //값이 같은 다른 객체 선언
if(hashSet.contains(anotherPos)) System.out.println("compare?");
//hash값이 다르지 않아 동작하지 않음..?
}
}
class Pos {
int r, c;
public Pos() {}
public Pos(int r, int c) {
this.r = r;
this.c = c;
}
//1. equals 오버라이드
@Override
public boolean equals(Object obj) {
System.out.println("디버그용 equals 호출");
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Pos pos = (Pos) obj;
return r == pos.r && c == pos.c;
}
//2. HashCode 오버라이드 -> HashMap, HashSet 등 hash값 비교 ..
@Override
public int hashCode() {
System.out.println("디버그용 hashcode 호출");
return Objects.hash(r, c);
}
}
그런데 넣지도 않은 anotherPos가 contains에 포함된다?
pos 인스턴스와 anotherPos 인스턴스는 내부 값은 같지만, 다른 객체니까 해시코드 자체는 다를 것(혹은 없을 것) 아닌가?
그렇게 생각했기에 이후 compare?은 출력되지 않을 것이라고 예상했다.
하지만 실제 결과는 달랐다.
HashSet에서 객체를 추가하거나 검색할 때, 두 메소드 모두 중요한 역할을 한다.
1. hashCode() 메소드는 객체를 해시 테이블 내의 특정 버킷에 할당하는 데 사용되며,
2. equals() 메소드는 그 버킷 내에서 객체의 동등성을 확인하는 데 사용된다.
여기서 중요한 부분을 파악했다.
원인 : hashCode()는 동일 해시 값으로 계산될 수 있다.
여기서 주목할 점은 hashCode() 메소드가 객체의 '해시코드'를 계산하는 것이지, 그 객체에 대한 '해시코드'를 저장하는 것이 아니라는 점이다.
그래서 pos와 anotherPos가 같은 내부 상태(r = 1, c = 1)를 가지고 있기 때문에, 같은 해시코드가 계산되고(!)
contains() 메서드에서 동일하게 여겨 값을 반환하게 된 것이다.
실제 pos와 anotherPos의 해시코드는 동일한 '993'임을 확인할 수 있었다.
디버그 출력은 왜 저렇게 되나요?
1. 첫 번째 hashCode() 호출 (pos 추가 시)
hashSet.add(pos)를 호출할 때, HashSet은 먼저 pos 객체의 hashCode()를 계산한다.
(해시코드를 계산하여 해시 테이블의 버킷에 저장하는 데 사용된다.)
아직 해시 테이블 내에 pos와 동일한 해시코드를 가진 다른 객체가 없으므로, equals() 메소드는 호출되지 않는다.
2. 두 번째 hashCode() 호출 (hashSet.contains(pos) 실행 시)
contains 호출 시 pos 객체의 hashCode()를 호출하여 해시코드를 계산한다. (여기서 출력)
이후, 해당 해시코드에 해당하는 버킷을 찾는다.
이미 pos 객체가 버킷에 있고, pos 객체 자체를 검사하고 있기 때문에 equals() 메소드는 필요 없어 호출되지 않는다.
< 최적화와 equals() 호출 생략 >
특정 조건에서 HashSet은 equals() 호출을 생략할 수 있다.
버킷에 객체가 단 하나만 있고, 그 객체가 contains() 메소드에 전달된 객체와 동일한 경우(즉, 동일한 참조를 가지는 경우), HashSet은 equals() 호출을 생략하고 바로 true를 반환할 수 있다. 이 부분에 해당하는 것이라고 추측했다.
3. 세 번째 hashCode() 호출 (hashSet.contains(anotherPos) 실행 시)
hashSet.contains(anotherPos)를 호출할 때, anotherPos 객체의 hashCode()를 호출하여 해시코드를 계산한다. (출력!)
이 때, 계산한 hashCode의 버킷에 pos 객체가 존재하기 때문에, HashSet은 버킷 내의 객체인 pos와 anotherPos를 equals() 메소드로 비교한다. 이 때 equals() 메소드가 호출된다.
=> 즉, 해시코드 계산 후 해시 테이블의 버킷을 보니, 다른 객체가 이미 존재했다. 그래서 equals를 통해 비교한 것.
버킷에 동일한 해시코드를 가진 여러 객체가 존재한다면, HashSet은 이들 각각을 이미 있는 pos 객체와 equals() 메소드를 사용하여 비교하기 때문이다.
해시코드도 같고, equals도 true인 완벽하게 똑같지만, 다른 인스턴스다!
anotherPos가 HashSet에 없지만, 같은 상태를 가진 pos가 HashSet에 이미 존재하기 때문에
anotherPos를 포함하고 있다고 판단(!)한 것이다.
메서드는 다음과 같이 동작한다. 아래 구문의 contains(anotherPos)를 예시로 들어보자.
1. HashSet의 contains() 메소드를 호출한다.
2. HashSet은 먼저 anotherPos의 hashCode() 메소드를 호출하여 해시코드를 얻고, 그 해시코드에 해당하는 *버킷(Buckit)을 찾는다.
3. 버킷 내 동일 해시 코드값에 존재하는 모든 객체와 anotherPos를 equals() 메소드로 비교한다.
4. pos 객체는 버킷에 추가되어 있고, anotherPos가 pos와 동일한 상태이기 때문에, equals() 비교에서 true를 반환한다.
5. 따라서 HashSet은 anotherPos가 집합에 포함되어 있다고 판단한다.
*버킷 : 해시 테이블 내에서 객체를 저장하는 물리적인 공간
해시 테이블은 데이터를 저장하고 검색하는 효율적인 방법을 제공하며, 이를 위해 해시 함수를 사용해 각 객체를 특정 버킷에 할당한다.
결론 : 버킷과 해시 충돌, equals == true. 이것이 Contains 비교 문제(?)를 일으켰다.
사실 문제까지는 아니다. 이것이 정상이다.
두 객체(pos, anotherPos)는 분명 다르게 선언한 인스턴스지만, 내용적으로 동일하다면 동일하게 취급되는 것이 정상이다.
그저 이런 테스트를 통해 나온 케이스가 내가 처음 경험해 본 것이었기에 신기하게 느껴졌다.
만약 굳이 pos와 anotherPos를 비교해야 한다면, 아마 다른 식별자를 추가해야 할 것이다.
해시 충돌?
동일한 해시코드를 가진 여러 객체가 발생하는 것을 '해시 충돌'이라고 한다.
지금 예시와 딱 맞는 것이라고 생각이 된다. 해시 충돌이 발생하면, 여러 객체들이 동일한 해시 코드를 갖게 되고, 이 때문에 같은 버킷(bucket)에 저장된다.
pos와 anotherPos가 같은 해시코드를 갖는 것 역시 해시 충돌의 일종일 것이다.
이 경우 두 객체는 hashCode() 메소드에 의해 동일한 해시코드를 반환하므로, HashSet 내부의 동일한 버킷에 할당되었기 때문이다.
지금의 경우 hashCode와 equals == true인 완전 동일한 객체지만, 만약 다른 객체가 동일 해시코드를 가진다고 해도, 사실 계산 자체는 된다. 하단에 자세한 내용을 서술하였다.
자바에서는 일반적으로 버킷에 연결 리스트 방식을 사용한다.
Java의 HashMap과 HashSet은 주로 체이닝 방식을 사용한다고 한다.
즉, 같은 해시 코드를 가진 객체들은 같은 버킷의 연결 리스트에 저장된다.
이 때문에, hashCode() 메소드의 구현이 중요한데, 해시 코드가 고르게 분포되도록 해야 효율적인 성능을 얻을 수 있을 것이다.
본 예제에서는 단순히 r과 c를 통해 만들어서, 동일한 해시코드가 나왔다.
해시 코드가 고르게 분포되지 않을 경우, 많은 객체들이 몇몇 버킷에 집중되어 성능 저하가 발생할 수 있다.
동작 자체는 정상적으로 이루어질 테지만, 같은 해시코드 버킷에 여러 객체들이 들어가니까 모든 객체를 equals로 비교하고, 시간 복잡도가 일반적인 O(1)에서 상당히 비효율적으로 바뀌게 된다는 거다!
pos와 anotherPos는 사실 동일 객체로 생각해도 되니 상관이 없지만, 해시코드는 같은데 내용물은 다른 객체들이 하나의 버킷에 집중된다면, 많은 시간적 손실이 날 것이다.
정말 유익한 고찰이었던 것 같다! 해시 구조에 대한 이해가 늘었다. :)
'CS study > java' 카테고리의 다른 글
| [디자인 패턴]프록시(Proxy) 패턴 설명과 예시 (0) | 2024.02.26 |
|---|---|
| 예시를 통해 알아보는 Java의 Call by Value, Call by Reference 개념 (1) | 2024.01.08 |
| URI/URL/URN, Restful 원칙 (1) | 2023.12.15 |
| SOLID 5원칙에 대해 (1) | 2023.12.14 |
| [Java] 인터페이스와 추상 메서드, 일반 메서드 (0) | 2023.10.24 |
