HashSet·LinkedHashSet·TreeSet 비교와 선택

앞 글들에서는 해시 집합을 직접 만들면서 중복을 막고 원소가 있는지 빠르게 확인하는 원리를 익혔습니다. 표준 라이브러리에도 같은 일을 하는 Set 인터페이스가 있고, 실무에서 주로 쓰는 구현은 HashSet, LinkedHashSet, TreeSet 세 가지입니다. 셋 모두 같은 원소를 두 번 저장하지 않습니다. 그런데 게시글 태그를 HashSet에 담아 출력해 보면, 입력한 순서도 아니고 사전순도 아닌 낯선 순서로 나올 때가 많습니다.

Set 인터페이스는 원소를 하나씩 꺼낼 때의 순서, 즉 반복 순서를 정하지 않고 그 결정을 구현에 맡깁니다. 그래서 세 구현을 가르는 가장 큰 차이는 반복 순서이고, 그 순서를 지키는 데 드는 비용이 두 번째 차이입니다. 이 글에서는 같은 입력을 세 구현에 넣어 차이를 확인하고, 각 구현이 그 순서를 어떻게 만들어 내는지 살펴본 뒤, 요구 사항에 따라 무엇을 고를지 정리합니다.

같은 입력을 세 구현에 넣어 보기

다음 코드는 "hash"가 두 번 들어 있는 문자열 다섯 개를 세 구현에 똑같이 넣고, 크기와 내용, "tree"가 들어 있는지를 출력합니다. compare 메서드는 매개변수를 Set<String> 타입으로 받으므로 어떤 구현을 넘겨도 같은 코드로 다룰 수 있습니다.

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

JDK 21에서 실행한 결과입니다. hash:로 시작하는 줄의 순서는 다른 JDK에서 다르게 나올 수 있어서, 실행한 버전을 함께 적었습니다.

hash: size=4, values=[set, tree, hash, linked]
hash: contains-tree=true
linked: size=4, values=[set, hash, tree, linked]
linked: contains-tree=true
tree: size=4, values=[hash, linked, set, tree]
tree: contains-tree=true

세 구현 모두 크기가 4이고 "tree"를 찾았습니다. 두 번째 "hash"는 이미 있는 원소라서 어느 구현에도 추가되지 않았습니다. 즉 중복을 거부하고 포함 여부에 답한다는, Set 인터페이스가 약속하는 일은 셋이 똑같이 합니다.

다른 것은 values= 뒤의 순서뿐입니다. LinkedHashSet은 처음 넣은 순서인 set, hash, tree, linked를 그대로 유지했고, TreeSet은 문자열의 사전순인 hash, linked, set, tree로 정렬했습니다. 그런데 HashSet의 set, tree, hash, linked는 둘 중 어느 쪽도 아닙니다. 앞의 두 순서는 각 클래스의 공식 API 문서(Javadoc)가 약속하는 순서이지만, HashSet의 순서는 아무도 약속하지 않은 순서입니다. 이 차이가 왜 중요한지부터 보겠습니다.

HashSet의 출력 순서에 기대면 안 되는 이유

HashSet의 Javadoc은 반복 순서를 전혀 보장하지 않으며, 특히 그 순서가 시간이 지나도 그대로 유지된다는 것도 보장하지 않는다고 적고 있습니다. 순서가 정해져 있지 않다는 말이 실행할 때마다 무작위로 섞인다는 뜻은 아닙니다. 같은 JDK에서 같은 원소를 같은 방식으로 넣으면 대개 같은 순서가 나오므로, 몇 번 실행해 보고 순서가 일정하다고 착각하기 쉽습니다. 다음 코드는 원소 구성이 전혀 바뀌지 않았는데도 순서가 달라지는 경우를 보여 줍니다.

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);
        System.out.println("input=" + input);
        System.out.println("before=" + unique);

        for (int i = 0; i < 20; i++) {
            unique.add("temp" + i);
        }
        for (int i = 0; i < 20; i++) {
            unique.remove("temp" + i);
        }
        System.out.println("after=" + unique);
        System.out.println("same-elements=" + unique.equals(Set.copyOf(input)));
    }
}

JDK 21에서 실행한 결과입니다. 임시 원소를 넣었다가 모두 지웠으니 원소 구성은 처음으로 돌아왔고, 그렇다면 before와 after의 순서도 같아야 할 것 같습니다.

input=[zeta, alpha, hash, tree]
before=[zeta, alpha, tree, hash]
after=[zeta, tree, alpha, hash]
same-elements=true

before는 네 문자열을 넣은 직후의 순서인데, 벌써 입력 순서와 다릅니다. 그다음 임시 원소 20개를 넣었다가 모두 지웠으니 집합에는 처음과 같은 네 원소만 남았고, 마지막 줄의 same-elements=true가 그것을 확인해 줍니다. 그런데도 after의 순서는 before와 다릅니다. 원소가 늘어나는 동안 내부 해시 테이블이 커졌는데, OpenJDK의 구현은 원소를 지워도 테이블을 다시 줄이지 않기 때문입니다. 테이블 크기가 바뀌면 원소가 놓이는 칸이 바뀌고, 칸이 바뀌면 반복 순서도 바뀝니다. 정확히 어떤 계산이 일어나는지는 바로 아래 '더 깊이'에서 따라가 봅니다.

순서가 바뀌는 계기는 원소를 넣고 빼는 것만이 아닙니다. 초기 용량을 다르게 주거나, 원소 클래스의 hashCode 구현이 바뀌거나, JDK 버전이 올라가 내부 구현이 달라져도 순서가 바뀔 수 있습니다. 그래서 HashSet의 출력 순서를 화면 표시나 테스트의 기대값으로 쓰면, 코드를 한 줄도 고치지 않았는데 어느 날 결과가 달라지는 버그가 됩니다. 순서가 기능의 일부라면 처음부터 순서를 약속하는 구현을 고르고, 화면에서만 정렬이 필요하다면 출력하는 시점에 정렬하면 됩니다.

더 깊이: HashSet의 반복 순서는 어디서 나올까 (OpenJDK 구현)

이 단락은 Javadoc이 약속하는 동작이 아니라 OpenJDK 21의 구현 방식을 설명합니다. 다른 버전이나 다른 JDK 구현에서는 달라질 수 있으니, 원리를 이해하는 데만 쓰고 코드가 여기에 기대게 만들지는 마세요.

HashSet이 내부에 HashMap을 하나 두고 동작한다는 점은 Javadoc에도 적혀 있습니다. OpenJDK는 원소를 그 맵의 키로 저장하고, 집합에는 키에 짝지을 값이 필요 없으므로 모든 키에 같은 빈 객체 하나(PRESENT라는 상수)를 값으로 넣습니다. HashMap의 버킷 배열은 길이가 언제나 2의 거듭제곱이고, 원소가 들어갈 버킷 번호는 다음과 같이 계산합니다.

int h = key.hashCode();
int index = (h ^ (h >>> 16)) & (table.length - 1);

해시 코드를 배열 인덱스로 바꾸는 글에서 쓴 Math.floorMod(hashCode, bucketCount)와 하는 일은 같습니다. 배열 길이가 2의 거듭제곱이면 & (length - 1)은 해시 값의 아래쪽 비트만 남기는데, 이 결과는 음수를 포함한 모든 int 값에서 floorMod와 같고 나눗셈보다 빠릅니다. 다만 아래쪽 비트만 보면 위쪽 비트의 차이가 버려지므로, 먼저 h ^ (h >>> 16)으로 위쪽 16비트를 아래쪽에 섞어 줍니다. 반복자는 이 배열을 0번 버킷부터 끝까지 차례로 훑고, 한 버킷 안에서는 연결된 순서대로 원소를 내놓습니다. 그래서 반복 순서는 곧 버킷 번호의 순서입니다.

앞 예제의 네 문자열에 이 계산을 적용하면 다음과 같습니다.

원소 네 개로 만든 집합은 버킷 16개로 시작합니다. 번호순으로 읽으면 zeta(0), alpha(7), tree(8), hash(14)이고, 이것이 before의 순서입니다. HashSet과 HashMap의 Javadoc에 따르면 기본 적재 계수(load factor)는 0.75이고, 원소 수가 '버킷 수 × 적재 계수'를 넘으면 버킷 배열을 대략 두 배로 늘려 모든 원소의 위치를 다시 계산합니다. 버킷이 16개라면 원소가 12개를 넘는 순간, 즉 임시 원소를 넣다가 13번째 원소가 들어갈 때 배열이 32개로 커집니다. 그 뒤 임시 원소를 모두 지워도 배열은 32개로 남으므로, 같은 네 원소가 zeta(0), tree(8), alpha(23), hash(30) 순서로 읽힙니다. 이것이 after의 순서입니다.

LinkedHashSet: 처음 넣은 순서를 기억하는 HashSet

LinkedHashSet은 HashSet을 상속한 클래스로, 원소를 찾고 중복을 막는 방식은 HashSet과 같습니다. 다른 점은 모든 원소를 넣은 순서대로 잇는 이중 연결 목록을 하나 더 유지한다는 것입니다. 원소를 찾을 때는 해시 테이블을 쓰고 반복할 때는 이 연결 목록을 따라가므로, 원소가 처음 넣은 순서대로 나옵니다. 앞 예제의 linked: 줄이 입력 순서를 그대로 보여 준 이유입니다.

여기서 '넣은 순서'가 정확히 무엇을 뜻하는지 짚어 둘 필요가 있습니다. 이미 있는 원소를 다시 add하는 경우와, 지웠다가 다시 넣는 경우의 결과가 다르기 때문입니다.

import java.util.LinkedHashSet;
import java.util.List;

public final class LinkedHashSetReinsert {
    public static void main(String[] args) {
        LinkedHashSet<String> tags = new LinkedHashSet<>(List.of("set", "hash", "tree"));
        System.out.println("add-again=" + tags.add("hash") + ", " + tags);

        tags.remove("hash");
        tags.add("hash");
        System.out.println("remove-then-add=" + tags);

        tags.addLast("set");
        System.out.println("addLast=" + tags);
    }
}

add-again=false, [set, hash, tree]
remove-then-add=[set, tree, hash]
addLast=[tree, hash, set]

첫 줄에서 이미 있는 "hash"를 다시 넣으면 add가 false를 돌려주고 순서도 그대로입니다. LinkedHashSet의 Javadoc도 원소를 다시 삽입할 때는 순서가 바뀌지 않는다고 명시합니다. 중복 원소는 아예 추가되지 않으니 처음 들어온 자리를 그대로 지키는 것입니다. 반면 둘째 줄처럼 remove로 지운 뒤 다시 add하면, 그 원소는 집합에 없던 새 원소로 취급되어 맨 뒤로 갑니다. 그래서 요구 사항에 '다시 추가하면'이라고만 적혀 있다면, 중복 추가를 말하는지 삭제 후 재추가를 말하는지 먼저 확인해야 합니다.

셋째 줄의 addLast는 Java 21에 추가된 메서드입니다. Java 21은 처음과 끝이 정해진 컬렉션을 위한 SequencedSet 인터페이스를 도입했고, LinkedHashSet이 이를 구현하면서 addFirst, addLast, getFirst, reversed 같은 메서드가 생겼습니다. addLast는 원소가 이미 있으면 그 원소를 맨 뒤로 옮기므로 "set"이 끝으로 이동했습니다. 순서를 일부러 바꾸고 싶을 때는 지웠다가 다시 넣기보다 이렇게 의도가 드러나는 메서드를 쓰는 편이 읽기 좋습니다.

연결 목록을 유지하려면 원소마다 앞뒤 원소를 가리키는 링크를 더 저장해야 하므로 메모리가 더 들고, Javadoc에 따르면 성능도 HashSet보다 약간 낮습니다. 대신 전체 반복은 오히려 유리합니다. HashSet은 빈 버킷까지 모두 훑어야 해서 반복 시간이 '원소 수 + 버킷 수'에 비례하지만, LinkedHashSet은 연결 목록만 따라가므로 원소 수에만 비례합니다.

TreeSet: 언제나 정렬된 순서와 범위 검색

TreeSet은 해시를 쓰지 않습니다. 원소를 균형 이진 탐색 트리인 레드-블랙 트리(red-black tree)에 정렬된 상태로 보관하고, 원소끼리 크기를 비교해서 위치를 찾습니다. 비교 기준은 원소 자신의 compareTo가 정하는 자연 순서이거나, 생성자에 넘긴 비교자(Comparator)입니다. 문자열의 자연 순서는 사전순이므로 앞 예제의 tree: 줄이 hash, linked, set, tree로 나왔습니다. 트리의 높이가 원소 수 n의 로그에 비례하도록 유지되므로, TreeSet의 Javadoc은 add, remove, contains에 O(log n) 시간을 보장합니다.

정렬된 순서보다 더 쓸모 있는 것은 범위 검색입니다. TreeSet이 구현하는 NavigableSet 인터페이스에는 '이 값보다 작은 것 중 가장 큰 값'이나 '40 이상 80 미만인 값 전부' 같은 질문에 바로 답하는 메서드가 있습니다. 다음은 게시글 조회 수를 모아 두고 범위를 묻는 예입니다.

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

at-least-45=[45, 60, 90]
below-60=45
ceiling-50=60
range=[45, 60]

45를 두 번 넣었지만 한 번만 남았고, 모든 결과가 정렬되어 있습니다. tailSet(45, true)는 45 이상인 값 전부이고, lower(60)은 60보다 작은 값 중 가장 큰 값, ceiling(50)은 50 이상인 값 중 가장 작은 값입니다. subSet(40, true, 80, false)의 두 boolean은 각 끝값을 포함할지를 정하므로, 40 이상 80 미만의 값만 골랐습니다. 가장 가까운 값을 찾는 메서드는 네 가지인데, 기준값 자체를 답으로 낼 수 있는지가 서로 다릅니다.

조건에 맞는 값이 없으면 네 메서드 모두 null을 돌려줍니다. 같은 기능을 HashSet으로 만들려면 질의할 때마다 모든 원소를 훑어 거르고 정렬해야 합니다. 그래서 범위 질의가 자주 반복된다면 TreeSet이 알맞습니다. 반대로 보고서를 만들 때 한 번 정렬하는 정도라면 HashSet에 저장해 두고 그때만 정렬하는 편이 쌉니다. TreeSet은 정렬된 상태를 지키느라 모든 add에 O(log n)을 쓰기 때문입니다.

범위 결과는 복사본이 아니라 원본과 연결된 뷰입니다

subSet, headSet, tailSet이 돌려주는 집합은 원소를 복사한 새 집합이 아닙니다. 원래 집합의 일부를 들여다보는 창, 즉 뷰(view)입니다. 뷰에서 원소를 지우면 원래 집합에서도 지워지고, 원래 집합에 범위 안의 값을 넣으면 뷰에도 보입니다. 결과를 독립된 복사본으로 생각하고 다루면 원본이 바뀌는 것을 놓치게 됩니다.

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

range에서 45를 지우자 all에서도 45가 사라졌습니다. 반대로 all에 75를 넣자, 75는 40 이상 80 미만이므로 range에도 나타났습니다. 마지막으로 뷰에 80을 넣으려고 하면 80은 뷰의 범위 밖이므로 IllegalArgumentException이 발생하고, 원본과 뷰 모두 바뀌지 않습니다. NavigableSet.subSet의 Javadoc에 적힌 동작입니다. 즉 뷰는 원본의 일부를 가리키는 또 다른 이름이면서, 자기 범위 조건은 끝까지 지킵니다. 80을 all에 직접 넣는 것은 문제가 없고, 그래도 range에는 나타나지 않습니다. 원본과 상관없는 독립된 집합이 필요하면 new TreeSet<>(range)처럼 새 집합을 만들면 됩니다.

TreeSet은 비교 결과가 0이면 같은 원소로 봅니다

HashSet과 LinkedHashSet은 hashCode로 버킷을 고르고 equals로 같은 원소인지 판단합니다. TreeSet은 둘 다 쓰지 않고 오직 비교 결과만 봅니다. 두 원소를 비교한 결과가 0이면 같은 원소로 취급하므로, 나중에 넣는 원소는 추가되지 않습니다. 이 규칙을 잊으면 점수순으로 게시글을 정렬하려다 게시글이 사라지는 일이 생깁니다.

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

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

    private record RankedPost(String title, int score) {}
}

Comparator.comparingInt(RankedPost::score)는 게시글의 score 값을 꺼내 비교하는 비교자를 만들고, .reversed()는 그 순서를 뒤집어 높은 점수가 앞에 오게 합니다. RankedPost::score처럼 메서드 이름을 값으로 넘기는 문법을 메서드 참조라고 합니다. 비교자를 만드는 방법은 Comparable과 Comparator를 다루는 17장에서, 메서드 참조는 람다를 다루는 30장에서 자세히 배웁니다. 여기서는 이 비교자가 점수만 보고 비교한다는 점만 기억하면 됩니다.

add-hash=true
add-set=false
add-tree=true
size=2, values=[RankedPost[title=hash, score=90], RankedPost[title=tree, score=80]]
contains-zzz=true

제목이 다른 게시글 세 개를 넣었는데 크기는 2입니다. set은 hash와 점수가 같아 비교 결과가 0이 되었고, TreeSet은 이미 같은 원소가 있다고 보고 add에서 false를 돌려주었습니다. 기존 원소를 새 원소로 바꾸지도 않으므로 처음 들어간 hash가 그대로 남습니다. 마지막 줄도 같은 이유로 나온 결과입니다. 넣은 적도 없는 zzz의 포함 여부를 물었는데 true가 나왔습니다. 점수 90인 원소가 이미 있으니, 비교자 입장에서는 같은 원소이기 때문입니다. record인 RankedPost를 equals로 비교하면 hash와 zzz는 분명히 다르지만, TreeSet은 equals를 한 번도 호출하지 않습니다.

Javadoc은 이 상황을 두고, 정렬 기준이 equals와 일관되어야(consistent with equals) TreeSet이 Set 인터페이스의 규칙을 제대로 따른다고 설명합니다. 비교 결과가 0인 경우와 equals가 true인 경우가 정확히 일치해야 한다는 뜻입니다. 그렇지 않아도 TreeSet의 동작 자체는 위처럼 정해져 있지만, 같은 원소들을 HashSet에 넣었을 때와 결과가 달라집니다. 해결 방법은 점수가 같을 때 쓸 두 번째 기준을 더해서, 정말 같은 게시글일 때만 비교 결과가 0이 되게 하는 것입니다.

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

public final class TreeSetTieBreaker {
    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) {}
}

size=3, values=[RankedPost[title=hash, score=90], RankedPost[title=set, score=90], RankedPost[title=tree, score=80]]

thenComparing(RankedPost::title)은 앞의 기준으로 비교한 결과가 0일 때만 제목을 사전순으로 비교합니다. 이제 hash와 set은 점수가 같아도 제목이 달라 비교 결과가 0이 아니므로 둘 다 남고, 크기는 3이 됩니다. 출력을 보면 점수는 내림차순이고, 같은 점수 안에서는 제목이 오름차순입니다. 제목과 점수가 모두 같은 두 게시글은 여전히 같은 원소가 되는데, 이 둘이 RankedPost의 구성 요소 전부이므로 record의 equals와도 일치합니다. 필드가 더 많은 클래스라면 비교 결과가 0이 되는 경우가 equals와 맞는지 따로 따져 봐야 합니다.

비교 기준이 아예 없는 경우도 알아 둡시다. RankedPost처럼 Comparable을 구현하지 않은 클래스의 객체를 비교자 없이 new TreeSet<>()에 넣으면, 컴파일은 되지만 첫 add에서 ClassCastException이 발생합니다. 자연 순서가 없는 원소를 비교하려다 실패하는 것입니다.

null을 넣을 수 있는지

HashSet과 LinkedHashSet은 null을 원소 하나로 받아 줍니다. null에는 hashCode를 호출할 수 없으므로, OpenJDK 구현은 null의 해시 값을 0으로 정해 따로 처리합니다. 자연 순서를 쓰는 TreeSet은 null을 다른 값과 비교할 방법이 없으므로 add(null)에서 NullPointerException을 던집니다. 비교자를 넘긴 경우에는 그 비교자가 null을 다룰 수 있는지에 달려 있습니다. 예를 들어 Comparator.nullsFirst(Comparator.naturalOrder())를 넘기면 null을 맨 앞에 두는 TreeSet을 만들 수 있습니다.

그렇다고 HashSet이 null을 받아 주니 편하다고 생각할 일은 아닙니다. 태그 목록에 null이 들어왔다면 대개 입력 처리의 버그입니다. 구현에 따라 우연히 받아들여지거나 거부되게 두기보다, 집합에 넣기 전에 직접 검사해서 거부하는 편이 안전합니다. 앞 글에서 만든 해시 집합이 Objects.requireNonNull로 null을 막은 것도 같은 이유입니다.

세 구현을 한 표로 비교하기

지금까지 본 차이를 한 표로 모으면 다음과 같습니다. 여기서 n은 원소 수입니다.

해시 기반 두 구현의 평균 O(1)에는 조건이 붙습니다. Javadoc의 표현으로는 해시 함수가 원소를 버킷에 고르게 흩어 놓는다고 가정할 때의 성능입니다. 원소 클래스의 hashCode가 많은 원소에 같은 값을 돌려준다면 그 원소들은 한 버킷에 몰리고, 그 버킷 안에서는 원소를 하나씩 비교해야 합니다.

더 깊이: 한 버킷에 충돌이 몰리면 (OpenJDK 구현)

앞 글의 학습용 구현처럼 버킷을 목록으로만 관리하면, 모든 원소가 한 버킷에 모였을 때 contains 한 번에 O(n)이 걸립니다. OpenJDK는 Java 8부터 이 최악의 경우를 완화합니다(JEP 180). 이미 원소가 8개 있는 버킷에 하나를 더 넣을 때, 버킷 배열이 64칸 이상이면 그 버킷의 연결 목록을 레드-블랙 트리로 바꿉니다. 배열이 64칸보다 작으면 트리로 바꾸는 대신 배열을 두 배로 키워 원소가 흩어지기를 먼저 기대합니다. 트리가 된 버킷은 원소를 해시 값 순으로 정렬해 둡니다. 해시 값까지 같은 원소끼리는, 두 원소가 같은 클래스이고 그 클래스가 String처럼 자기 타입과 비교하는 Comparable을 구현했다면 compareTo 순서로 정렬합니다. 그래서 해시 값이 모두 같더라도 그런 원소라면 O(log n)에 가깝게 찾을 수 있습니다. 그렇지 않은 원소는 여전히 느려질 수 있으므로, 근본적인 해결책은 hashCode를 고르게 퍼지도록 만드는 것입니다.

게시글 태그에는 어떤 Set을 쓸까

세 구현 중 무엇을 고를지는 '중복을 막아야 하는가'로 정해지지 않습니다. 셋 다 중복을 막기 때문입니다. 실제로 선택을 가르는 질문은 '순서가 기능의 일부인가'와 '범위 검색이 필요한가'입니다. 게시글 태그를 예로 들면 다음과 같습니다.

• 작성자가 입력한 순서대로 태그를 보여 줘야 한다면, 그 순서가 저장 규칙이므로 LinkedHashSet을 씁니다.
• 검색용 내부 색인이라 순서가 어디에도 드러나지 않는다면, 가장 단순한 HashSet으로 충분합니다.
• 자동 완성 목록처럼 언제나 사전순이어야 하고 'ja로 시작하는 태그' 같은 범위 검색도 한다면 TreeSet을 고려합니다.

자주 하는 실수는 화면에 정렬해서 보여 줘야 한다는 이유만으로 저장 구조를 TreeSet으로 바꾸는 것입니다. 저장할 때 지킬 순서와 화면에 보여 줄 순서는 다른 문제입니다. 다음 코드는 태그를 등록 순서대로 저장하고, 검색 화면에 보여 줄 때만 정렬한 복사본을 만듭니다.

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[] {"Tree", "hash", "Set", "HASH", "set"}) {
            tags.add(raw.toLowerCase(Locale.ROOT));
        }
        System.out.println("registration-order=" + tags);
        System.out.println("search-view=" + tags.stream().sorted().toList());
    }
}

registration-order=[tree, hash, set]
search-view=[hash, set, tree]

입력된 다섯 태그를 소문자로 바꾸면 tree, hash, set, hash, set이 되므로, 대소문자만 달랐던 HASH와 두 번째 set은 중복으로 걸러졌습니다. Locale.ROOT는 실행 환경의 언어 설정에 따라 대소문자 변환 결과가 달라지는 일을 막으려고 넣었습니다. 첫 줄은 처음 등록된 순서 그대로입니다. 둘째 줄의 tags.stream().sorted().toList()는 원소를 정렬한 새 List를 만들 뿐 tags의 순서는 바꾸지 않습니다. 스트림은 32장에서 자세히 다룹니다. 이렇게 저장 규칙과 표시 방식을 나눠 두면, 나중에 화면의 정렬 기준이 바뀌어도 저장 구조는 그대로 둘 수 있습니다.

메서드가 집합을 돌려줄 때도 같은 생각이 필요합니다. 반환하는 집합의 순서를 문서에 약속했다면, 내부 구현을 LinkedHashSet에서 HashSet으로 바꾸는 것은 성능 개선이 아니라 기능 변경입니다. 반대로 순서를 약속한 적이 없는데 호출하는 쪽이 지금 출력되는 순서에 기대고 있다면, 고쳐야 할 것은 호출하는 쪽입니다. Java 21부터는 반환 타입을 SequencedSet으로 선언해서, 순서가 있는 집합이라는 사실을 타입으로 드러낼 수도 있습니다.

정리

• HashSet, LinkedHashSet, TreeSet은 모두 중복을 거부하지만 반복 순서가 다릅니다. HashSet은 순서를 보장하지 않고, LinkedHashSet은 처음 넣은 순서를, TreeSet은 정렬 순서를 보장합니다.
• HashSet의 순서는 같은 원소라도 테이블 크기, 초기 용량, JDK 버전에 따라 바뀔 수 있으므로 화면 표시나 테스트에 쓰면 안 됩니다.
• LinkedHashSet에서 이미 있는 원소를 다시 add하면 자리가 그대로이고, 지웠다가 다시 넣으면 맨 뒤로 갑니다.
• TreeSet은 O(log n)으로 정렬 순서와 lower, floor, ceiling, higher, subSet 같은 범위 검색을 제공합니다. 범위 메서드가 돌려주는 집합은 원본과 연결된 뷰입니다.
• TreeSet은 equals가 아니라 비교 결과로 같은 원소를 판단하므로, 비교 결과가 0인 경우가 equals와 일치하도록 비교 기준을 만들어야 합니다.
• 저장할 때 지킬 순서와 화면에 보여 줄 순서를 구분하면, 대부분의 경우 선택이 자연스럽게 정해집니다.

연습 문제

1. TreeSet에 20, 45, 60, 90이 들어 있습니다. lower(45), floor(45), ceiling(45), higher(45), lower(20)의 결과를 예측하세요.

2. 위 TreeSetBackedRangeView에서처럼 all이 [20, 45, 60, 90]이고 range가 all.subSet(40, true, 80, false)라고 합시다. Set<Integer> copy = new TreeSet<>(range);로 복사한 뒤 copy.remove(60)을 호출하면 all과 range는 어떻게 되나요? 복사 대신 range.add(80)을 먼저 호출하면 어떻게 되나요?

3. 다음 코드의 출력을 예측하고, 그 이유를 설명하세요. String.CASE_INSENSITIVE_ORDER는 대소문자를 무시하고 문자열을 비교하는 비교자입니다.

   Set<String> tags = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
   System.out.println(tags.add("Hash"));
   System.out.println(tags.add("hash"));
   System.out.println(tags.add("Set"));
   System.out.println(tags + ", contains-SET=" + tags.contains("SET"));

true
false
true
[Hash, Set], contains-SET=true

다음 글

Set으로 합집합·교집합·차집합 구하기에서는 addAll, retainAll, removeAll로 두 집합의 합집합, 교집합, 차집합을 구합니다. 이 메서드들은 호출한 집합을 직접 바꾸기 때문에, 원본을 지키면서 연산하는 방법도 함께 다룹니다.