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"));
    }
}

세 결과의 size와 포함 여부는 같습니다. LinkedHashSet은 최초 삽입 위치를 기억하므로 중복 해시가 다시 들어와도 위치를 끝으로 옮기지 않습니다. TreeSet은 자연 순서를 사용해 알파벳순으로 순회합니다. HashSet 문자열 표현의 순서는 설명 근거로 쓰지 않습니다.

구현별 비용과 null 정책

HashSet의 add·포함 여부·remove는 좋은 해시 분산에서 평균 O(1)입니다. LinkedHashSet도 해시 테이블을 사용하면서 앞뒤 연결 정보를 추가해 비슷한 평균 복잡도를 제공하지만 원소당 링크 메모리가 더 필요합니다. TreeSet은 균형 이진 검색 트리를 사용해 주요 연산이 O(로그 n)이고 정렬·범위 조회를 얻습니다.

HashSet과 LinkedHashSet은 null 하나를 허용합니다. 자연 순서 TreeSet은 null을 비교할 수 없어 일반적으로 NullPointerException을 냅니다. null 정책을 구현의 우연한 차이로 두지 말고 도메인 입력 확인으로 먼저 결정하는 편이 안전합니다.

TreeSet에서 비교자가 0을 반환하면 Set 관점에서 중복으로 취급합니다. equals가 false여도 정렬 비교가 0이면 두 번째 원소가 추가되지 않습니다. 정렬 기준이 동등성 의미와 모순되지 않는지 검토해야 합니다.

범위 질의와 TreeSet 선택

날짜나 점수 구간을 반복해서 찾는다면 매번 전체 HashSet을 정렬하는 것보다 NavigableSet이 직접적인 규칙입니다. lower, floor, ceiling, higher와 subSet을 사용할 수 있습니다. 단 한 번의 보고서 정렬 때문에 모든 쓰기에 O(로그 n) 비용을 지불할 필요는 없습니다.

src/TreeSetRangeQuery.java

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

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

중복 45는 한 번만 남고 모든 범위 결과는 정렬되어 있습니다. 같은 기능을 HashSet으로 만들면 filter와 정렬을 질의마다 반복해야 합니다. 질의 빈도와 변경 빈도를 함께 측정해 저장 시 정렬과 조회 시 정렬 중 하나를 선택합니다.

Study Log 태그 순서 기준

교재 본문에 처음 등장한 태그 순서를 유지하면 읽는 사람이 맥락을 따라가기 쉽습니다. 이 요구에는 LinkedHashSet이 적합합니다. 검색용 내부 인덱스라 순서가 전혀 보이지 않으면 HashSet이 더 단순합니다. 자동 완성 목록이 항상 사전순이어야 하고 범위 검색도 한다면 TreeSet을 고려합니다.

app/OrderedStudyTagCli.java

import java.util.LinkedHashSet;
import java.util.Locale;
import java.util.Set;

public final class OrderedStudyTagCli {
    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("learning-order=" + tags);
        System.out.println("search-view=" + tags.stream().sorted().toList());
    }
}

저장 결과는 최초 학습 순서이고 검색 표현은 정렬 복사본입니다. 한 자료 구조가 모든 표현 순서를 동시에 책임지게 하지 않습니다.

연습 문제

점수 내림차순으로 Session을 정렬하되 점수가 같아도 주제가 다르면 둘 다 보관하세요. 비교자가 점수만 비교할 때 원소가 사라지는 이유도 확인합니다.

정답과 해설

첫 비교 결과가 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<Session> order =
                Comparator.comparingInt(Session::score).reversed().thenComparing(Session::topic);
        Set<Session> sessions = new TreeSet<>(order);
        sessions.add(new Session("hash", 90));
        sessions.add(new Session("set", 90));
        sessions.add(new Session("tree", 80));
        System.out.println("size=" + sessions.size() + ", values=" + sessions);
    }

    private record Session(String topic, int score) {}
}

size는 3입니다. 주제까지 같으면 비교자가 0을 반환해 같은 정렬 키로 취급합니다. 그 의미가 도메인 동등성과 맞는지 별도 확인해야 합니다.

세 구현 모두 중복 거부라는 Set 규칙은 같지만, 반복 순서가 관찰 가능한 API 결과라면 구현 교체도 기능 변경이 됩니다. 반대로 순서를 문서화하지 않았다면 우연히 나온 현재 출력에 의존하는 호출자를 먼저 고쳐야 합니다.

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

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