[JAVA] Java HashSet의 중복 제거 원리 : hashCode()와 equals()의 깊은 이해

HashSet의 중복 제거 원리

 

자바에서 HashSet은 중복을 허용하지 않는 데이터를 관리할 때 가장 먼저 선택되는 강력한 도구입니다. 하지만 단순히 "중복이 안 된다"는 현상만 알고 사용하는 것과, 내부에서 어떤 메커니즘을 통해 객체의 동일성을 판단하는지 이해하는 것은 천차만별의 결과를 낳습니다. 특히 커스텀 객체를 HashSet에 담을 때 발생할 수 있는 논리적 오류를 방지하기 위해서는 hashCode()와 equals()의 상관관계를 명확히 알아야 합니다. 이 글에서는 JVM 내부에서 HashSet이 데이터를 저장하고 비교하는 과정을 단계별로 분석하여, 데이터 무결성을 지키는 핵심 비법을 공유합니다.

---

1. HashSet의 정체: 사실은 HashMap이다?

많은 초급 개발자가 간과하는 사실 중 하나는 HashSet이 내부적으로 HashMap을 사용하여 데이터를 관리한다는 점입니다. HashSet.add() 메서드를 호출하면, 내부적으로는 전달받은 객체를 HashMap의 Key로 저장하고, Value에는 의미 없는 더미 객체(PRESENT)를 채워 넣습니다. 따라서 HashSet의 중복 제거 로직은 곧 HashMap의 Key 중복 확인 로직과 동일하며, 이는 해싱(Hashing) 기법을 기반으로 동작합니다.

---

2. 중복 확인의 2단계 알고리즘

HashSet에 객체를 추가하려고 할 때, 자바는 효율성을 위해 다음의 2단계 검증 과정을 거칩니다. 모든 데이터를 일일이 비교하는 $O(n)$의 비효율을 피하기 위함입니다.

1단계: hashCode() 비교 (해시 코드 확인)

먼저 추가하려는 객체의 hashCode() 메서드를 호출하여 해시값을 얻습니다. 이 해시값은 객체가 저장될 버킷(Bucket)의 주소를 결정합니다. 만약 이 해시값이 기존 데이터들과 겹치지 않는다면, 자바는 즉시 "다른 객체"로 판단하고 데이터를 저장합니다.

2단계: equals() 비교 (실제 값 확인)

만약 해시값이 같은 데이터가 이미 존재한다면(해시 충돌, Hash Collision), 자바는 equals() 메서드를 호출합니다. 해시값이 같더라도 실제 데이터가 다를 수 있기 때문입니다. equals()의 결과가 true라면 중복으로 판단하여 저장을 거부하고, false라면 같은 버킷 내에 연결 리스트(또는 트리) 형태로 데이터를 추가합니다.

---

3. hashCode()와 equals()의 비교 분석

객체의 동일성을 판단하는 두 메서드의 역할과 차이점을 표로 정리해 보았습니다.

비교 항목	hashCode()	equals()
핵심 역할	객체를 식별할 정수값(해시코드) 생성	두 객체의 논리적 동등성 비교
비교 시점	1차 필터링 (빠른 검색)	2차 정밀 검사 (충돌 시 실행)
반환 타입	int	boolean
성능적 특징	산술 연산으로 매우 빠름	필드 값을 일일이 비교하므로 상대적 느림

---

4. 개발 시 반드시 지켜야 할 "불변의 법칙"

커스텀 클래스(예: User, Product 등)를 HashSet에서 정상적으로 작동시키려면 반드시 두 메서드를 동시에 오버라이딩(Overriding)해야 합니다.

중요 규칙:
1. equals()가 true인 두 객체는 반드시 같은 hashCode()를 가져야 합니다.
2. 하지만 hashCode()가 같다고 해서 반드시 equals()가 true일 필요는 없습니다. (해시 충돌 허용)

만약 equals()만 오버라이딩하고 hashCode()를 방치하면, 논리적으로 같은 객체임에도 불구하고 해시값이 달라 서로 다른 버킷에 저장되어 중복 제거가 작동하지 않는 버그가 발생합니다.

---

5. 결론: 효율적인 데이터 관리의 시작

Java HashSet의 중복 제거는 "hashCode()로 빠르게 거르고, equals()로 정밀하게 확인한다"는 전략을 취하고 있습니다. 이를 통해 수만 개의 데이터 사이에서도 $O(1)$에 가까운 속도로 중복을 찾아낼 수 있는 것입니다. 여러분이 작성하는 클래스에 이 원리를 올바르게 적용한다면, 데이터의 무결성과 성능이라는 두 마리 토끼를 모두 잡을 수 있습니다.

---

내용 출처 및 참고 자료:

• Oracle Java 17 Documentation: Class HashSet & Object.hashCode()
• Joshua Bloch, "Effective Java 3rd Edition" - Item 11: Always override hashCode when you override equals
• Baeldung: Guide to Java HashSet
• GeeksforGeeks: Internal working of HashSet in Java