자바 컬렉션 한눈에 보기 4편: HashSet과 TreeSet, 중복 판정의 기준

자바 컬렉션 한눈에 보기 4편: HashSet과 TreeSet, 중복 판정의 기준

---

들어가며

Set은 API만 보면 매우 단순하다.

• 중복을 허용하지 않는다

그런데 이 단순한 규칙 뒤에는 사실 이미 배운 거의 모든 개념이 녹아 있다.

• HashSet은 HashMap의 이해가 그대로 필요하고
• TreeSet은 TreeMap의 비교 기반 정렬 철학이 그대로 들어가며
• 중복 판정 기준도 hash냐 compare냐에 따라 달라진다

즉 Set은 별도 세계가 아니라
Map 개념을 "값 자체만 저장"하도록 변형한 구조에 가깝다.

---

목차

• 17) HashSet은 왜 중복을 허용하지 않을까
• 18) TreeSet 내부 구조

---

17) HashSet은 왜 중복을 허용하지 않을까

17-1) HashSet은 별도 마법 구조가 아니다

Set은 원소만 저장하고 Map은 key-value를 저장한다.
그래서 처음에는 둘이 꽤 다른 구조처럼 보인다.

하지만 HashSet이 정말 필요한 것은 사실 하나다.

• 이 원소가 이미 있는가

이 질문은 HashMap의 key 조회와 거의 같다.
즉 HashSet은 사실상 "value가 필요 없는 HashMap"처럼 이해할 수 있다.

17-2) 내부적으로는 key로만 관리한다

개념적으로는 아래처럼 생각하면 된다.

private final HashMap<E, Object> map = new HashMap<>();
private static final Object PRESENT = new Object();

즉 HashSet은 원소를 HashMap의 key로 저장하고,
value 자리에는 의미 없는 더미 객체를 넣는다.

17-3) 중복 판정은 결국 HashMap key 규칙이다

따라서 HashSet의 중복 판정 기준은 아래와 같다.

• hashCode()로 bucket 후보를 찾고
• 그 bucket 안에서 equals()로 같은 원소인지 비교한다

즉 HashSet에서 중복 문제가 생기면,
결국 equals()와 hashCode() 기준이 잘 맞는지 다시 봐야 한다.

17-4) 추가 동작은 사실상 put(key, PRESENT)다

개념적으로 add(e)는 아래와 비슷하다.

public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

즉 이미 key가 있으면 새로 저장하지 않는다.
그래서 "중복을 허용하지 않는다"는 약속이 자연스럽게 구현된다.

---

18) TreeSet 내부 구조

18-1) TreeSet은 정렬된 집합이다

TreeSet은 아래 특성을 가진다.

• 원소가 정렬된 상태로 유지된다
• 범위 조회가 가능하다
• 가장 작은 값/큰 값 접근이 자연스럽다

이 기능은 TreeMap의 key 정렬 기능과 거의 같다.

즉 개념적으로는 아래처럼 볼 수 있다.

private final NavigableMap<E, Object> map = new TreeMap<>();

18-2) 중복 제거도 비교 기준으로 한다

TreeSet은 hash를 쓰지 않는다.
원소를 넣을 때마다 현재 노드와 비교하며 내려간다.

• 작으면 왼쪽
• 크면 오른쪽
• 비교 결과가 0이면 같은 원소로 본다

즉 TreeSet에서는 정렬과 중복 제거가
같은 비교 기준에서 나온다.

18-3) equals()보다 compareTo()가 더 중요할 수 있다

이 지점이 실무에서 중요하다.
TreeSet은 보통 compareTo() 또는 Comparator 결과가 0이면 같은 원소로 취급한다.

즉 equals()와 다르게 동작할 수 있다.

그래서 비교 기준을 잘못 잡으면:

• 개발자 감각상으로는 다른 값인데
• TreeSet에는 하나만 남는 상황

이 생길 수 있다.

18-4) 예시로 보면 더 분명하다

Set<Integer> numbers = new TreeSet<>();
numbers.add(30);
numbers.add(10);
numbers.add(20);
numbers.add(20);

결과는 정렬된 상태로 유지되고, 20은 하나만 남는다.
즉 TreeSet은 "정렬된 HashSet"이 아니라,
애초에 철학이 TreeMap 쪽에 가깝다.

---

마치며

Set 구간은 짧아 보여도 중요한 교훈이 있다.

• HashSet은 HashMap key 규칙을 그대로 따른다
• TreeSet은 TreeMap의 비교 기반 정렬 철학을 그대로 따른다
• 중복 제거 기준은 자료구조 철학에 따라 달라진다

즉 Set은 독립된 마법 상자가 아니라,
이미 배운 Map 개념을 "값만 중요하게" 바꿔 쓴 결과물이다.

---

한 줄 정리

Set의 핵심은 "중복을 막는다"는 표면 규칙보다,
그 중복을 hash 기반으로 판단하는지, 비교 기반으로 판단하는지에 따라 내부 철학이 완전히 달라진다는 점이다.