수정할 수 없는 목록과 정렬 결과 다루기

배열에 담긴 태그를 List로 바꾸고 싶다고 해 봅시다. Arrays.asList(tags), List.of(...), List.copyOf(...), new ArrayList<>(...) 가운데 무엇을 써도 List<String>이 나오고, 출력해 보면 모두 [array, list]처럼 똑같아 보입니다. 하지만 이 목록들은 세 가지 질문에 서로 다르게 답합니다. 원소를 추가하거나 바꿀 수 있는가, 원본 배열이나 목록과 내용을 공유하는가, null 원소를 받아들이는가입니다. 이 차이를 모르고 고르면 add를 호출하는 순간 예외가 나거나, 밖에서 바꾼 배열 내용이 내 목록에 그대로 번집니다.

정렬도 같은 질문을 던져야 합니다. list.sort(...)는 그 목록 자체의 순서를 바꾸고, 스트림의 sorted()는 원본을 그대로 두고 정렬된 새 목록을 만듭니다. 이 글에서는 작은 프로그램으로 목록을 만드는 방법들의 차이를 확인한 뒤, 원본을 바꾸는 정렬과 정렬된 사본을 비교합니다. 이어서 비교 결과가 같은 동점 원소를 List와 TreeSet이 어떻게 다르게 다루는지, 정렬된 목록에서 이진 탐색 결과를 어떻게 읽는지 살펴봅니다. 비교자(Comparator)를 만드는 방법은 앞 글에서 다뤘습니다.

Arrays.asList는 배열을 감싼 고정 크기 목록이다

용도에 맞는 List 고르기에서 Arrays.asList로 만든 목록에 add를 호출하면 예외가 난다는 것을 보았습니다. 이유는 이 메서드가 하는 일에 있습니다. Arrays.asList(array)는 배열의 원소를 새 저장소로 복사하지 않고, 배열 자체를 List 모양으로 감싸서 돌려줍니다. 이렇게 데이터를 따로 복사해 두지 않고 원본을 그대로 들여다보는 객체를 뷰(view)라고 합니다. 목록의 get(0)은 배열의 0번 칸을 읽고, set(0, ...)은 배열의 0번 칸에 씁니다.

다음 프로그램은 뷰를 만든 뒤 원본 배열의 칸을 바꾸고, 이어서 뷰에 원소를 추가해 봅니다. 두 동작 가운데 무엇이 뷰에 반영되고 무엇이 실패하는지 확인해 보세요.

import java.util.Arrays;
import java.util.List;

public final class FixedSizeListAddFailure {
    public static void main(String[] args) {
        String[] source = {"array", "list"};
        List<String> view = Arrays.asList(source);
        source[0] = "changed";
        System.out.println("view=" + view);
        view.add("failure");
    }
}

view=[changed, list]
Exception in thread "main" java.lang.UnsupportedOperationException

예외 줄 아래에는 at으로 시작하는 스택 트레이스가 이어지는데, 여기서는 생략했습니다. 첫 줄에서 view는 changed를 보여 줍니다. 목록을 만든 뒤에 배열의 0번 칸을 바꿨을 뿐 목록에는 손대지 않았지만, 목록이 그 칸을 직접 읽기 때문입니다. 반대 방향도 마찬가지여서 view.set(1, "x")를 호출하면 배열의 1번 칸이 바뀝니다.

add가 실패하는 이유도 같은 데서 나옵니다. 자바 배열은 한 번 만들면 길이를 바꿀 수 없는데, 뷰에는 배열 말고 원소를 둘 곳이 없습니다. 그래서 크기를 바꾸는 add와 remove는 지원하지 않고 UnsupportedOperationException을 던집니다. 이름 때문에 헷갈리기 쉬운데, OpenJDK에서 Arrays.asList가 돌려주는 객체는 java.util.ArrayList가 아니라 Arrays 클래스 안에 따로 정의된 같은 이름의 중첩 클래스입니다. 이 클래스는 get과 set은 직접 구현하지만 add는 부모인 AbstractList의 기본 구현을 그대로 쓰고, 그 기본 구현이 예외를 던집니다. 생략한 스택 트레이스의 첫 줄이 AbstractList.add인 것도 이 때문입니다.

배열과 연결이 끊긴 목록이 필요하면 복사해야 합니다. 원소를 자유롭게 추가하고 지울 목록이면 new ArrayList<>(Arrays.asList(source))처럼 ArrayList 생성자에 넘기고, 읽기만 할 목록이면 List.copyOf(Arrays.asList(source))로 수정할 수 없는 사본을 만듭니다. 어느 쪽이든 복사한 뒤에는 배열의 칸을 바꿔도 목록에 반영되지 않습니다.

목록을 만드는 방법별 차이

List를 만드는 대표적인 방법을 세 가지 질문으로 정리하면 다음과 같습니다. 여기서 수정할 수 없다(unmodifiable)는 것은 add, remove, set 같은 변경 메서드를 호출하면 언제나 UnsupportedOperationException이 난다는 뜻입니다.

마지막 줄의 Collections.unmodifiableList는 변경 메서드만 막은 뷰입니다. 이 뷰를 통해서는 목록을 바꿀 수 없지만, 원본 목록이 바뀌면 그 내용이 뷰에도 그대로 보입니다. 돌려받은 컬렉션이 원본과 연결이 끊긴 사본인지 원본을 들여다보는 뷰인지는 다음 글에서 컬렉션을 반환하는 방법을 고를 때 다시 따집니다.

표에서 눈여겨볼 점은 수정할 수 있는지와 null을 허용하는지가 서로 다른 질문이라는 것입니다. 다음 프로그램은 null이 들어 있는 뷰를 스트림 결과와 List.copyOf로 각각 옮겨 봅니다.

import java.util.Arrays;
import java.util.List;

public final class ListNullBoundary {
    public static void main(String[] args) {
        List<String> view = Arrays.asList("array", null);
        List<String> streamResult = view.stream().toList();
        System.out.println("null-kept=" + (streamResult.get(1) == null));
        try {
            List.copyOf(view);
        } catch (NullPointerException expected) {
            System.out.println("copy rejects null");
        }
        try {
            streamResult.set(0, "changed");
        } catch (UnsupportedOperationException expected) {
            System.out.println("stream result rejects set");
        }
    }
}

null-kept=true
copy rejects null
stream result rejects set

Arrays.asList는 배열을 감쌀 뿐이므로 배열에 null이 있으면 그대로 보여 줍니다. Java 16에 추가된 Stream.toList()도 null을 그대로 담기 때문에 첫 줄이 true입니다. 반면 List.of와 List.copyOf는 설계상 null 원소를 받지 않아서, 목록을 만드는 순간 NullPointerException을 던집니다. 그렇다고 toList()의 결과를 고칠 수 있는 것은 아니어서, 마지막 줄처럼 set은 거부합니다.

그러니 'null을 담을 수 있다'와 '내용을 바꿀 수 있다'는 따로 확인해야 합니다. 이 차이는 메서드를 설계할 때도 드러납니다. 입력 목록을 List.copyOf로 복사해 보관하는 메서드는 null이 섞인 목록을 받으면 예외를 던지므로, 그런 입력을 받지 않는다는 조건을 문서에 적거나 미리 검사해야 호출하는 쪽이 놀라지 않습니다.

더 깊이: List.copyOf가 언제나 새 객체를 만들지는 않는다

List.copyOf의 Javadoc에는 '주어진 컬렉션이 이미 수정할 수 없는 목록이면 보통 복사하지 않는다'는 구현 메모가 있습니다. 실제로 OpenJDK 21에서 List.of로 만든 목록 im을 넘기면 List.copyOf(im) == im이 true입니다. 어차피 아무도 바꿀 수 없는 목록이므로 같은 객체를 함께 써도 문제가 없기 때문입니다. 그러니 List.copyOf의 결과가 원본과 다른 객체라고 가정하고 ==로 비교하는 코드를 짜면 안 됩니다. 이 메서드가 약속하는 것은 '돌려준 목록은 수정할 수 없고, 원본이 나중에 바뀌어도 영향을 받지 않는다'는 것까지입니다.

결과가 없을 때는 null 대신 빈 목록을 돌려준다

검색 결과처럼 개수가 정해지지 않은 목록을 돌려주는 메서드는 결과가 하나도 없을 때 무엇을 돌려줄지 정해야 합니다. null을 돌려주면 호출하는 쪽마다 if (result != null) 검사를 넣어야 하고, 한 군데라도 빠뜨리면 NullPointerException이 납니다. 게다가 null이 '찾아봤지만 없다'는 뜻인지 '아직 찾지 않았다'는 뜻인지도 알 수 없습니다. 결과가 0개라면 빈 목록을 돌려주는 편이 낫습니다.

import java.util.List;

public final class EmptyResultInsteadOfNull {
    public static void main(String[] args) {
        List<String> found = findByTag("rust");
        System.out.println("count=" + found.size());
        for (String title : found) {
            System.out.println("title=" + title);
        }
        System.out.println("done");
    }

    private static List<String> findByTag(String tag) {
        if (tag.equals("java")) {
            return List.of("hash", "queue");
        }
        return List.of();
    }
}

count=0
done

findByTag("rust")가 빈 목록을 돌려주므로 size()는 0이고, 향상된 for문은 한 번도 돌지 않고 끝납니다. 호출하는 쪽은 결과가 있든 없든 같은 코드로 처리할 수 있습니다. List.of()는 수정할 수 없는 빈 목록이라 호출자가 실수로 원소를 추가할 수도 없습니다. 집합과 맵에는 같은 역할을 하는 Set.of()와 Map.of()가 있습니다.

Collections.emptyList()도 수정할 수 없는 빈 목록을 돌려주므로 거의 같은 자리에 쓸 수 있습니다. 작은 차이가 하나 있는데, null을 허용하지 않는 List.of()는 contains(null)에서 NullPointerException을 던지고 Collections.emptyList()는 false를 돌려줍니다. 반대로 호출할 때마다 new ArrayList<>()를 돌려주면, 호출자는 이 목록을 바꿔도 되는지, 바꾸면 어딘가에 반영되는지 헷갈릴 수 있습니다. 돌려준 목록을 호출자가 고쳐 써도 된다는 것이 의도일 때만 가변 목록을 돌려줍니다.

원본을 정렬할까, 정렬된 사본을 만들까

앞 글에서 보았듯이 list.sort(comparator)와 Collections.sort(list)는 그 목록 객체 안에서 원소의 순서를 직접 바꾸고, 스트림의 sorted()는 원본을 두고 새 목록을 만듭니다. 대상 자체를 바꾸는 앞의 방식을 제자리(in-place) 정렬이라고 합니다. 그렇다면 어떤 목록을 제자리 정렬할 수 있을까요? List.sort의 Javadoc은 목록이 '수정할 수 있어야 하지만 크기를 바꿀 수 있을 필요는 없다'고 적고 있습니다. 정렬은 원소를 추가하거나 지우지 않고 각 칸의 원소를 다시 써 넣는 일이기 때문입니다. 앞에서 본 두 종류의 목록에 이 규칙을 적용해 보겠습니다.

import java.util.Arrays;
import java.util.List;

public final class SortChangesTarget {
    public static void main(String[] args) {
        String[] array = {"thread", "array", "hash"};
        List<String> view = Arrays.asList(array);
        view.sort(null);
        System.out.println("array=" + Arrays.toString(array));

        List<String> fixed = List.of("thread", "array", "hash");
        try {
            fixed.sort(null);
        } catch (UnsupportedOperationException e) {
            System.out.println("List.of sort -> " + e.getClass().getSimpleName());
        }
    }
}

array=[array, hash, thread]
List.of sort -> UnsupportedOperationException

sort(null)은 비교자 대신 원소의 자연 순서, 여기서는 문자열의 사전순으로 정렬하라는 뜻입니다. Arrays.asList의 뷰는 크기를 바꿀 수는 없어도 칸의 내용은 바꿀 수 있으므로 정렬할 수 있습니다. 그리고 뷰는 배열에 직접 쓰므로, 정렬이 끝나면 원본 배열 array가 정렬되어 있습니다. 배열을 그대로 두려던 코드였다면 원본이 바뀌는 버그가 됩니다. 반대로 List.of로 만든 목록은 내용을 바꾸는 것 자체가 막혀 있으므로, sort를 호출하는 즉시 UnsupportedOperationException이 납니다. 이미 정렬된 목록이나 빈 목록이어도 마찬가지입니다.

원본을 그대로 두고 정렬된 결과만 얻는 방법은 두 가지입니다. 스트림의 sorted()로 정렬된 새 목록을 만들거나, 가변 사본을 만든 뒤 그 사본을 정렬하는 것입니다. 다음 프로그램은 같은 원본에서 두 방법으로 조회 수 오름차순과 내림차순 결과를 만듭니다.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public final class SortingAndCopyContracts {
    public static void main(String[] args) {
        List<Entry> source =
                List.of(new Entry("thread", 60), new Entry("array", 40), new Entry("hash", 50));
        Comparator<Entry> byViewCount = Comparator.comparingInt(Entry::viewCount);
        List<Entry> immutableSorted = source.stream().sorted(byViewCount).toList();
        List<Entry> mutableSorted = new ArrayList<>(source);
        mutableSorted.sort(byViewCount.reversed());
        System.out.println("source=" + source);
        System.out.println("asc=" + immutableSorted);
        System.out.println("desc=" + mutableSorted);
        mutableSorted.add(new Entry("queue", 30));
        System.out.println("mutable-size=" + mutableSorted.size());
    }

    private record Entry(String title, int viewCount) {}
}

source=[Entry[title=thread, viewCount=60], Entry[title=array, viewCount=40], Entry[title=hash, viewCount=50]]
asc=[Entry[title=array, viewCount=40], Entry[title=hash, viewCount=50], Entry[title=thread, viewCount=60]]
desc=[Entry[title=thread, viewCount=60], Entry[title=hash, viewCount=50], Entry[title=array, viewCount=40]]
mutable-size=4

첫 줄의 source는 처음 넣은 순서 그대로입니다. source는 List.of로 만들어서 애초에 정렬할 수 없고, 두 정렬 모두 다른 목록을 대상으로 했기 때문입니다. 둘째 줄의 asc는 stream().sorted(byViewCount).toList()가 만든 새 목록으로, 조회 수 오름차순입니다. 셋째 줄의 desc는 new ArrayList<>(source)로 복사한 가변 목록을 byViewCount.reversed()로 제자리 정렬한 결과입니다.

마지막 줄은 가변 사본에만 queue를 추가해서 크기가 4가 된 것을 보여 줍니다. 추가한 뒤에 다시 정렬하지는 않았으므로, queue는 조회 수와 상관없이 목록 맨 뒤에 붙습니다. 정렬은 호출한 순간의 순서를 만들 뿐, 이후에 들어오는 원소의 자리까지 정해 주지는 않습니다.

두 방법은 결과를 고칠 수 있는지가 다릅니다. Stream.toList()가 돌려준 asc는 수정할 수 없는 목록이라 asc.add(...)를 호출하면 예외가 납니다. 정렬한 결과에 계속 원소를 추가해야 한다면 new ArrayList<>(source)로 복사해 정렬하거나, 스트림 끝에서 collect(Collectors.toCollection(ArrayList::new))로 ArrayList를 지정해 모읍니다. Collectors.toList()도 현재 구현에서는 ArrayList를 돌려주지만, Javadoc은 돌려주는 목록의 타입이나 수정 가능 여부를 약속하지 않습니다.

사본을 만들어도 원소 객체는 공유된다

new ArrayList<>(source)나 List.copyOf(source)가 복사하는 것은 원소를 가리키는 참조입니다. 원소 객체까지 새로 만들지는 않으므로 이런 복사를 얕은 복사(shallow copy)라고 부릅니다. 원소가 String이나 앞 예제의 Entry처럼 만든 뒤에는 바뀌지 않는 객체라면 참조를 공유해도 문제가 없습니다. 하지만 원소가 필드를 바꿀 수 있는 객체라면, 수정할 수 없는 목록 안에 들어 있어도 그 객체의 상태는 바뀔 수 있습니다.

다음 프로그램은 목록의 칸을 바꾸는 것과 원소 객체의 필드를 바꾸는 것을 나눠서 확인합니다. 예제에 쓴 List.getFirst()는 Java 21에 추가된 메서드로, 비어 있지 않은 목록에서는 get(0)과 같은 원소를 돌려주고 빈 목록에서는 NoSuchElementException을 던집니다.

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

public final class ShallowSnapshotBoundary {
    public static void main(String[] args) {
        Box first = new Box(40);
        List<Box> source = new ArrayList<>(List.of(first));
        List<Box> snapshot = List.copyOf(source);
        first.count = 55;
        source.set(0, new Box(70));
        System.out.println("source=" + source.getFirst().count);
        System.out.println("snapshot=" + snapshot.getFirst().count);
        System.out.println("shared-first=" + (snapshot.getFirst() == first));
    }

    private static final class Box {
        int count;
        Box(int count) { this.count = count; }
    }
}

source=70
snapshot=55
shared-first=true

문장이 하나씩 실행될 때마다 두 목록의 첫 칸이 무엇을 가리키는지 따라가 보겠습니다.

List.copyOf는 first를 가리키는 참조를 복사했으므로, 처음에는 두 목록의 첫 칸이 같은 Box를 가리킵니다. 그래서 first.count = 55는 두 목록 모두에서 보입니다. 반면 source.set(0, ...)은 source의 칸만 새 Box로 바꾸는 목록 변경이라 snapshot에는 반영되지 않습니다. 출력의 snapshot=55와 shared-first=true가 이 두 사실을 보여 줍니다.

앞의 정렬 예제에서 사본을 마음 놓고 만들 수 있었던 것은 Entry가 String과 int만 담은 record라서 만든 뒤에는 값이 바뀌지 않기 때문입니다. 원소가 바뀌지 않으면 목록을 몇 번 복사하든 원소를 공유해도 안전합니다. 이런 객체를 만드는 방법은 불변 객체와 안전한 공유에서 다뤘습니다.

동점 원소: List는 모두 남기고 TreeSet은 하나만 남긴다

앞 글에서 비교자가 0을 돌려주면 두 원소는 그 기준에서 동점이라고 했습니다. 동점을 어떻게 처리하는지는 자료구조마다 다릅니다. 다음 프로그램은 점수 내림차순 비교자 하나로 목록을 정렬하고, 같은 비교자를 쓰는 TreeSet에도 같은 원소를 넣어 봅니다. hash와 set은 점수가 90으로 같습니다.

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

public final class ListAndTreeSortingDifference {
    public static void main(String[] args) {
        Comparator<Entry> byScore = Comparator.comparingInt(Entry::score).reversed();
        List<Entry> list =
                new ArrayList<>(
                        List.of(
                                new Entry("hash", 90),
                                new Entry("set", 90),
                                new Entry("queue", 80)));
        list.sort(byScore);
        Set<Entry> tree = new TreeSet<>(byScore);
        tree.addAll(list);
        System.out.println("list-size=" + list.size() + " " + list);
        System.out.println("tree-size=" + tree.size() + " " + tree);
    }

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

list-size=3 [Entry[title=hash, score=90], Entry[title=set, score=90], Entry[title=queue, score=80]]
tree-size=2 [Entry[title=hash, score=90], Entry[title=queue, score=80]]

list.sort는 원소를 하나도 버리지 않고 순서만 바꾸므로 크기가 3 그대로입니다. 동점인 hash와 set 가운데 hash가 앞에 있는 것은 입력 순서가 그랬기 때문입니다. List.sort는 안정 정렬(stable sort)이어서 비교 결과가 0인 원소끼리는 원래 순서를 바꾸지 않습니다. 순서가 있는 스트림의 sorted()도 안정 정렬이지만, 순서가 없는 스트림에서는 동점끼리의 순서를 약속하지 않습니다.

TreeSet은 원소를 넣을 때 equals가 아니라 비교자로 이미 있는 원소인지 판단합니다. set을 넣을 때 비교자가 hash와 비교해 0을 돌려주므로, TreeSet은 같은 원소가 이미 있다고 보고 add에서 false를 돌려줍니다. 새 원소가 기존 원소를 대신하는 것도 아니어서 먼저 들어간 hash가 그대로 남고, 크기는 2가 됩니다.

TreeSet이 비교자로만 판단한다는 것은 검색에서도 드러납니다. 앞 프로그램의 main 끝에 다음 두 줄을 붙여 실행해 보세요.

        System.out.println("contains-set=" + tree.contains(new Entry("set", 90)));
        System.out.println("equals-check=" + new Entry("set", 90).equals(new Entry("hash", 90)));

contains-set=true
equals-check=false

set은 TreeSet에 들어간 적이 없는데도 contains가 true를 돌려줍니다. 비교자가 hash와 비교해 0을 돌려주기 때문입니다. 반면 record가 자동으로 만든 equals는 제목과 점수를 모두 비교하므로 두 Entry가 다르다고 답합니다. 이처럼 비교자가 0을 돌려주는 경우와 equals가 true인 경우가 일치하지 않으면, 그 순서를 'equals와 일관되지 않다(inconsistent with equals)'고 합니다. TreeSet의 Javadoc에 따르면 이런 비교자를 써도 TreeSet의 동작은 잘 정의되어 있지만, equals로 같음을 정하는 Set 인터페이스의 일반 규칙과는 어긋나게 됩니다.

해결 방법은 무엇을 원하는지에 따라 다릅니다. 같은 점수의 게시글을 모두 보관하는 정렬된 집합이 필요하면 Comparator.comparingInt(Entry::score).reversed().thenComparing(Entry::title)처럼 동점일 때 제목을 비교하는 기준을 덧붙입니다. 이렇게 바꾸면 TreeSet에 세 원소가 모두 남습니다. 제목과 점수가 모두 같은 원소까지 따로 보관해야 한다면 집합이 아니라 List를 정렬해서 써야 합니다. 반대로 점수마다 대표 하나만 남기는 것이 목적이라면 지금의 TreeSet이 맞습니다.

정렬된 목록에서 이진 탐색하기

목록에서 값을 찾는 방법 가운데 어떤 것은 정렬이 필요 없고, 어떤 것은 정렬이 반드시 필요합니다. Collections.min과 Collections.max는 원소를 처음부터 끝까지 한 번씩 훑어 가장 작은 값과 가장 큰 값을 찾으므로 정렬하지 않은 목록에도 쓸 수 있습니다. 반면 Collections.binarySearch는 가운데 원소와 비교해 찾을 범위를 절반씩 줄여 나가는 이진 탐색이라, 목록이 같은 기준으로 오름차순 정렬되어 있어야 합니다. 그 대신 원소가 n개일 때 비교를 약 log₂ n번만 하면 됩니다.

import java.util.Collections;
import java.util.List;

public final class BinarySearchResult {
    public static void main(String[] args) {
        List<Integer> scores = List.of(70, 80, 90);
        System.out.println("found=" + Collections.binarySearch(scores, 80));
        int missing = Collections.binarySearch(scores, 85);
        System.out.println("missing=" + missing + ", insert-at=" + (-missing - 1));
        System.out.println("too-big=" + Collections.binarySearch(scores, 100));
        List<Integer> unsorted = List.of(90, 70, 80);
        System.out.println("unsorted=" + Collections.binarySearch(unsorted, 90));
    }
}

found=1
missing=-3, insert-at=2
too-big=-4
unsorted=-4

값을 찾으면 그 인덱스를 돌려줍니다. 80은 인덱스 1에 있으므로 첫 줄은 1입니다. 찾지 못하면 '이 값을 넣는다면 들어갈 자리', 즉 삽입 위치(insertion point)를 써서 -(삽입 위치) - 1을 돌려줍니다. 85는 80과 90 사이인 인덱스 2에 들어가야 하므로 결과는 -3이고, 둘째 줄의 insert-at처럼 -missing - 1을 계산하면 삽입 위치 2를 되살릴 수 있습니다. 모든 원소보다 큰 100은 삽입 위치가 목록 크기인 3이라서 -4가 나옵니다.

그냥 -(삽입 위치)를 돌려주지 않고 1을 더 빼는 데는 이유가 있습니다. 모든 원소보다 작은 값의 삽입 위치는 0인데, 0에 마이너스를 붙여도 0이라서 '인덱스 0에서 찾았다'와 구별되지 않습니다. 1을 더 빼면 찾지 못한 경우는 언제나 음수가 되므로, 결과가 0 이상인지만 보고 찾았는지를 판단할 수 있습니다.

마지막 줄은 정렬하지 않은 목록 [90, 70, 80]에서 90을 찾은 결과입니다. 90은 분명히 인덱스 0에 있는데 '없다'는 뜻의 음수가 나왔습니다. 이진 탐색은 가운데 원소 70과 비교한 뒤 '90은 70보다 크니 오른쪽에 있을 것'이라고 판단해 왼쪽을 버리기 때문입니다. Javadoc은 정렬되지 않은 목록에서의 결과를 '정의되지 않음'이라고 적고 있으니, 이런 엉뚱한 값이 나와도 이상하지 않습니다.

규칙이 두 가지 더 있습니다. 첫째, 정렬할 때 쓴 순서와 검색할 때 쓰는 순서가 같아야 합니다. 비교자로 정렬한 목록이라면 Collections.binarySearch(list, key, comparator)에 같은 순서를 만드는 비교자를 넘겨야 하고, 그렇지 않으면 결과는 역시 정의되지 않습니다. 둘째, 같은 값이 여러 개 있으면 그 가운데 어느 인덱스를 돌려줄지 정해져 있지 않습니다. 그래서 점수만 비교하는 비교자로 검색에 성공했더라도, 원하는 제목의 게시글을 찾았다고 판단해서는 안 됩니다.

서비스는 내부 목록 대신 정렬된 사본을 돌려준다

지금까지 본 내용을 게시판 서비스에 적용해 보겠습니다. 서비스는 게시글을 내부 ArrayList에 쌓아 두고, 순위를 요청받으면 조회 수 내림차순으로 정렬한 목록을 돌려줍니다. 내부 목록을 정렬해서 그대로 돌려주면 호출자가 그 목록에 원소를 끼워 넣을 수 있고, 서비스가 나중에 추가한 게시글이 호출자가 들고 있던 목록에 섞여 들어갑니다. 그래서 ranking()은 요청받을 때마다 스트림으로 정렬된 새 목록을 만들어 돌려줍니다.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public final class BoardSnapshotService {
    public static void main(String[] args) {
        Service service = new Service();
        service.add("hash", 50);
        service.add("array", 40);
        List<Entry> first = service.ranking();
        service.add("thread", 60);
        System.out.println("first=" + first);
        System.out.println("current=" + service.ranking());
    }

    private static final class Service {
        private final List<Entry> entries = new ArrayList<>();

        void add(String title, int viewCount) {
            entries.add(new Entry(title, viewCount));
        }

        List<Entry> ranking() {
            return entries.stream()
                    .sorted(Comparator.comparingInt(Entry::viewCount).reversed())
                    .toList();
        }
    }

    private record Entry(String title, int viewCount) {}
}

first=[Entry[title=hash, viewCount=50], Entry[title=array, viewCount=40]]
current=[Entry[title=thread, viewCount=60], Entry[title=hash, viewCount=50], Entry[title=array, viewCount=40]]

first는 게시글이 두 개일 때 받은 순위입니다. 그 뒤에 thread를 추가했지만 first에는 여전히 두 개만 들어 있습니다. ranking()이 돌려준 목록은 그 순간의 내용을 정렬해 담은 별도의 목록이기 때문입니다. thread가 포함된 순위를 보려면 둘째 줄의 current처럼 ranking()을 다시 호출해야 합니다.

결과가 Stream.toList()로 만든 수정할 수 없는 목록이라, 호출자가 순위 목록에 원소를 끼워 넣을 수도 없습니다. 내부 ArrayList는 서비스 밖으로 한 번도 나가지 않으므로, 게시글을 추가하는 길은 add 메서드 하나뿐입니다. 저장은 가변 목록으로 하고, 바깥에 보여 줄 때는 그때그때 정렬한 사본을 만드는 구조입니다.

더 깊이: 여러 스레드가 같은 목록을 쓸 때

BoardSnapshotService는 스레드 하나에서만 쓰는 예제입니다. 여러 스레드가 동시에 add와 ranking()을 호출한다면 ranking()이 사본을 돌려준다는 사실만으로는 안전해지지 않습니다. 사본을 만들려고 내부 ArrayList를 순회하는 도중에 다른 스레드가 원소를 추가할 수 있기 때문입니다. 스레드는 다음 장부터 다루므로, 여기서는 표준 라이브러리의 동기화 래퍼가 무엇을 막아 주고 무엇을 막아 주지 못하는지만 짚어 둡니다.

Collections.synchronizedList(list)는 add, contains 같은 메서드 하나하나를 잠금으로 감싼 목록을 돌려줍니다. 한 번의 호출은 다른 스레드의 호출과 섞이지 않지만, 두 호출 사이에는 다른 스레드가 끼어들 수 있습니다. 예를 들어 '없으면 추가한다'는 if (!list.contains(x)) list.add(x);를 두 스레드가 동시에 실행하면 다음 순서가 가능합니다.

메서드마다 잠금이 걸려 있었는데도 x가 두 번 들어갔습니다. 이런 실행 순서는 드물게 나타나지만 실제로 일어납니다. 두 호출을 하나로 묶으려면 래퍼 객체를 잠그는 synchronized (list) 블록 안에서 contains와 add를 함께 실행해야 합니다. 래퍼의 메서드들이 바로 그 객체를 잠금으로 쓰기 때문입니다. 애초에 중복 없는 저장이 목적이라면 add 한 번으로 '없으면 추가'를 끝내는 동시성 Set을 쓰는 편이 낫습니다. 동기화 래퍼의 이런 틈은 ConcurrentHashMap과 동시성 컬렉션에서 실제로 재현해 봅니다.

순회도 마찬가지입니다. 래퍼의 iterator()는 감싼 목록의 반복자를 그대로 돌려줄 뿐 순회 전체를 잠그지 않으므로, Javadoc은 래퍼를 순회할 때 반드시 synchronized (list) 블록 안에서 하라고 요구합니다. 이를 지키지 않고 순회하는 도중에 다른 스레드가 목록을 바꾸면 결과를 예측할 수 없습니다. ConcurrentModificationException이 날 수도 있지만, 이 예외에 기대서는 안 됩니다. 순회 중에 목록을 바꾸면 이 예외가 나는 이유는 Iterable과 Iterator에서 다뤘습니다. 이런 즉시 실패(fail-fast) 검사를 두고 Javadoc은 '최선을 다하는 수준(best-effort)'일 뿐 보장되지 않는다고 적고 있습니다. 실제로 스레드가 하나뿐이어도 순회 중에 원소를 지우면 예외 없이 원소를 건너뛰고 끝나는 경우가 있으므로, 예외가 나지 않았다고 해서 순회가 올바르게 끝났다고 볼 수 없습니다.

정리

• Arrays.asList는 배열을 감싼 뷰입니다. set과 정렬은 배열에 그대로 반영되고, 크기를 바꾸는 add·remove는 UnsupportedOperationException을 던집니다.
• List.of와 List.copyOf는 수정할 수 없고 null을 거부합니다. Stream.toList()도 수정할 수 없지만 null은 담습니다. 수정 가능 여부와 null 허용 여부는 따로 확인합니다.
• 결과가 없으면 null 대신 List.of() 같은 빈 컬렉션을 돌려줍니다.
• list.sort는 목록을 제자리에서 정렬하고, stream().sorted().toList()는 원본을 두고 수정할 수 없는 새 목록을 만듭니다. 정렬한 뒤에도 고칠 목록이 필요하면 가변 사본을 정렬합니다.
• 컬렉션 복사는 원소 참조만 복사하는 얕은 복사입니다. 원소 객체의 필드를 바꾸면 사본에서도 보입니다.
• List.sort는 동점 원소를 모두 남기고 원래 순서를 지키는 안정 정렬입니다. TreeSet은 비교 결과가 0인 원소를 같은 원소로 보고 나중 것을 넣지 않습니다.
• Collections.binarySearch는 같은 순서로 정렬된 목록에서만 의미가 있고, 찾지 못하면 -(삽입 위치) - 1을 돌려줍니다.

연습 문제

1. 원본 String 배열 {"thread", "array"}로 목록을 만드세요. 이후 배열의 칸을 바꿔도 목록이 영향을 받지 않아야 하고, 목록에 원소를 추가하고 정렬해도 배열이 바뀌지 않아야 합니다.
2. 다음 프로그램을 실행하기 전에 출력을 예상해 보세요. 마지막 println이 실행되는지도 판단하세요.

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public final class ViewCopyQuiz {
    public static void main(String[] args) {
        String[] tags = {"set", "array", "map"};
        List<String> view = Arrays.asList(tags);
        Collections.sort(view);
        System.out.println(Arrays.toString(tags));
        List<String> copy = List.copyOf(view);
        tags[0] = "tree";
        System.out.println(view + " " + copy);
        copy.set(0, "hash");
        System.out.println("copy=" + copy);
    }
}

3. 제목이 서로 다른 Entry 세 개 hash=90, set=90, queue=80을 점수 오름차순으로 비교하고 동점이면 제목 오름차순으로 비교하는 TreeSet에 넣으면, 제목 순서와 크기는 어떻게 될까요? 또 정렬된 점수 목록 [80, 90, 90]에서 85를 검색하면 반환값과 삽입 위치는 무엇이고, 90을 검색한 결과를 특정 인덱스 하나로 단정해도 될까요?

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public final class IndependentMutableListSolution {
    public static void main(String[] args) {
        String[] source = {"thread", "array"};
        List<String> values = new ArrayList<>(Arrays.asList(source));
        source[0] = "changed";
        values.add("hash");
        values.sort(String::compareTo);
        System.out.println("source=" + Arrays.toString(source));
        System.out.println("values=" + values);
    }
}

source=[changed, array]
values=[array, hash, thread]

[array, map, set]
[tree, map, set] [array, map, set]
Exception in thread "main" java.lang.UnsupportedOperationException

import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.TreeSet;

public class SortTieAndSearchSolution {
    record Entry(String title, int score) {}

    public static void main(String[] args) {
        var order = Comparator.comparingInt(Entry::score)
                .thenComparing(Entry::title);
        var entries = new TreeSet<Entry>(order);
        entries.addAll(List.of(new Entry("hash", 90),
                new Entry("set", 90), new Entry("queue", 80)));
        System.out.println("titles=" + entries.stream().map(Entry::title).toList());
        System.out.println("size=" + entries.size());

        var scores = List.of(80, 90, 90);
        int missing = Collections.binarySearch(scores, 85);
        int found = Collections.binarySearch(scores, 90);
        System.out.println("missing=" + missing);
        System.out.println("insertion=" + (-missing - 1));
        System.out.println("duplicate-index-valid=" + (found == 1 || found == 2));
        System.out.println("duplicate-score=" + scores.get(found));
    }
}

titles=[queue, hash, set]
size=3
missing=-2
insertion=1
duplicate-index-valid=true
duplicate-score=90

다음 글

다음 글에서는 List, Set, Map, Deque 가운데 무엇을 쓸지 요구 사항에서 출발해 고르는 방법을 정리합니다. 내부에는 가변 컬렉션을 두고 밖으로는 수정할 수 없는 사본을 돌려주는 설계도 다시 다룹니다.