Java에서 중복을 제거하고 싶을 때 가장 먼저 떠오르는 자료구조는 바로 HashSet이다.
내부적으로는 어떻게 동작할까?
1. HashSet이란?
Set인터페이스를 구현한 클래스- 중복을 허용하지 않음
- 요소의 순서를 보장하지 않음
- 내부적으로는
HashMap을 기반으로 구현되어 있음
2. 내부 동작 방식
HashSet은 데이터를 저장할 때 HashMap을 활용한다.
실제로는 다음과 같이 동작한다.
Set<String> set = new HashSet<>();
set.add("apple"); // 내부적으로는 map.put("apple", DUMMY_VALUE)
- 저장할 때, 값은 HashMap의 key로 저장됨
- value에는 항상 동일한 더미 객체가 사용됨
3. 중복 제거 메커니즘
두 단계로 중복 여부를 판단한다.
1. hashCode() 확인
먼저 객체의 해시값으로 동일한 버킷인지 확인한다.
2. equals() 비교
같은 버킷에 들어온 경우, equals()로 실제 같은 객체인지 비교한다.
Set<String> set = new HashSet<>();
set.add("hashtest");
set.add("hashtest"); // 중복이라 추가되지 않음즉, hashCode가 같고 equals도 true인 경우 → 중복으로 간주해서 추가되지 않는다.
4. 속도가 빠른 이유
-
내부 구조가 HashMap이기 때문에 평균 시간 복잡도는 O(1)
-
저장 시 해시 기반으로 버킷을 찾고, equals()로만 최종 비교 → 연산 속도 매우 빠름
-
특히 대용량 데이터 처리 시 효율적
5. 정리
- HashSet은 내부적으로 HashMap을 사용하여 구현됨
- 중복 제거 과정은 hashCode() → equals() 순서로 이루어짐
- 평균 시간 복잡도는 O(1) → 성능 우수
