Q. HashSet의 내부 동작 방식과 중복 제거 메커니즘을 설명하고, HashSet이 효율적인 중복 체크를 할 수 있는 이유를 설명해주세요.
A.
🔍 Java HashSet의 내부 동작 원리와 중복 제거 메커니즘
Java 컬렉션 중 하나인 HashSet은 중복 없는 데이터 집합(Set)을 저장할 수 있도록 설계된 자료구조입니다.
이 글에서는 HashSet의 내부 구조와 중복 제거 방식, 그리고 중복 체크가 효율적인 이유를 정리해봅니다.
📦 HashSet이란?
HashSet은 Set 인터페이스를 구현한 클래스입니다.
내부적으로 HashMap을 기반으로 동작합니다.
중복을 허용하지 않고, 순서를 보장하지 않으며, null 값은 하나만 허용합니다.
Set<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
set.add("apple"); // 중복이므로 무시됨
System.out.println(set); // [apple, banana] (순서는 보장되지 않음)🧠 내부 동작 원리
✅ 핵심: HashMap을 사용
HashSet은 내부에서 데이터를 HashMap의 key로 저장합니다. 값(value)은 모두 동일한 dummy 객체(PRESENT)입니다.
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
add(E e) 메서드는 다음과 같이 작동합니다:public boolean add(E e) {
return map.put(e, PRESENT) == null;
}즉, HashSet.add(e)는 사실상 HashMap.put(e, dummy)와 동일합니다.
✅ 내부 배열 사용
HashMap은 내부적으로 초기 크기 16의 배열(Node<K,V>[] table)을 사용하며, 해시값에 따라 이 배열의 인덱스에 데이터를 배치합니다. 필요 시 크기는 2배씩 확장됩니다.
🧮 중복 제거 메커니즘
-
객체의 hashCode() 값 계산
객체를 추가할 때, 먼저 해당 객체의 hashCode()를 계산합니다. -
버킷(bucket) 선택
hashCode()를 바탕으로 어떤 버킷(배열의 index)에 저장할지를 결정합니다. (hash % capacity) -
동일한 해시 버킷에 값이 있으면 equals() 비교
같은 버킷에 이미 객체가 있다면, equals() 메서드를 통해 논리적으로 같은 객체인지 판단합니다. -
만약 동일한 해시 버킷에 저장된 엔트리가 많아질 경우(기본 기준 8개 이상), 성능 저하를 방지하기 위해 해당 버킷은 연결 리스트에서 Red-Black Tree로 전환됩니다(Java 8+). 이로써 최악의 경우에도 탐색 시간이 O(log n)으로 보장됩니다.
-
같다면 중복으로 판단 → 저장하지 않음
즉, hashCode()와 equals() 둘 다 같아야 중복으로 판단됩니다.
요약: hashCode() → 후보 압축 → equals() → 중복 판단
⚡ 왜 중복 체크가 효율적인가?
👉 O(1)에 가까운 성능
HashMap의 주요 연산(put, get)은 평균적으로 O(1) 시간 복잡도를 가집니다.
해시 충돌이 적고, 버킷이 균일하게 분포되어 있다면 매우 빠릅니다.
👉 hashCode() → equals()의 2단계 비교
hashCode()로 빠르게 필터링하고,
equals()는 오직 후보만 비교하므로 비교 횟수가 적습니다.
⚠️ hashCode()와 equals() 구현 주의
HashSet에 사용자 정의 객체를 넣을 경우, 반드시 hashCode()와 equals()를 오버라이드해야 정확히 동작합니다.
@Override
public int hashCode() {
return Objects.hash(name, age);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Person)) return false;
Person p = (Person) o;
return age == p.age && name.equals(p.name);
}✅ 요약
| 항목 | 내용 |
|---|---|
| 내부 자료구조 | HashMap 사용 |
| 중복 판단 기준 | hashCode() + equals() |
| 성능 | 평균 O(1) |
| 순서 보장 | ❌ (순서를 유지하지 않음) |
| null 허용 | 1개까지 허용 가능 |
| 사용자 객체 사용 시 | hashCode()와 equals() 필수 오버라이드 |
📝 결론
HashSet은 내부적으로 HashMap의 키 저장 구조를 활용하여, 중복을 빠르게 제거할 수 있는 자료구조입니다. 해시 기반의 비교 방식으로 인해 평균적으로 매우 빠른 성능을 보이며, 특히 중복 제거나 빠른 포함 여부 확인(contains)에 탁월합니다.
Q. O(n)과 O(log n)의 성능 차이를 실생활 예시를 들어 설명하고, 데이터의 크기가 1백만 개일 때 각각 대략 몇 번의 연산이 필요한지 비교해주세요.
A.
🔍 시간 복잡도 O(n) vs O(log n)
| 복잡도 | 의미 | 예시 | 100만 개 데이터에서 예상 연산 횟수 |
|---|---|---|---|
| O(n) | 선형 시간 | 줄 세운 사람 한 명씩 검사 | 약 1,000,000번 |
| O(log n) | 로그 시간 | 전화번호부에서 이진 탐색 | 약 20번 |
🎯 실생활 비유
🔸 O(n) – "줄 서 있는 100만 명 중 내 친구 찾기"
방법: 맨 앞부터 한 사람씩 얼굴을 확인
- "최악의 경우 마지막 100만 번째 사람까지 확인해야 함"
- "비효율적이지만 단순함"
- "선형 탐색 (Linear Search)"
🔸 O(log n) – "전화번호부에서 사람 이름 찾기"
방법: 절반씩 접어서 원하는 이름이 있는지 판단
- "100만 개 → 50만 → 25만 → … → 1 (20번 이하로 탐색 끝)"
- "이진 탐색 (Binary Search) 방식"
- "정렬된 데이터에서만 가능하지만, 엄청 빠름"
📈 수치 비교: 1,000,000개의 데이터
| 복잡도 | 연산 횟수 계산 | 결과 |
|---|---|---|
| O(n) | = n = 1,000,000 | 🔁 약 100만 번 |
| O(log n) | = log₂(1,000,000) ≈ 19.93 | 🔁 약 20번 |
참고:
- "log₂(10⁶) ≈ log₁₀(10⁶) / log₁₀(2) = 6 / 0.301 ≈ 19.93"
- "실제 구현에서는 log n 연산이라도 정렬이 필요하거나 조건문이 많으면 상수 계수가 커질 수 있음"
🧠 언제 어떤 복잡도를 선택해야 할까?
| 조건 | 적절한 선택 |
|---|---|
| 데이터가 작고 정렬이 안 되어 있음 | O(n) 허용 가능 |
| 데이터가 크고 빠른 탐색이 중요 | O(log n) 또는 더 낮은 복잡도 필요 |
| 탐색을 자주 하고 데이터 변경이 적음 | 정렬 + 이진 탐색 구조 (Tree, Binary Search, etc.) |
✅ 결론
- O(n)은 직관적이고 단순하지만, 데이터 양이 많아질수록 성능이 급격히 저하됩니다.
- O(log n)은 초대형 데이터에서도 빠른 성능을 보장하며, 검색 최적화의 대표적인 예입니다.
- 실제 프로그래밍에서는 문제 상황에 따라 적절한 알고리즘과 자료구조 선택이 중요합니다.
