Set으로 합집합·교집합·차집합 구하기

지금까지는 Set을 주로 중복을 막는 도구로 썼습니다. 그런데 집합은 '어느 그룹에 속하는가'를 나타내는 데도 잘 맞습니다. 자바 게시판과 스프링 게시판에 모두 달린 태그는 두 태그 집합의 교집합(intersection)이고, 둘 중 한 곳에라도 달린 태그는 합집합(union)입니다. 제출은 했지만 아직 공개되지 않은 게시글은 제출 집합에서 공개 집합을 뺀 차집합(difference)입니다. 세 연산을 원소가 들어가는 조건으로 정의하는 방법은 집합의 표현과 연산에서 자세히 다룹니다.

자바의 Set에는 union처럼 결과를 새 집합으로 돌려주는 메서드가 없습니다. 대신 Collection 인터페이스에 정의된 addAll, retainAll, removeAll을 쓰는데, 이 세 메서드는 호출한 집합 자체를 바꿉니다. 이 사실을 모르면 교집합을 구하다가 원래 데이터를 잃어버리게 됩니다. 이 글에서는 세 메서드가 하는 일을 확인하고, 원본을 지키면서 연산하는 방법과 연산 결과를 검산하는 방법을 익힌 뒤 게시글 저장소에 적용합니다.

세 메서드가 하는 일

두 집합 a와 b가 있을 때, a에서 각 메서드를 호출하면 다음과 같이 됩니다.

Set의 Javadoc도 인수가 집합일 때 세 메서드가 호출한 집합을 각각 합집합, 교집합, 차집합으로 바꾼다고 설명합니다. 결과가 담기는 곳은 언제나 a이고, b는 원소를 확인하는 데만 쓰일 뿐 바뀌지 않습니다. 반환값은 결과 집합이 아니라 boolean이며, Collection의 Javadoc에 따르면 '이 호출로 a가 바뀌었는가'를 뜻합니다. 예를 들어 a.addAll(b)는 b의 원소가 모두 이미 a에 있었다면 아무것도 추가하지 못하므로 false를 돌려줍니다. 앞 글들에서 add가 새 원소를 넣었는지를 boolean으로 알려 준 것과 같은 방식입니다.

이름도 이 동작을 그대로 말합니다. retainAll(b)는 'b에 있는 것만 남겨라', removeAll(b)는 'b에 있는 것을 모두 지워라'라는 뜻입니다. 두 집합을 받아 결과를 만들어 주는 함수가 아니라, 호출한 집합에게 내리는 명령입니다.

retainAll이 원본을 바꿔 버리는 실수

공개된 게시글 제목 집합과 추천 게시글 제목 집합이 있습니다. 공개도 되었고 추천도 된 제목을 구하려고 공개 집합에 바로 retainAll을 호출하면 어떻게 되는지 보겠습니다.

import java.util.HashSet;
import java.util.Set;

public final class DestructiveIntersectionBug {
    public static void main(String[] args) {
        Set<String> published = new HashSet<>(Set.of("array", "hash", "thread"));
        Set<String> featured = Set.of("hash", "thread", "lock");
        System.out.println("changed=" + published.retainAll(featured));
        System.out.println("common=" + published);
        System.out.println("published-count=" + published.size());
        System.out.println("changed-again=" + published.retainAll(featured));
    }
}

JDK 21에서 실행한 결과입니다. common의 순서는 HashSet이 정한 것이므로 환경에 따라 다를 수 있습니다.

changed=true
common=[thread, hash]
published-count=2
changed-again=false

공통 제목 hash와 thread는 제대로 구했습니다. 문제는 그 결과가 published에 담겼다는 것입니다. featured에 없는 array가 지워졌으므로 첫 줄은 true이고, 공개된 게시글이 원래 3개였다는 정보는 사라졌습니다. 이 코드 뒤에서 공개 게시글 수를 세는 코드가 있다면 3이 아니라 2를 받게 됩니다.

마지막 줄도 눈여겨볼 만합니다. 같은 호출을 한 번 더 하면 이번에는 더 지울 원소가 없으므로 false가 나옵니다. 하지만 false라고 해서 원본이 되돌아온 것은 아니고, published는 여전히 2개입니다. 반환값은 이번 호출이 무언가를 바꿨는지만 알려 줄 뿐입니다.

고치는 방법은 간단합니다. 원본을 계속 써야 한다면, 먼저 복사본을 만들고 그 복사본에서 연산합니다.

Set<String> common = new HashSet<>(published);
common.retainAll(featured);

new HashSet<>(published)는 published의 원소를 모두 담은 새 집합을 만들기 때문에, 이후의 retainAll은 common만 바꿉니다. 원본이 Set.of(...)로 만든 수정할 수 없는(unmodifiable) 집합일 때도 이 복사 단계가 필요합니다. Set의 Javadoc에 따르면 이런 집합에서는 원소를 바꾸는 메서드를 호출하기만 해도 UnsupportedOperationException이 발생합니다. 실제로 바뀌는 원소가 없는 호출이라도 마찬가지입니다.

원본을 바꾸지 않는 집합 연산 메서드 만들기

복사하고 연산하는 일을 매번 손으로 하다 보면 언젠가 복사를 빠뜨립니다. 그래서 복사부터 결과 반환까지를 메서드 하나로 묶어 두면 편합니다. 다음 코드는 자바 게시판과 스프링 게시판의 태그로 세 연산을 해 봅니다.

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public final class SetOperationToolkit {
    public static void main(String[] args) {
        Set<String> java = Set.of("array", "hash", "thread");
        Set<String> spring = Set.of("http", "thread", "database");
        System.out.println("union=" + sorted(union(java, spring)));
        System.out.println("intersection=" + sorted(intersection(java, spring)));
        System.out.println("java-only=" + sorted(difference(java, spring)));
        System.out.println("inputs=" + java.size() + "/" + spring.size());
    }

    static <E> Set<E> union(Set<? extends E> left, Set<? extends E> right) {
        Set<E> result = new HashSet<>(left);
        result.addAll(right);
        return Set.copyOf(result);
    }

    static <E> Set<E> intersection(Set<? extends E> left, Set<?> right) {
        Set<E> result = new HashSet<>(left);
        result.retainAll(right);
        return Set.copyOf(result);
    }

    static <E> Set<E> difference(Set<? extends E> left, Set<?> right) {
        Set<E> result = new HashSet<>(left);
        result.removeAll(right);
        return Set.copyOf(result);
    }

    private static <E extends Comparable<? super E>> List<E> sorted(Set<E> values) {
        return values.stream().sorted().toList();
    }
}

union=[array, database, hash, http, thread]
intersection=[thread]
java-only=[array, hash]
inputs=3/3

세 메서드는 모두 같은 순서로 일합니다. 왼쪽 집합을 새 HashSet에 복사하고, 그 복사본에서 연산한 뒤, Set.copyOf로 수정할 수 없는 집합을 만들어 돌려줍니다. 그래서 마지막 줄처럼 두 입력은 연산 뒤에도 3개씩 그대로이고, 호출한 쪽이 결과 집합을 받아서 실수로 바꾸려 해도 예외가 발생합니다. 다만 Set.copyOf가 복사하는 것은 원소를 가리키는 참조이지 원소 객체 자체가 아닙니다. 원소가 가변 객체라면 그 내용은 여전히 바뀔 수 있습니다.

매개변수 타입이 조금씩 다른 이유도 짚어 보겠습니다. union의 두 매개변수와 다른 메서드의 left는 결과에 들어갈 원소를 내주는 쪽이므로 Set<? extends E>로 받습니다. 반면 intersection과 difference의 right는 원소가 들어 있는지 확인하는 데만 쓰이고, retainAll과 removeAll도 인수를 Collection<?>로 받으므로 어떤 타입의 집합이든 받을 수 있게 Set<?>로 두었습니다. 와일드카드를 이렇게 고르는 기준은 생산자·소비자 와일드카드를 다룬 글에서 설명했습니다.

출력할 때 sorted로 정렬한 데도 이유가 있습니다. Set.of와 Set.copyOf가 만든 집합의 반복 순서는 Javadoc상 정해져 있지 않습니다. 게다가 OpenJDK는 JVM을 시작할 때마다 이 순서를 일부러 섞도록 구현되어 있어서(Javadoc이 약속한 동작이 아니라 구현 방식입니다), 정렬하지 않고 출력하면 같은 프로그램도 실행할 때마다 다른 순서로 출력될 수 있습니다. 정렬해 두면 결과를 눈으로 비교하거나 테스트의 기대값으로 쓰기 쉽습니다.

이 도우미 메서드는 null이 아닌 원소만 다룬다고 가정합니다. HashSet에는 null을 넣을 수 있지만, 마지막 단계의 Set.copyOf는 null 원소가 있으면 NullPointerException을 던지기 때문입니다. null도 의미 있는 원소로 다뤄야 한다면, 결과를 Set.copyOf 대신 다른 방법으로 감싸야 합니다.

결과 크기로 검산하기

집합 연산의 결과가 맞는지 확인할 때는 크기 사이의 관계를 이용할 수 있습니다. 합집합은 두 집합을 그냥 더하면 공통 원소를 두 번 세게 되므로, 합집합의 크기는 두 크기의 합에서 교집합의 크기를 뺀 값이고, 이를 포함·배제의 원리라고 합니다. 위 예제에 대입하면 3 + 3 − 1 = 5이고, 실제로 union에는 원소가 5개 있습니다.

left는 right와 겹치는 부분(교집합)과 겹치지 않는 부분(차집합)으로 빈틈없이 나뉩니다. 그래서 차집합의 크기와 교집합의 크기를 더하면 left의 크기가 됩니다. 위 예제에서는 2 + 1 = 3입니다. 이런 관계가 어긋난다면 연산 코드나 원소의 동등성 구현 어딘가에 문제가 있다는 뜻입니다. 거꾸로 크기가 맞는다고 해서 어떤 원소가 들어 있는지까지 맞는 것은 아니므로, 크기 검산은 원소 확인을 대신하지 못하고 보조하는 역할만 합니다.

연산 결과가 이상하다면 equals와 hashCode부터

HashSet과 LinkedHashSet에서 세 메서드는 결국 원소 하나하나가 집합에 들어 있는지를 확인하며 동작합니다. 그리고 그 확인은 equals와 hashCode를 다룬 글에서 본 것처럼 hashCode로 버킷을 찾고 equals로 비교하는 방식입니다. 그래서 원소 클래스의 equals와 hashCode가 잘못되어 있으면, 연산 코드에는 아무 문제가 없어도 결과가 틀립니다. 다음 Tag 클래스는 equals만 재정의하고 hashCode는 재정의하지 않았습니다.

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public final class BrokenTagSetOperation {
    public static void main(String[] args) {
        Set<Tag> java = new HashSet<>(List.of(new Tag("java"), new Tag("hash")));
        Set<Tag> spring = new HashSet<>(List.of(new Tag("hash"), new Tag("spring")));

        Set<Tag> union = new HashSet<>(java);
        union.addAll(spring);
        Set<Tag> common = new HashSet<>(java);
        common.retainAll(spring);

        System.out.println("equals=" + new Tag("hash").equals(new Tag("hash")));
        System.out.println("union-size=" + union.size());
        System.out.println("common=" + common);
    }

    private static final class Tag {
        private final String name;

        Tag(String name) {
            this.name = name;
        }

        @Override
        public boolean equals(Object other) {
            return other instanceof Tag tag && tag.name.equals(name);
        }

        // hashCode는 재정의하지 않았다

        @Override
        public String toString() {
            return name;
        }
    }
}

equals=true
union-size=4
common=[]

첫 줄을 보면 이름이 같은 두 Tag는 equals로 분명히 같습니다. 그런데 java, hash, spring 세 태그의 합집합 크기가 4이고, 공통 태그 hash가 들어 있어야 할 교집합은 비어 있습니다. hashCode를 재정의하지 않으면 Object의 기본 구현이 쓰이는데, 이 구현은 가능한 한 객체마다 서로 다른 값을 돌려줍니다. 그래서 두 Tag("hash")는 equals로는 같아도 해시 값은 거의 언제나 다릅니다. HashSet은 같은 원소라면 해시 값도 같다는 규칙을 믿고 해시 값으로 버킷을 고르므로, 해시 값이 다른 두 원소는 대개 서로 다른 버킷에서 찾게 됩니다. 게다가 OpenJDK 구현은 같은 버킷에 들어가더라도 저장해 둔 해시 값부터 비교하고, 해시 값이 다르면 equals를 아예 호출하지 않습니다. 합집합에서는 두 번째 hash가 새 원소로 추가되었고, 교집합에서는 spring 집합에서 hash를 찾지 못해 지워 버린 것입니다.

해결 방법은 equals와 같은 필드로 hashCode를 재정의하는 것입니다. Tag를 toString 재정의만 남긴 private record Tag(String name)으로 바꾸면, 컴파일러가 name을 기준으로 equals와 hashCode를 함께 만들어 주므로 같은 코드에서 union-size=3, common=[hash]가 나옵니다. 이런 실수는 컴파일러의 도움을 받아 미리 찾을 수도 있습니다. javac -Xlint:overrides로 컴파일하면 위 코드에서 Class Tag overrides equals, but neither it nor any superclass overrides hashCode method라는 경고가 나옵니다. 기본 설정에서는 이 경고가 나오지 않으니 옵션을 켜야 합니다.

인수의 종류를 바꾸면 결과가 달라지기도 합니다. common.retainAll(spring) 대신 common.retainAll(List.copyOf(spring))처럼 인수로 List를 넘기면 [hash]가 나옵니다. List의 contains는 해시를 쓰지 않고 equals로만 비교하기 때문입니다. 같은 원소로 같은 연산을 했는데 인수의 종류에 따라 결과가 달라진다면, 연산 코드가 아니라 원소 클래스의 equals와 hashCode가 서로 맞지 않는다는 신호입니다.

더 깊이: 인수 컬렉션의 종류가 속도를 바꿉니다

HashSet은 retainAll을 직접 구현하지 않고 AbstractCollection에서 물려받습니다. AbstractCollection.retainAll의 Javadoc에 적힌 방식대로, 이 메서드는 호출한 집합의 원소를 하나씩 꺼내 인수 컬렉션의 contains로 확인하고, 없으면 지웁니다. 그래서 전체 시간은 '호출한 집합의 크기 × 인수의 contains 한 번 비용'입니다. 인수가 HashSet이면 contains가 평균 O(1)이라 전체가 O(n)이지만, 원소가 m개인 ArrayList를 넘기면 contains마다 목록을 처음부터 훑으므로 O(n × m)이 됩니다. 원소가 수만 개씩이라면 큰 차이입니다.

removeAll은 AbstractSet이 따로 구현합니다. AbstractSet.removeAll의 Javadoc에 따르면, 두 컬렉션 중 크기가 작은 쪽을 훑습니다. 호출한 집합이 더 작으면 그 원소마다 인수의 contains를 부르고, 인수가 더 작으면 인수의 원소마다 호출한 집합의 remove를 부릅니다. 어느 경우든 큰 목록을 인수로 넘길 일이 있다면 먼저 new HashSet<>(list)로 바꿔 넘기는 편이 안전합니다.

중복을 없애면서 처음 순서 지키기

집합 연산과 함께 자주 하는 일이 목록에서 중복을 없애는 것입니다. new HashSet<>(list)로도 중복은 사라지지만, 앞 글에서 본 것처럼 HashSet은 순서를 보장하지 않습니다. 처음 등장한 순서를 지켜야 한다면 LinkedHashSet을 거쳐 다시 List로 만듭니다.

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

public final class OrderedDuplicateRemoval {
    public static void main(String[] args) {
        List<String> input = List.of("array", "hash", "array", "set", "hash");
        List<String> unique = new ArrayList<>(new LinkedHashSet<>(input));
        System.out.println("input=" + input);
        System.out.println("unique=" + unique);
        System.out.println("first-array=" + unique.indexOf("array"));
    }
}

input=[array, hash, array, set, hash]
unique=[array, hash, set]
first-array=0

LinkedHashSet은 두 번째 array와 두 번째 hash를 중복으로 거부하므로, 각 문자열이 처음 등장한 순서인 array, hash, set만 남습니다. 집합에는 인덱스가 없지만, 이 집합을 new ArrayList<>(...)에 넘기면 집합의 반복 순서대로 원소를 담은 목록이 만들어집니다. 그래서 indexOf 같은 목록 메서드를 다시 쓸 수 있고, array의 위치는 0입니다. 같은 일을 스트림으로 하려면 input.stream().distinct().toList()라고 쓸 수 있습니다. distinct도 순서가 있는 스트림에서는 처음 나온 원소를 남깁니다.

목표에 따라 고르는 방법은 다음과 같습니다.

• 순서가 상관없다면 new HashSet<>(list)
• 처음 등장한 순서를 지키려면 new ArrayList<>(new LinkedHashSet<>(list)) 또는 list.stream().distinct().toList()
• 정렬된 결과가 필요하면 new TreeSet<>(list) 또는 list.stream().distinct().sorted().toList()

어떤 방법이든 무엇을 같은 원소로 볼지는 집합이 정합니다. 해시 기반 집합은 equals와 hashCode로, TreeSet은 비교 결과가 0인지로 판단합니다. "Hash"와 "hash"를 같은 태그로 보고 싶다면, 집합에 넣기 전에 소문자로 바꾸는 식으로 값을 정규화해야 합니다. 그런데 정규화하면 사용자가 처음 입력한 표기가 사라집니다. 원래 표기도 보여 줘야 한다면 정규화한 값을 키로, 원래 표기를 값으로 저장하는 Map이 알맞습니다. Map은 다음 장에서 다룹니다.

게시글 저장소의 공개 대기 목록 구하기

이제 게시글 저장소에 적용해 보겠습니다. 작성자가 제출한 게시글 제목 집합과 실제로 공개된 제목 집합이 있을 때, 공개를 기다리는 게시글은 제출 집합에서 공개 집합을 뺀 차집합입니다.

이때 크기의 차이로 대기 수를 계산하면 안 됩니다. 공개 집합에 제출 기록이 없는 제목이 섞여 있을 수 있기 때문입니다. 예를 들어 제출이 {array, hash}이고 공개가 {hash, orphan}이라면 두 크기는 모두 2이므로 2 − 2 = 0이지만, array는 아직 공개되지 않았으므로 실제 대기는 1개입니다. 크기만 보지 말고 어떤 원소가 어느 집합에 속하는지를 계산해야 합니다. 다음 코드는 제출 집합과 공개 집합을 복사해 유효하게 공개된 제목, 공개 대기 제목, 제출 기록이 없는 제목을 각각 구합니다.

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

public final class BoardPublicationSetCli {
    public static void main(String[] args) {
        Set<String> submitted = new LinkedHashSet<>(List.of("array", "hash", "set", "map"));
        Set<String> published = Set.of("array", "hash", "orphan");
        Set<String> validPublished = copy(submitted);
        validPublished.retainAll(published);
        Set<String> pending = copy(submitted);
        pending.removeAll(published);
        Set<String> unknown = copy(published);
        unknown.removeAll(submitted);
        System.out.println("published=" + validPublished);
        System.out.println("pending=" + pending);
        System.out.println("unknown=" + unknown);
        System.out.println("published-count=" + validPublished.size() + "/" + submitted.size());
    }

    private static <E> Set<E> copy(Set<E> source) {
        return new LinkedHashSet<>(source);
    }
}

published=[array, hash]
pending=[set, map]
unknown=[orphan]
published-count=2/4

세 결과는 모두 원본이 아니라 copy로 만든 복사본에서 계산했으므로, submitted와 published는 어느 연산 뒤에도 그대로입니다. validPublished와 pending은 제출 집합의 LinkedHashSet 복사본에서 원소를 지우기만 했기 때문에, 남은 원소들이 제출 순서를 유지합니다. 그래서 published=[array, hash]와 pending=[set, map]이 제출 순서대로 출력되었습니다. unknown은 공개 집합에서 제출 집합을 뺀 결과이고, 제출 기록 없이 공개된 orphan이 여기서 드러납니다. 이 제목은 유효한 공개 수에 넣지 않고 따로 확인할 대상으로 분리했으므로, 공개 비율은 3/4가 아니라 2/4입니다. 앞의 검산 규칙대로 유효 공개 2개와 대기 2개를 더하면 제출 4개가 됩니다.

정리

• addAll, retainAll, removeAll은 각각 합집합, 교집합, 차집합을 구하지만, 결과를 새 집합으로 돌려주지 않고 호출한 집합을 바꿉니다. 반환값은 '이 호출로 집합이 바뀌었는가'를 뜻하는 boolean입니다.
• 원본을 계속 써야 하거나 원본이 Set.of처럼 수정할 수 없는 집합이라면, 복사본을 만든 뒤 연산합니다. 복사부터 반환까지를 메서드 하나로 묶어 두면 복사를 빠뜨리는 실수를 막을 수 있습니다.
• 합집합의 크기는 두 크기의 합에서 교집합의 크기를 뺀 값이고, 차집합과 교집합의 크기를 더하면 왼쪽 집합의 크기입니다. 이 관계로 결과를 검산할 수 있습니다.
• 해시 기반 집합의 연산 결과가 이상하다면 원소 클래스의 equals와 hashCode가 서로 맞는지부터 확인합니다.
• 중복을 없애면서 처음 순서를 지키려면 LinkedHashSet을 거치거나 스트림의 distinct를 씁니다.

연습 문제

1. 다음 코드의 출력을 예측하세요. 각 줄이 왜 그렇게 나오는지도 설명하세요.

   Set<String> s = new HashSet<>(Set.of("a", "b"));
   System.out.println(s.addAll(Set.of("b")));
   System.out.println(s.removeAll(Set.of("c")));
   System.out.println(s.retainAll(Set.of("a", "b", "c")));
   System.out.println(s.retainAll(Set.of("a")));
   System.out.println(s);

2. 제출 집합이 {array, hash}, 공개 집합이 {hash, orphan}입니다. 유효하게 공개된 제목, 공개 대기 제목, 제출 기록이 없는 제목을 각각 구하세요. 두 집합의 크기 차이가 대기 수와 같은지도 확인하세요.

3. 세 게시판의 태그 집합 a = {java, hash, set}, b = {java, set, map}, c = {java, map, queue}가 있습니다. 세 게시판에 모두 달린 태그와, 적어도 한 게시판에 달린 태그를 구하는 프로그램을 작성하세요. 연산이 끝난 뒤에도 세 원본 집합의 크기는 3이어야 합니다. 코드를 쓰기 전에 두 결과의 원소를 먼저 적어 보세요.

false
false
false
true
[a]

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

public final class ThreeBoardTagSetSolution {
    public static void main(String[] args) {
        Set<String> a = Set.of("java", "hash", "set");
        Set<String> b = Set.of("java", "set", "map");
        Set<String> c = Set.of("java", "map", "queue");
        Set<String> common = new LinkedHashSet<>(a);
        common.retainAll(b);
        common.retainAll(c);
        Set<String> all = new LinkedHashSet<>();
        all.addAll(a);
        all.addAll(b);
        all.addAll(c);
        System.out.println("common=" + common);
        System.out.println("all=" + all.stream().sorted().toList());
        System.out.println("unchanged=" + a.size() + "/" + b.size() + "/" + c.size());
    }
}

common=[java]
all=[hash, java, map, queue, set]
unchanged=3/3/3

다음 장

이 장에서는 해시 코드로 버킷을 고르고 equals로 원소를 구별하는 원리에서 시작해, 표준 Set 구현을 고르고 집합 연산을 쓰는 데까지 왔습니다. 16장에서는 키와 값을 짝지어 저장하는 Map을 다룹니다. 이 글에서 정규화한 태그와 원래 표기를 함께 보관하려면 필요하다고 했던 바로 그 자료구조입니다. HashMap, LinkedHashMap, TreeMap은 이 장에서 본 세 Set 구현과 같은 방식으로 키를 관리하므로, 여기서 익힌 순서와 비용의 차이가 그대로 이어집니다.