HashSet vs TreeSet 차이 정리

자바 HashSet과 TreeSet 차이는 Set이 중복을 허용하지 않는다는 공통점만 보면 쉽게 놓치기 쉽습니다.

그래서 HashSet과 TreeSet도 그냥 같은 Set인데 정렬만 되느냐 아니냐 정도로 가볍게 넘기기 쉽습니다.

그런데 실무에서는 이 차이를 그렇게만 보면 자주 틀립니다.

HashSet은 해시 기반 Set이고, TreeSet은 정렬과 탐색이 가능한 정렬 기반 Set입니다.

이 차이 때문에 성능, 순회 순서, null 처리, 중복 판단 체감, 그리고 lower, floor, ceiling, higher 같은 탐색 능력까지 모두 달라집니다.

이번 글에서는 둘 다 중복 제거용 Set이라는 표면 아래에서 실제로 무엇이 다른지 실전 기준으로 정리하겠습니다.

자바 HashSet과 TreeSet 차이를 먼저 한 줄로 비교하기

• HashSet: 빠른 추가/조회가 중심, 순서 보장 없음
• TreeSet: 정렬된 상태 유지, 탐색 API 제공, 비교 기준이 매우 중요

Oracle 문서 기준으로 HashSet은 hash table, 실제로는 HashMap 기반이라고 설명합니다.

반면 TreeSet은 TreeMap 기반의 NavigableSet 구현입니다.

즉 처음부터 내부 구조와 목적이 다릅니다.

HashSet은 무엇이 강할까

HashSet은 기본 연산인 add, remove, contains, size가 평균적으로 상수 시간에 가깝게 동작하도록 설계되어 있습니다.

그래서 “정렬은 필요 없고 빠르게 중복만 막고 싶다”면 보통 가장 먼저 떠올릴 후보가 됩니다.

예를 들어 로그인한 사용자 ID 중복 체크, 방문 여부 체크, 이미 처리한 키 모음, 태그 중복 제거 같은 장면이 그렇습니다.

중요한 점은 순회 순서를 믿으면 안 된다는 것입니다.

문서도 iteration order를 보장하지 않는다고 분명히 말합니다.

오늘은 우연히 들어간 순서처럼 보여도, 다음 실행에서 같은 모양이 유지된다고 기대하면 안 됩니다.

TreeSet은 무엇이 강할까

TreeSet은 원소를 넣는 순간부터 정렬된 상태를 유지합니다.

그리고 NavigableSet이기 때문에 단순 중복 제거를 넘어선 탐색이 가능합니다.

예를 들어 아래 같은 질문에 잘 맞습니다.

• 특정 값보다 바로 작은 값은 무엇인가
• 특정 값보다 크거나 같은 첫 값은 무엇인가
• 범위 안의 원소만 잘라서 보고 싶다
• 가장 작은 값, 가장 큰 값을 자주 꺼내고 싶다

이런 장면은 HashSet만으로는 자연스럽지 않습니다.

TreeSet은 lower, floor, ceiling, higher, first, last, subSet, headSet, tailSet 같은 API를 제공합니다.

즉 TreeSet은 중복 제거 + 정렬 + 경계 탐색이 필요한 경우에 진가가 있습니다.

시간복잡도는 왜 다를까

Oracle 문서 기준으로 HashSet의 기본 연산은 평균적으로 상수 시간, TreeSet의 기본 연산은 보장된 log(n) 시간입니다.

그래서 단순 membership check만 잦다면 일반적으로 HashSet이 더 가볍습니다.

반대로 항상 정렬 상태를 유지해야 하거나, 범위 탐색과 인접 원소 탐색이 중요하다면 TreeSet의 log(n) 비용이 충분히 납득됩니다.

핵심은 Big-O 숫자 자체보다 무엇을 자주 하느냐입니다.

정렬된 결과가 필요해서 결국 HashSet → List 변환 → 정렬을 반복한다면, 처음부터 TreeSet이 더 단순하고 읽기 좋은 선택일 수 있습니다.

중복 판단 방식이 체감상 다른 이유

여기서 많은 사람이 헷갈립니다.

HashSet은 equals와 hashCode 감각이 중요합니다.

반면 TreeSet은 문서가 말하듯 비교 기준이 equals와 consistent 해야 Set 계약을 올바르게 따릅니다.

즉 TreeSet에서는 compareTo나 Comparator.compare 결과가 0이면, 정렬 관점에서 같은 원소처럼 취급됩니다.

아래 예시를 보면 바로 감이 옵니다.

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

class Student {
    private final String name;
    private final int score;

    Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

    public String getName() {
        return name;
    }

    public int getScore() {
        return score;
    }
}

public class Main {
    public static void main(String[] args) {
        Comparator<Student> byNameOnly = Comparator.comparing(Student::getName);
        Set<Student> students = new TreeSet<>(byNameOnly);

        students.add(new Student("Kim", 90));
        students.add(new Student("Kim", 100));

        System.out.println(students.size());
    }
}

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

class Student {
    private final String name;
    private final int score;

    Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

    public String getName() {
        return name;
    }

    public int getScore() {
        return score;
    }
}

public class Main {
    public static void main(String[] args) {
        Comparator<Student> byNameOnly = Comparator.comparing(Student::getName);
        Set<Student> students = new TreeSet<>(byNameOnly);

        students.add(new Student("Kim", 90));
        students.add(new Student("Kim", 100));

        System.out.println(students.size());
    }
}

이름만 비교하면 compare 결과가 0이기 때문에 두 학생은 TreeSet 입장에서 같은 위치의 원소처럼 취급될 수 있습니다.

즉 HashSet에서는 equals/hashCode 설계가 중요하고, TreeSet에서는 정렬 기준이 곧 중복 판단 체감에도 영향을 준다는 점을 꼭 기억해야 합니다.

null 처리는 왜 다르게 느껴질까

HashSet 문서는 null element를 허용한다고 설명합니다.

하지만 TreeSet은 자연 순서를 쓰는 경우 null을 넣으면 비교할 수 없어 문제가 됩니다.

comparator가 null을 안전하게 다루도록 명시적으로 설계된 경우가 아니라면, 보통 TreeSet에서는 null을 자연스럽게 기대하지 않는 편이 안전합니다.

그래서 입력값에 null 가능성이 섞여 있고 그냥 membership 집합으로 쓸 것이라면 HashSet 쪽이 훨씬 마음이 편할 수 있습니다.

순서가 필요할 때 무조건 TreeSet일까

실무에서는 여기서 LinkedHashSet을 같이 떠올릴 수 있어야 판단이 더 좋아집니다. 입력 순서를 유지하고 싶을 뿐 정렬 기준 탐색이 필요 없는 경우에는 TreeSet보다 LinkedHashSet이 더 자연스러울 수 있습니다.

즉 “순서가 필요하다”는 말을 더 잘게 쪼개서, 정렬된 순서인지, 입력 순서인지, 경계 탐색이 필요한 순서인지 나눠서 보는 습관이 중요합니다.

꼭 그렇지는 않습니다.

이 질문을 잘게 나눠야 합니다.

1. 원소를 넣는 순간부터 정렬 상태가 계속 필요하다

이 경우 TreeSet이 잘 맞습니다.

2. 평소엔 빠른 중복 체크만 하고, 마지막에 한 번만 정렬하면 된다

이 경우 HashSet에 모은 뒤 List로 바꿔 정렬하는 편이 더 단순할 수 있습니다.

3. 입력 순서를 보존하고 싶다

이 경우는 TreeSet도 HashSet도 정확한 답이 아닐 수 있고, LinkedHashSet을 검토하는 편이 맞습니다.

즉 순서가 필요하다는 말만으로 TreeSet을 바로 고르면 판단이 거칠 수 있습니다.

TreeSet이 특히 잘 맞는 실전 장면

• 점수표에서 바로 이전 점수와 다음 점수를 찾고 싶을 때
• 예약 가능한 시간 중 가장 가까운 다음 시간을 찾고 싶을 때
• 범위 안 데이터만 잘라서 보고 싶을 때
• 중복 제거와 동시에 오름차순 출력을 계속 유지해야 할 때

이런 문제는 NavigableSet 기능이 바로 가치로 이어집니다.

import java.util.NavigableSet;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        NavigableSet<Integer> scores = new TreeSet<>();
        scores.add(70);
        scores.add(85);
        scores.add(90);
        scores.add(100);

        System.out.println(scores.floor(88));   // 85
        System.out.println(scores.ceiling(88)); // 90
    }
}

import java.util.NavigableSet;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        NavigableSet<Integer> scores = new TreeSet<>();
        scores.add(70);
        scores.add(85);
        scores.add(90);
        scores.add(100);

        System.out.println(scores.floor(88));   // 85
        System.out.println(scores.ceiling(88)); // 90
    }
}

이 감각은 단순 중복 제거 집합과는 확실히 다릅니다.

HashSet이 더 자연스러운 실전 장면

• 이미 본 이메일인지 확인하기
• 중복 로그인 세션 키를 막기
• 방문한 노드/상태를 빠르게 체크하기
• 대량 데이터에서 단순 membership test를 자주 하기

여기서는 정렬보다 빠른 존재 확인이 더 중요합니다.

이런 장면에서 TreeSet을 습관적으로 쓰면 괜히 비교 기준 설계와 log(n) 비용을 떠안게 됩니다.

실전 선택 기준 요약

HashSet을 먼저 떠올릴 때

• 정렬이 필요 없다
• 빠른 중복 체크와 포함 여부 확인이 핵심이다
• null 허용이 실무적으로 편하다
• 출력 순서를 믿지 않아도 된다

TreeSet을 먼저 떠올릴 때

• 정렬된 상태가 계속 필요하다
• 가장 가까운 이전/다음 값 탐색이 중요하다
• 범위 조회가 많다
• compare 기준을 명확히 설계할 수 있다

정리

HashSet과 TreeSet은 둘 다 Set이지만, 실제로는 비슷한 통에 담긴 다른 도구에 가깝습니다.

• HashSet은 빠른 해시 기반 중복 체크 도구
• TreeSet은 정렬과 탐색까지 포함한 정렬 기반 Set 도구

그래서 중복 제거만 본다면 HashSet이 기본값에 가깝고, 정렬과 경계 탐색까지 필요하면 TreeSet이 설계적으로 더 자연스럽다고 정리하면 좋습니다.

같이 보면 좋은 글은 HashMap과 TreeMap 차이, Comparable과 Comparator 차이, equals와 hashCode 글입니다.

같이 보면 좋은 내부 글은 Comparable과 Comparator 차이, equals와 hashCode, HashMap과 TreeMap 차이입니다.

공식 참고 자료로는 Oracle Java SE 21 HashSet API, Oracle Java SE 21 TreeSet API, Oracle Java SE 21 NavigableSet API, Oracle Java SE 21 SortedSet API를 함께 보면 좋습니다.