본문 바로가기

Set 구현과 순서 계약

중복 제거는 같지만 무순서·삽입 순서·정렬 순서가 다른 세 구현을 작업 요구와 비용으로 선택합니다.

Set 인터페이스는 중복 없는 원소 집합을 약속하지만 반복 순서까지 하나로 고정하지 않습니다.

HashSet은 해시 기반 일반 선택, LinkedHashSet은 삽입 순서 보존, TreeSet은 비교 기준에 따른 정렬과 범위 탐색을 제공합니다.

결과를 화면에 보여 준다고 무조건 정렬 Set을 선택하지 않고, 저장 규칙과 표현 단계를 분리해야 합니다.

HashSet 반복 순서에 대한 잘못된 가정

작은 문자열 몇 개는 우연히 입력과 비슷하게 출력될 수 있습니다.

그 관찰을 API 사용 규칙으로 오해하면 JDK 버전, 용량, 입력 조합이 바뀔 때 화면 순서가 달라집니다.

다음 코드는 기대 문자열을 직접 비교해 취약한 가정을 드러냅니다.

lab/HashSetOrderAssumptionBug.java
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public final class HashSetOrderAssumptionBug {
    public static void main(String[] args) {
        List<String> input = List.of("zeta", "alpha", "hash", "tree");
        Set<String> unique = new HashSet<>(input);
        List<String> observed = unique.stream().toList();
        System.out.println("input=" + input);
        System.out.println("observed=" + observed);
        System.out.println("preserved=" + observed.equals(input));
    }
}

출력이 preserved=false라면 즉시 실패를 볼 수 있고, true가 나와도 규칙이 생긴 것은 아닙니다.

입력 순서를 기능 요구로 삼으려면 LinkedHashSet을 명시해야 합니다.

화면에서만 가나다순이 필요하면 HashSet을 유지하고 출력 시점에 스트림의 sorted()를 적용할 수 있습니다.

동일 입력의 세 구현 비교

src/StandardSetOrderComparison.java
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public final class StandardSetOrderComparison {
    public static void main(String[] args) {
        List<String> input = List.of("set", "hash", "tree", "hash", "linked");
        compare("hash", new HashSet<>(), input);
        compare("linked", new LinkedHashSet<>(), input);
        compare("tree", new TreeSet<>(), input);
    }

    private static void compare(String name, Set<String> target, List<String> input) {
        for (String value : input) {
            target.add(value);
        }
        System.out.println(name + ": size=" + target.size() + ", values=" + target);
        System.out.println(name + ": contains-tree=" + target.contains("tree"));
    }
}
같은 다섯 입력과 세 Set의 순서 계약

set, hash, tree, hash, linked를 넣으면 세 구현 모두 네 원소를 보관하지만 반복 순서를 정하는 계약은 다릅니다.

Set 선택 · 반복 순서 계약

같은 다섯 입력과 세 Set의 순서 계약

중복 hash를 제외한 원소는 모두 네 개입니다. LinkedHashSet은 첫 삽입 순서, TreeSet은 문자열 자연 순서를 따릅니다.

같은 입력에서 분기하는 세 반복 순서 계약 실선은set,hash,tree,hash,linked의같은입력을각각별도의빈HashSet/LinkedHashSet/TreeSet에전달합니다. 모두4원소/tree포함이며Linked는첫삽입순서,Tree는자연순서,Hash는반복순서보장없음입니다. 하나의 입력 목록 set, hash, tree, hash, linked HashSet size=4 / tree 포함 반복 순서 보장 없음 LinkedHashSet set, hash, tree, linked 첫 삽입 순서 TreeSet hash, linked, set, tree 문자열 자연 순서 실선: 같은 입력을 서로 다른 빈 집합에 전달 · 결과 구성은 모두 네 원소 HashSet의 현재 출력 나열은 계약으로 사용하지 않음
같은 입력에서 분기하는 세 반복 순서 계약 실선은set,hash,tree,hash,linked의같은입력을각각별도의빈HashSet/LinkedHashSet/TreeSet에전달합니다. 모두4원소/tree포함이며Linked는첫삽입순서,Tree는자연순서,Hash는반복순서보장없음입니다. 하나의 입력 목록 set, hash, tree, hash, linked HashSet size=4 / tree 포함 반복 순서 보장 없음 LinkedHashSet set, hash, tree, linked 첫 삽입 순서 TreeSet hash, linked, set, tree 문자열 자연 순서 실선: 같은 입력을 각각 전달 세 구현은 각각 빈 집합 시작 출력 순서와 원소 구성 구별

HashSet

공통 실행 결과
size=4
contains-tree=true
반복 순서의 계약과 값
반복 순서 보장 없음
원소는 set, hash, tree, linked 네 종류
현재 나열 순서는 계약으로 사용하지 않음

LinkedHashSet

공통 실행 결과
size=4
contains-tree=true
반복 순서의 계약과 값
최초 삽입 순서
[set, hash, tree, linked]

TreeSet

공통 실행 결과
size=4
contains-tree=true
반복 순서의 계약과 값
문자열 자연 순서
[hash, linked, set, tree]

입력은 [set, hash, tree, hash, linked]입니다. 기존 hash에 다시 add해도 LinkedHashSet의 위치는 유지됩니다. 저장 순서와 출력 시 sorted()를 적용한 순서는 별개의 규칙입니다.

세 결과의 size와 포함 여부는 같습니다.

LinkedHashSet은 최초 삽입 위치를 기억하므로 문자열 hash를 다시 추가해도 위치를 끝으로 옮기지 않습니다.

TreeSet은 자연 순서를 사용해 알파벳순으로 순회합니다.

HashSet 문자열 표현의 순서는 설명 근거로 쓰지 않습니다. LinkedHashSet의 순서 계약에 따라 중복 add는 위치를 유지하지만, 제거했다가 다시 추가하면 새 삽입이므로 끝으로 갑니다. 이 둘을 모두 “다시 추가”로 부르면 요구가 달라집니다.

구현별 비용과 null 정책

HashSet의 add·포함 여부·remove는 좋은 해시 분산에서 평균 O(1)입니다.

LinkedHashSet도 해시 테이블을 사용하면서 앞뒤 연결 정보를 추가해 비슷한 평균 복잡도를 제공하지만 원소당 링크 메모리가 더 필요합니다.

TreeSet은 균형 이진 검색 트리를 사용해 주요 연산이 O(log n)이고 정렬·범위 조회를 얻습니다.

HashSet과 LinkedHashSet은 null 하나를 허용합니다.

자연 순서 TreeSet은 null을 비교할 수 없어 NullPointerException을 냅니다. 명시적 비교자가 null의 순서를 정의한 경우에는 정책이 달라질 수 있으므로 자연 순서와 비교자 기반 구성을 구분합니다.

null 정책을 구현의 우연한 차이로 두지 말고 도메인 입력 확인으로 먼저 결정하는 편이 안전합니다.

TreeSet에서 비교자가 0을 반환하면 Set 관점에서 중복으로 취급합니다.

equals가 false여도 정렬 비교가 0이면 두 번째 원소가 추가되지 않습니다.

정렬 기준이 동등성 의미와 모순되지 않는지 검토해야 합니다.

90점의 hash와 set에 점수만 내림차순으로 비교하면 둘의 결과는 0입니다. 두 번째 add는 false여서 hash만 남고, 뒤의 tree 80까지 합친 크기는 2입니다. 원 연습처럼 제목을 다음 비교 기준에 넣으면 hash와 set의 결과가 0이 아니어 둘 다 남아 크기가 3이 됩니다. 이것은 비교자가 원소를 덮어쓰는 동작이 아니라 새 원소의 추가를 거부한 결과입니다.

범위 질의와 TreeSet 선택

날짜나 점수 구간을 반복해서 찾는다면 매번 전체 HashSet을 정렬하는 것보다 NavigableSet이 직접적인 규칙입니다.

lower, floor, ceiling, higher와 subSet을 사용할 수 있습니다.

단 한 번의 보고서 정렬 때문에 모든 쓰기에 O(log n) 비용을 지불할 필요는 없습니다.

src/TreeSetRangeQuery.java
import java.util.NavigableSet;
import java.util.TreeSet;

public final class TreeSetRangeQuery {
    public static void main(String[] args) {
        NavigableSet<Integer> viewCount = new TreeSet<>();
        viewCount.add(20);
        viewCount.add(45);
        viewCount.add(60);
        viewCount.add(90);
        viewCount.add(45);
        System.out.println("at-least-45=" + viewCount.tailSet(45, true));
        System.out.println("below-60=" + viewCount.lower(60));
        System.out.println("ceiling-50=" + viewCount.ceiling(50));
        System.out.println("range=" + viewCount.subSet(40, true, 80, false));
    }
}
네 값에 적용한 TreeSet 범위 경계

20, 45, 60, 90에서 포함 여부와 경계 방향을 달리한 네 질의가 서로 다른 부분 집합이나 한 값을 반환합니다.

범위 질의 · 포함과 제외 경계

네 값에 적용한 TreeSet 범위 경계

중복 45를 제외한 값은 20·45·60·90입니다. 경계 포함 여부와 가장 가까운 값을 찾는 조건을 각 호출과 맞춰 읽습니다.

네 실제 질의의 포함 조건과 선택 결과 입력20/45/60/90에서tailSet45포함은45/60/90,subSet40포함80제외는45/60,lower60은45,ceiling50은60입니다. 실선은각질의조건과그결과를연결하며한질의결과를다음질의입력으로쓰지않습니다. tailSet(45, true) 포함 조건 45 이상 선택 결과 45, 60, 90 lower(60) 엄격한 상한 60 미만 중 최대 선택 결과 45 ceiling(50) 포함하는 하한 50 이상 중 최소 선택 결과 60 subSet(40~80) 포함·제외 구간 40 이상 / 80 미만 선택 결과 45, 60 실선: 각 질의의 조건 → 결과 입력: 20, 45, 60, 90 네 질의는 각각 원 집합 사용
네 실제 질의의 포함 조건과 선택 결과 입력20/45/60/90에서tailSet45포함은45/60/90,subSet40포함80제외는45/60,lower60은45,ceiling50은60입니다. 실선은각질의조건과그결과를연결하며한질의결과를다음질의입력으로쓰지않습니다. tailSet(45, true) lower(60) ceiling(50) subSet(40~80) 포함 조건 45 이상 선택 결과 45, 60, 90 엄격한 상한 60 미만 중 최대 선택 결과 45 포함하는 하한 50 이상 중 최소 선택 결과 60 포함·제외 구간 40 이상 / 80 미만 선택 결과 45, 60 실선: 각 질의의 조건 → 결과 입력: 20, 45, 60, 90 네 질의는 각각 원 집합 사용
네 값에 적용한 TreeSet 범위 경계
실제 호출선택 조건실제 결과
tailSet(45, true)value ≥ 45[45, 60, 90]
lower(60)60보다 작은 값 중 최대45
ceiling(50)50 이상인 값 중 최소60
subSet(40, true, 80, false)40 ≤ value < 80[45, 60]
tailSet(45, true)
선택 조건
value ≥ 45
실제 결과
[45, 60, 90]
lower(60)
선택 조건
60보다 작은 값 중 최대
실제 결과
45
ceiling(50)
선택 조건
50 이상인 값 중 최소
실제 결과
60
subSet(40, true, 80, false)
선택 조건
40 ≤ value < 80
실제 결과
[45, 60]

입력 [20, 45, 60, 90, 45]에서 중복 45는 하나만 남습니다. 이 main은 질의 결과만 출력하며 반환된 범위 뷰를 변경하지 않습니다.

중복 45는 한 번만 남고 모든 범위 결과는 정렬되어 있습니다.

같은 기능을 HashSet으로 만들면 filter와 정렬을 질의마다 반복해야 합니다.

질의 빈도와 변경 빈도를 함께 측정해 저장 시 정렬과 조회 시 정렬 중 하나를 선택합니다.

subSet·headSet·tailSet은 기본 집합과 연결된 범위 뷰를 반환합니다. 결과를 독립 복사본으로 오해하면 뷰의 remove가 원본도 바꾸는 것을 놓칩니다. NavigableSet 범위 뷰 계약상 범위를 벗어난 add는 IllegalArgumentException입니다. 원 main은 뷰를 변경하지 않으며, 아래 예제는 이 별도 변경 경계를 확인합니다.

src/TreeSetBackedRangeView.java
import java.util.List;
import java.util.NavigableSet;
import java.util.TreeSet;

public final class TreeSetBackedRangeView {
    public static void main(String[] args) {
        NavigableSet<Integer> all = new TreeSet<>(List.of(20, 45, 60, 90));
        NavigableSet<Integer> range = all.subSet(40, true, 80, false);
        System.out.println("removed=" + range.remove(45));
        System.out.println("all=" + all);
        all.add(75);
        System.out.println("range=" + range);
        try {
            range.add(80);
        } catch (IllegalArgumentException expected) {
            System.out.println("outside-range");
        }
    }
}

출력은 removed=true, all=[20, 60, 90], range=[60, 75], outside-range입니다. 원본과 뷰의 변경이 양방향으로 보이지만 제외 상한 80은 뷰에 추가할 수 없습니다. 같은 값 80을 all에 직접 추가하는 것은 별도 연산이고 허용됩니다.

복사본과 범위 뷰 구별하기

위 range를 new TreeSet<>(range)로 복사하고 복사본에서 60을 제거하면 all에서도 60이 없어지나요? 제거가 아니라 range.add(80)을 먼저 호출한 경우에는 어떤 예외와 어떤 상태가 남나요?

공유 변경 범위 확인

새 TreeSet은 독립 집합이므로 그 집합에서 60을 제거해도 all에는 60이 남습니다. 원 범위 뷰에 80을 추가하려 하면 IllegalArgumentException으로 거부되고 원본·뷰의 원소는 추가 전과 같습니다. 뷰는 원본의 모든 값을 허용하는 별칭이 아니라 40 이상·80 미만이라는 조건을 유지하는 변경 통로입니다.

경계값으로 확인하기

원문의 20·45·60·90에서 lower(45), floor(45), ceiling(45), higher(45)를 각각 예측하세요. lower와 higher는 같은 값을 제외하고 floor와 ceiling은 포함할 수 있습니다.

엄격한 경계와 포함 경계 확인

결과는 20, 45, 45, 60입니다. lower(45)는 45 미만 중 최대, floor(45)는 45 이하 중 최대, ceiling(45)는 45 이상 중 최소, higher(45)는 45 초과 중 최소입니다. 45가 들어 있는지가 이 두 쌍의 결과를 갈라놓습니다. 원 예제처럼 없는 기준값 50만 보면 포함·제외 차이가 드러나지 않을 수 있습니다.

게시글 저장소 태그 순서 기준

게시글에 태그가 처음 등록된 순서를 유지하면 작성자가 입력한 맥락을 보존할 수 있습니다.

이 요구에는 LinkedHashSet이 적합합니다.

검색용 내부 인덱스라 순서가 전혀 보이지 않으면 HashSet이 더 단순합니다.

자동 완성 목록이 항상 사전순이어야 하고 범위 검색도 한다면 TreeSet을 고려합니다.

app/OrderedBoardTagCli.java
import java.util.LinkedHashSet;
import java.util.Locale;
import java.util.Set;

public final class OrderedBoardTagCli {
    public static void main(String[] args) {
        Set<String> tags = new LinkedHashSet<>();
        for (String raw : new String[] {"Hash", "Set", "hash", "Tree", "Set"}) {
            tags.add(raw.toLowerCase(Locale.ROOT));
        }
        System.out.println("registration-order=" + tags);
        System.out.println("search-view=" + tags.stream().sorted().toList());
    }
}

저장 결과는 최초 등록 순서이고 검색 표현은 정렬 복사본입니다.

한 자료 구조가 모든 표현 순서를 동시에 책임지게 하지 않습니다.

연습 문제

점수 내림차순으로 게시글을 정렬하되 점수가 같아도 제목이 다르면 둘 다 보관하세요.

비교자가 점수만 비교할 때 원소가 사라지는 이유도 확인합니다.

정답과 해설

첫 비교 결과가 0이면 TreeSet은 중복으로 봅니다.

점수가 같을 때 제목을 두 번째 비교 기준으로 사용해 완전한 순서를 만듭니다.

exercise/TreeSetTieBreakerSolution.java
import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

public final class TreeSetTieBreakerSolution {
    public static void main(String[] args) {
        Comparator<RankedPost> order =
                Comparator.comparingInt(RankedPost::score)
                        .reversed()
                        .thenComparing(RankedPost::title);
        Set<RankedPost> posts = new TreeSet<>(order);
        posts.add(new RankedPost("hash", 90));
        posts.add(new RankedPost("set", 90));
        posts.add(new RankedPost("tree", 80));
        System.out.println("size=" + posts.size() + ", values=" + posts);
    }

    private record RankedPost(String title, int score) {}
}
점수 동률을 title로 구분한 세 게시글

점수 내림차순으로 90점 두 글을 먼저 두고 동점인 hash와 set은 제목 오름차순으로 구분하여 세 원소를 보관합니다.

TreeSet 비교 · 점수 다음 제목

점수 동률을 title로 구분한 세 게시글

점수는 내림차순, 동점일 때 제목은 오름차순입니다. 90점의 hash와 set을 다른 원소로 남겨 최종 size가 3입니다.

동점에서 제목으로 가르는 정렬 키 hash90/set90은점수비교0뒤제목비교로구분해둘다남습니다. tree80은뒤로놓고최종3원소입니다. 실선은정렬규칙과결과이지TreeSet내부비교실행순서가아닙니다. 90점 두 값 비교 hash와 set의 점수 90 대 90 / 첫 비교 0 thenComparing 제목 hash가 set보다 먼저 두 값 모두 보관 비교 결과는 0이 아님 다른 점수의 tree tree 80 대 두 90 점수 내림차순 기준 90점들 뒤에 위치 hash90 / set90 / tree80 최종 관찰 size=3 실선: 정렬 규칙·결과 관계 내부 비교 호출 순서 아님 점수만 비교하면 두번째90 거부
동점에서 제목으로 가르는 정렬 키 hash90/set90은점수비교0뒤제목비교로구분해둘다남습니다. tree80은뒤로놓고최종3원소입니다. 실선은정렬규칙과결과이지TreeSet내부비교실행순서가아닙니다. 90점 두 값 비교 다른 점수의 tree hash와 set의 점수 90 대 90 / 첫 비교 0 thenComparing 제목 hash가 set보다 먼저 두 값 모두 보관 비교 결과는 0이 아님 tree 80 대 두 90 점수 내림차순 기준 90점들 뒤에 위치 hash90 / set90 / tree80 최종 관찰 size=3 실선: 정렬 규칙·결과 관계 내부 비교 호출 순서 아님 점수만 비교하면 두번째90 거부

hash
score=90

원문의 비교 기준
동점이면 제목 오름차순
집합에서의 결과
90점 중 제목 hash가 먼저

set
score=90

원문의 비교 기준
점수는 같지만 제목이 hash와 다름
집합에서의 결과
비교 결과가 0이 아니므로 둘 다 보관

tree
score=80

원문의 비교 기준
80점은 90점 다음
집합에서의 결과
마지막 원소; 전체 size=3

원문은 점수 비교에 reversed()를 적용한 뒤 thenComparing(RankedPost::title)로 동률을 구분합니다. 점수만 비교하는 잘못된 비교자는 이 main에서 실행하지 않습니다. 표는 내부 비교 호출 순서가 아니라 최종 정렬 순서와 규칙을 설명합니다.

size는 3입니다.

제목까지 같으면 비교자가 0을 반환해 같은 정렬 키로 취급합니다.

그 의미가 도메인 동등성과 맞는지 별도로 확인해야 합니다.

세 구현 모두 중복 거부라는 Set 규칙은 같지만, 반복 순서가 관찰 가능한 API 결과라면 구현 교체도 기능 변경이 됩니다.

반대로 순서를 문서화하지 않았다면 우연히 나온 현재 출력에 의존하는 호출자를 먼저 고쳐야 합니다.

표준 Set 선택은 중복 여부에서 끝나지 않습니다.

순서가 규칙인지 표현인지, 범위 질의가 반복되는지, 비교자의 0이 어떤 동등성을 뜻하는지 결정하면 세 구현 중 선택이 자연스럽게 좁혀집니다.

제네릭 Set과 재해시

이전 문서

게시글 저장소 집합 연산

다음 문서

이 페이지 목차

이 페이지 목차

HashSet 반복 순서에 대한 잘못된 가정동일 입력의 세 구현 비교구현별 비용과 null 정책범위 질의와 TreeSet 선택게시글 저장소 태그 순서 기준연습 문제