요구 사항에 맞는 컬렉션 고르기

게시판 하나에도 컬렉션이 할 일은 여러 가지입니다. 게시글을 등록한 순서대로 보여 줘야 하고, 같은 주소(slug)를 가진 게시글이 두 번 등록되지 않게 막아야 하며, slug로 게시글을 바로 찾아야 합니다. 처리할 작업은 들어온 순서대로 꺼내고, 최근 본 게시글은 새로 본 것을 맨 앞에 붙여야 합니다. 이때 클래스 이름부터 떠올리면 'ArrayList가 빠른가, LinkedList가 빠른가' 같은 질문에서 맴돌기 쉽습니다.

순서를 거꾸로 하면 선택이 쉬워집니다. 먼저 요구 사항이 무엇을 필요로 하는지 묻습니다. 원소에 순서가 있어야 하는지, 중복을 허용하는지, 키로 값을 찾는지, 양쪽 끝에서 넣고 빼는지에 따라 List, Set, Map, Deque 가운데 어떤 인터페이스를 쓸지가 정해집니다. 그다음 실제로 어떤 연산을 얼마나 자주 하는지를 보고 구현 클래스를 고릅니다. 이 글에서는 이 순서대로 컬렉션을 고르고, 마지막에 고른 컬렉션을 밖으로 돌려주는 방법까지 정리합니다.

모든 요구를 List로 처리하면 생기는 일

List 하나로도 거의 모든 일을 흉내 낼 수 있습니다. 중복을 막고 싶으면 추가하기 전에 같은 값이 있는지 처음부터 훑어보면 됩니다. 다음 프로그램은 서로 다른 slug 1,000개를 이런 식으로 ArrayList에 넣으면서, 같은 값이 있는지 확인하느라 equals를 몇 번 호출했는지 셉니다.

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

public final class ListForEveryRequirementBug {
    public static void main(String[] args) {
        List<String> unique = new ArrayList<>();
        int comparisons = 0;
        for (int value = 0; value < 1000; value++) {
            String slug = "post-" + value;
            boolean found = false;
            for (String existing : unique) {
                comparisons++;
                if (existing.equals(slug)) {
                    found = true;
                    break;
                }
            }
            if (!found) unique.add(slug);
        }
        System.out.println("size=" + unique.size() + ", comparisons=" + comparisons);
    }
}

size=1000, comparisons=499500

k번째 slug를 넣을 때(k는 0부터 셉니다) 목록에는 이미 k개가 들어 있고, 모두 다른 값이므로 k번을 다 비교하고 나서야 '없다'는 것을 압니다. 그래서 비교 횟수는 0 + 1 + … + 999 = 999 × 1000 / 2 = 499,500번입니다. unique.contains(slug)를 썼어도 같습니다. ArrayList의 contains도 내부에서 원소를 처음부터 하나씩 equals로 비교하기 때문입니다.

문제는 이 횟수가 데이터보다 훨씬 빨리 늘어난다는 것입니다. 반복 횟수를 10,000으로 바꿔 실행하면 다음과 같습니다.

데이터가 10배가 되자 비교 횟수는 약 100배가 되었습니다. 원소 n개를 넣는 데 n²에 비례하는 비교가 드는 것입니다. 요구 사항의 핵심은 '같은 값이 이미 있는가'인데, List는 이 질문에 빨리 답하는 구조가 아닙니다.

이 질문에 맞는 인터페이스는 Set입니다. Set.add는 같은 값이 이미 있으면 아무것도 넣지 않고 false를 돌려주므로, 중복 검사와 추가가 메서드 하나로 끝납니다.

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

public final class SetForUniqueSlugs {
    public static void main(String[] args) {
        Set<String> unique = new LinkedHashSet<>();
        int rejected = 0;
        for (int value = 0; value < 1000; value++) {
            if (!unique.add("post-" + value)) rejected++;
        }
        if (!unique.add("post-0")) rejected++;
        System.out.println("size=" + unique.size() + ", rejected=" + rejected);
    }
}

size=1000, rejected=1

마지막에 다시 넣은 post-0만 add가 false를 돌려주어 rejected가 1입니다. LinkedHashSet은 HashSet처럼 해시 코드로 원소가 들어 있을 버킷을 바로 찾으므로, 원소가 많아져도 add 한 번의 비용이 평균적으로 일정합니다. 그 원리는 해시 테이블의 동작 원리에서 다뤘습니다. 여기서 HashSet 대신 LinkedHashSet을 고른 것은 넣은 순서를 기억해 두려는 것입니다.

같은 일이 키와 값의 관계에서도 일어납니다. slug 목록과 게시글 목록을 따로 두고 indexOf로 찾은 위치에서 짝을 꺼내면, 찾을 때마다 처음부터 훑어야 합니다. 게다가 한쪽 목록만 정렬하거나 지우는 순간 짝이 어긋납니다. 이런 관계는 처음부터 Map으로 표현해야 한다는 것을 Map 인터페이스와 구현 클래스에서 보았습니다.

요구 사항으로 인터페이스 정하기

어떤 인터페이스를 쓸지는 요구 사항에 다음 질문을 던져 보면 정해집니다. 앞의 네 줄이 기본 질문이고, 마지막 줄은 큐 가운데 꺼내는 규칙이 다른 경우입니다.

마지막 줄의 PriorityQueue는 Queue 인터페이스를 구현하지만 꺼내는 규칙이 다릅니다. poll을 호출하면 들어온 순서와 상관없이 가장 작은 값(비교자를 주면 비교자 기준으로 가장 앞서는 값)을 꺼냅니다. 그런데 이 큐를 출력하거나 향상된 for문으로 훑으면 우선순위 순서가 나오지 않습니다. 다음 프로그램에서 확인해 보세요.

import java.util.PriorityQueue;
import java.util.Queue;

public final class PriorityOrder {
    public static void main(String[] args) {
        Queue<Integer> deadlines = new PriorityQueue<>();
        deadlines.offer(30);
        deadlines.offer(10);
        deadlines.offer(20);
        System.out.println("print=" + deadlines);
        StringBuilder polled = new StringBuilder();
        while (!deadlines.isEmpty()) {
            polled.append(deadlines.poll()).append(' ');
        }
        System.out.println("poll=" + polled.toString().trim());
    }
}

print=[10, 30, 20]
poll=10 20 30

출력한 순서는 [10, 30, 20]인데, poll로 하나씩 꺼내면 10, 20, 30 순서입니다. PriorityQueue는 내부 배열에 원소를 힙(heap)이라는 구조로 담아 둡니다. 힙은 부모 칸의 원소가 자식 칸의 원소보다 크지 않다는 규칙만 지키므로, 맨 앞 원소가 가장 작다는 것은 확실하지만 나머지 원소는 우선순위 순서로 늘어서 있지 않습니다. 출력과 반복자는 이 배열을 앞에서부터 읽을 뿐입니다. Javadoc도 반복자가 특정 순서로 원소를 돌려준다고 보장하지 않는다고 적고 있습니다. 그러니 우선순위 순서는 poll을 반복해서 꺼내는 순서로만 판단해야 합니다. 배열의 칸을 부모와 자식으로 짝짓는 방법과 원소를 넣고 꺼낼 때 이 규칙을 되살리는 과정은 완전 이진 트리·힙·우선순위 큐에서 다룹니다. 그 글은 주로 큰 값을 먼저 꺼내는 최대 힙으로 설명하는데, PriorityQueue는 같은 글에 나오는 최소 힙처럼 가장 작은 값을 맨 앞에 둡니다.

같은 이유로 Queue라는 이름만 보고 구현을 바꿔 끼우면 안 됩니다. '들어온 명령을 차례대로 처리한다'와 '기한이 가장 빠른 작업부터 처리한다'는 둘 다 Queue로 표현할 수 있지만 꺼내는 규칙이 다릅니다. ArrayDeque를 PriorityQueue로 바꾸면 컴파일은 되어도 처리 순서가 달라집니다. 스택과 큐를 다루는 메서드는 ArrayDeque로 스택과 큐 다루기에서 정리했습니다.

인터페이스는 할 수 있는 연산을 정해 주는 동시에, 하지 말아야 할 연산을 막아 줍니다. 메서드가 매개변수를 Queue<String>으로 받으면 그 메서드는 offer, poll, peek 같은 큐 연산과 size, contains처럼 Collection에서 물려받은 메서드는 쓸 수 있지만, get(3)처럼 위치에 기대는 코드는 쓸 수 없습니다. Set의 add가 돌려주는 boolean은 '이미 있었다'는 사실을 호출자에게 알려 줍니다. 반대로 모든 변수를 가장 넓은 Collection으로 선언하면 위치로 꺼내기(get(i))나 양쪽 끝에서 꺼내기(pollLast()) 같은 연산이 사라지고, 그 컬렉션이 무엇을 하려는 것인지도 코드에서 읽을 수 없게 됩니다. 참고로 Map은 Collection을 상속하지 않는 별도의 인터페이스라서 애초에 Collection 변수에 담을 수 없습니다.

List·Set·Map·Queue가 남기는 것 비교하기

다음 프로그램은 같은 제목 array를 두 번 넣으면서 List, Set, Map이 각각 무엇을 남기는지 보여 줍니다. Queue에는 제목이 아니라 처리할 명령 print를 넣습니다. 변수는 인터페이스 타입으로 선언하고, 구현 클래스는 new 뒤에서만 고른다는 점도 눈여겨보세요.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public final class CollectionChoiceScenarios {
    public static void main(String[] args) {
        List<String> orderedTitles = new ArrayList<>();
        orderedTitles.add("array");
        orderedTitles.add("array");
        Set<String> firstTags = new LinkedHashSet<>();
        firstTags.addAll(orderedTitles);
        Map<String, Integer> totals = new HashMap<>();
        for (String title : orderedTitles) {
            totals.merge(title, 1, Integer::sum);
        }
        Queue<String> pending = new ArrayDeque<>();
        pending.offer("print");
        System.out.println(orderedTitles);
        System.out.println(firstTags);
        System.out.println(totals);
        System.out.println(pending.poll());
    }
}

[array, array]
[array]
{array=2}
print

첫 줄에서 List는 두 번 넣은 array를 모두 순서대로 보관합니다. 둘째 줄의 Set은 같은 목록을 addAll로 받았지만 두 번째 array는 이미 있으므로 하나만 남깁니다. 셋째 줄의 Map은 merge(title, 1, Integer::sum)으로 제목별 횟수를 셉니다. 처음 보는 키에는 1을 넣고, 이미 있는 키에는 기존 값과 1을 더한 값을 넣으므로 array의 값이 2가 됩니다. merge는 Map 활용: 중복 키 처리와 merge·compute에서 자세히 다뤘습니다. 마지막 줄은 큐에서 poll로 꺼낸 print이고, 이제 큐는 비어 있습니다.

구현 클래스는 자주 하는 연산으로 고른다

인터페이스를 정했으면 실제로 어떤 연산을 얼마나 자주 하는지 보고 구현을 고릅니다. List라면 대부분 ArrayList가 맞습니다. 원소 참조를 배열 하나에 이어서 담아 두므로 get(i)가 바로 그 칸을 읽고, 전체를 훑는 것도 빠르며, 원소마다 노드 객체를 따로 만드는 LinkedList보다 메모리도 적게 씁니다. 두 구현의 비용을 연산별로 비교하면 다음과 같습니다.

LinkedList가 유리한 것은 맨 앞에 추가하는 경우와 마지막 줄입니다. 그런데 맨 앞에서 넣고 빼는 일은 ArrayDeque도 분할 상환 O(1)에 해내므로, LinkedList만의 장점은 사실상 마지막 줄 하나입니다. ListIterator는 목록을 앞뒤로 오가면서 지금 가리키는 위치에 원소를 넣거나 지울 수 있는 반복자인데, LinkedList에서는 이미 그 위치에 와 있다면 노드 연결만 바꾸면 되기 때문입니다. 그 위치까지 이동하는 비용은 따로 듭니다. 흔히 'LinkedList는 중간 삽입이 O(1)'이라고 말하지만, add(i, x)처럼 인덱스로 위치를 찾아가야 하면 O(n)입니다. 표의 '분할 상환 O(1)'은 대부분의 추가는 O(1)이지만 배열이 꽉 차면 더 큰 배열로 모두 옮기는 일이 가끔 생겨서, 여러 번의 비용을 평균 내면 O(1)이 된다는 뜻입니다. 자세한 비교는 ArrayList와 LinkedList의 연산 비용과 용량이 늘어나는 동적 배열 만들기에서 다뤘습니다.

큐나 스택이 필요하면 ArrayDeque가 기본입니다. Set과 Map은 순회할 때 어떤 순서가 필요한지로 고릅니다.

해시 계열의 '평균 O(1)'에는 hashCode가 원소를 버킷에 고르게 흩어 놓고, 원소가 늘면 적재 계수(load factor)에 맞춰 버킷 배열을 키운다는 전제가 붙습니다. 많은 원소가 한 버킷에 몰리면 그만큼 느려집니다. 트리 계열의 O(log n)은 비교 횟수를 말하므로, 긴 문자열처럼 비교 한 번이 비싼 키라면 그 비용이 곱해집니다. 트리 계열은 앞 글에서 본 것처럼 비교자가 0을 돌려주는 원소를 같은 원소로 다룬다는 점도 함께 기억해야 합니다. 세 가지 Set 구현은 HashSet·LinkedHashSet·TreeSet 비교와 선택에서 직접 비교해 보았습니다.

더 깊이: 복잡도 표가 알려 주지 않는 것

복잡도 표의 한 칸에는 많은 조건이 생략되어 있습니다. 위치를 찾는 비용이 포함됐는지, 평균인지 최악인지, 배열을 늘리는 비용을 나눠 계산했는지, 해시나 비교 한 번에 얼마가 드는지가 모두 칸 밖에 있습니다. 그래서 같은 O(n)이라도 실제 시간은 크게 다를 수 있습니다. 예를 들어 ArrayList의 중간 삽입은 O(n)이지만 연속된 메모리를 한 번에 옮기는 작업이라 빠르고, LinkedList의 순회는 메모리 여기저기에 흩어진 노드를 하나씩 찾아가야 해서 CPU 캐시를 잘 쓰지 못합니다.

원소가 수십 개 정도라면 복잡도 차이보다 코드가 단순한지, 객체를 몇 개 만드는지가 더 중요할 때가 많습니다. 성능 때문에 구현을 바꾸려면 먼저 두 구현이 같은 결과를 내는지 확인하고, JMH(Java Microbenchmark Harness) 같은 도구로 실제와 비슷한 데이터와 연산 비율을 써서 측정해야 합니다. 짧은 반복문을 System.nanoTime()으로 한 번 재는 정도로는 JIT 컴파일러의 최적화나 워밍업 때문에 엉뚱한 결론이 나오기 쉽습니다.

내부에는 가변 컬렉션, 밖으로는 수정할 수 없는 사본

컬렉션을 고르는 일은 클래스 안에서 끝나지 않습니다. 그 컬렉션을 메서드로 돌려줄 때 무엇을 돌려줄지도 정해야 합니다. 내부에서 ArrayList에 원소를 쌓는다고 해서 반환값까지 가변 목록일 필요는 없습니다. 내부 목록을 그대로 돌려주면 호출자가 클래스 몰래 원소를 넣거나 지울 수 있기 때문입니다. List.copyOf, Set.copyOf, Map.copyOf는 원본의 현재 내용을 담은 수정할 수 없는 사본을 만들어 줍니다. 원본이 나중에 바뀌어도 사본은 그대로입니다. 다만 앞 글에서 본 것처럼 null이 들어 있으면 예외를 던지고, 원소 객체까지 복사하지는 않습니다.

여기서 하나 조심할 것이 있습니다. Set.copyOf와 Map.copyOf는 순회 순서를 약속하지 않습니다. 넣은 순서를 기억하는 LinkedHashMap을 넘겨도 그 순서가 사본에 남는다는 보장이 없습니다. 다음 프로그램으로 확인해 보세요.

import java.util.LinkedHashMap;
import java.util.Map;

public final class CopyOfOrder {
    public static void main(String[] args) {
        Map<String, Integer> totals = new LinkedHashMap<>();
        totals.put("hash", 50);
        totals.put("queue", 40);
        totals.put("set", 30);
        totals.put("array", 20);
        System.out.println("original=" + totals);
        System.out.println("copy=" + Map.copyOf(totals));
    }
}

original={hash=50, queue=40, set=30, array=20}
copy={queue=40, set=30, array=20, hash=50}

첫 줄은 넣은 순서 그대로입니다. 둘째 줄의 순서는 실행할 때마다 달라질 수 있습니다. OpenJDK 21에서 같은 프로그램을 여러 번 실행하니 copy={array=20, set=30, queue=40, hash=50}처럼 다른 순서도 나왔습니다. OpenJDK 구현이 JVM을 시작할 때마다 바뀌는 값으로 순회 순서를 섞기 때문입니다. Javadoc도 이 순서를 '정해져 있지 않고 바뀔 수 있다'고 적고 있으니, 순서가 반환값의 일부라면 Map.copyOf는 맞지 않습니다.

순서를 지키면서 수정을 막으려면 복사와 수정 금지를 따로 처리합니다. new LinkedHashMap<>(totals)로 순서를 지킨 사본을 만들고, 그 사본을 Collections.unmodifiableMap으로 감싸 변경 메서드를 막는 것입니다. Collections.unmodifiableMap(totals)처럼 원본을 바로 감싸면 수정은 막히지만, 원본을 들여다보는 뷰라서 원본의 이후 변경이 그대로 보입니다. 네 가지 반환 방법을 비교하면 다음과 같습니다.

공식 문서도 수정할 수 없는 Map을 만드는 팩터리와 원본을 감싸는 unmodifiableMap 뷰를 따로 설명합니다. 뷰는 이 밖에도 흔합니다. Map.keySet()이 돌려주는 집합도 원본 맵의 뷰라서, 맵에 키를 추가하면 이미 받아 둔 keySet()의 크기도 함께 늘어납니다. 그러니 컬렉션을 돌려주는 메서드는 그것이 원본을 들여다보는 뷰인지, 호출한 시점의 사본인지를 문서에 밝혀야 합니다.

반대 방향도 있습니다. 수정할 수 없는 목록을 받아서 내부에서 원소를 추가해야 한다면, 받은 목록을 그대로 쓰지 말고 new ArrayList<>(source)로 내가 소유할 사본을 만듭니다. 받은 목록이 List.of로 만든 것이라면 추가할 때 예외가 나고, 가변 목록이라도 호출자가 나중에 바꾸면 내 상태가 함께 바뀌기 때문입니다.

여러 스레드가 같은 컬렉션을 쓰는지도 따로 따져야 할 질문입니다. 흔히 '스레드에 안전한 컬렉션'이라고 한데 묶지만, 방법마다 약속하는 것이 다릅니다. Collections.synchronizedList 같은 동기화 래퍼는 메서드 호출 하나하나만 잠그므로, 앞 글에서 본 것처럼 '없으면 추가' 같은 복합 연산과 순회는 직접 잠가야 합니다. ConcurrentHashMap 같은 동시성 컬렉션은 merge처럼 복합 연산을 한 번에 처리하는 메서드를 제공하고, 순회 중에 다른 스레드가 내용을 바꿔도 예외를 던지지 않습니다. 수정할 수 없는 사본은 아무도 바꿀 수 없으니 여러 스레드가 함께 읽어도 내용이 변하지 않지만, 만든 뒤의 변경은 담지 않습니다. 이 차이는 ConcurrentHashMap과 동시성 컬렉션에서 실제로 확인합니다.

게시판 저장소에 네 컬렉션 배치하기

지금까지의 기준으로 게시판 저장소를 설계해 보겠습니다. 저장소는 등록 요청을 대기열에 받아 두었다가 한꺼번에 처리하고, 처리한 게시글을 등록 순서대로 보관합니다. 동시에 지금까지 나온 태그를 처음 나온 순서대로 모으고, 제목별 조회 수 합계도 냅니다. 요구가 네 가지이므로 컬렉션도 네 개를 씁니다.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public final class BoardCollectionDesign {
    public static void main(String[] args) {
        Repository repository = new Repository();
        repository.enqueue(new Entry("hash", 50, List.of("java", "set")));
        repository.enqueue(new Entry("queue", 40, List.of("java", "deque")));
        repository.processAll();
        System.out.println(repository.entries());
        System.out.println(repository.tags());
        System.out.println(repository.totals());
    }

    private static final class Repository {
        private final Queue<Entry> pending = new ArrayDeque<>();
        private final List<Entry> entries = new ArrayList<>();
        private final Set<String> tags = new LinkedHashSet<>();
        private final Map<String, Integer> totals = new LinkedHashMap<>();

        void enqueue(Entry e) {
            pending.offer(e);
        }

        void processAll() {
            for (Entry e; (e = pending.poll()) != null; ) {
                entries.add(e);
                tags.addAll(e.tags());
                totals.merge(e.title(), e.viewCount(), Integer::sum);
            }
        }

        List<Entry> entries() {
            return List.copyOf(entries);
        }

        List<String> tags() {
            return List.copyOf(tags);
        }

        Map<String, Integer> totals() {
            return Collections.unmodifiableMap(new LinkedHashMap<>(totals));
        }
    }

    private record Entry(String title, int viewCount, List<String> tags) {
        Entry {
            if (title == null || title.isBlank() || viewCount < 0) {
                throw new IllegalArgumentException("invalid entry");
            }
            tags = List.copyOf(tags);
        }
    }
}

[Entry[title=hash, viewCount=50, tags=[java, set]], Entry[title=queue, viewCount=40, tags=[java, deque]]]
[java, set, deque]
{hash=50, queue=40}

네 필드는 각자 하나의 요구를 맡습니다. pending은 등록 요청을 들어온 순서대로 꺼내는 큐라서 ArrayDeque입니다. entries는 게시글을 등록 순서대로 두고 같은 내용도 허용하는 목록이라 ArrayList이고, tags는 같은 태그를 한 번만 두되 처음 나온 순서를 지키는 LinkedHashSet입니다. totals는 제목으로 조회 수 합계를 찾는 맵이고, 넣은 순서대로 보여 주려고 LinkedHashMap을 골랐습니다.

processAll()은 hash와 queue를 차례로 꺼내 세 필드에 반영합니다. 두 번째 게시글의 태그 java는 이미 있으므로 tags에는 deque만 늘어나고, 둘째 출력 줄이 [java, set, deque]가 됩니다. 반복문 조건 (e = pending.poll()) != null은 큐가 비면 poll()이 null을 돌려준다는 점을 이용합니다. ArrayDeque는 null 원소를 아예 받지 않으므로, 여기서 null은 '큐가 비었다'는 뜻으로만 읽힙니다.

조회 메서드 세 개는 모두 수정할 수 없는 사본을 돌려주지만 방법이 조금씩 다릅니다. tags()가 Set.copyOf가 아니라 List.copyOf를 쓰는 것은 순서 때문입니다. Set.copyOf는 앞에서 본 Map.copyOf처럼 순서를 약속하지 않지만, List.copyOf는 넘겨받은 컬렉션의 순회 순서대로 원소를 담습니다. 같은 이유로 totals()는 Map.copyOf 대신 LinkedHashMap으로 복사한 뒤 감쌌습니다. 조회 결과에서도 처음 나온 순서가 유지되어야 하기 때문입니다.

Entry의 컴팩트 생성자(compact constructor)에 있는 tags = List.copyOf(tags)도 같은 생각에서 나왔습니다. record의 필드는 다른 값으로 다시 대입할 수 없지만, 필드가 가리키는 목록까지 수정할 수 없게 되는 것은 아닙니다. 호출자가 넘긴 가변 목록을 그대로 저장하면, 호출자가 나중에 그 목록에 태그를 추가할 때 Entry의 태그도 함께 바뀝니다. 생성자에서 사본을 만들어 두면 호출자는 자기 목록을 마음대로 바꿀 수 있고, Entry가 보관한 태그는 그대로입니다. 원소가 바뀌지 않는 String이므로 이 정도면 충분합니다. 또한 tags가 null이거나 null 원소를 담고 있으면 이 줄에서 NullPointerException이 나서, 잘못된 입력이 객체 안으로 들어오지 못합니다.

이 저장소는 스레드 하나에서만 쓰는 예제입니다. processAll()이 하는 poll, 목록 추가, 집합 추가, 합계 갱신은 하나로 묶인 연산이 아니므로, 여러 스레드가 동시에 호출하면 앞에서 말한 동시성 문제를 따로 해결해야 합니다.

정리

• 컬렉션은 클래스 이름이 아니라 요구 사항에서 고릅니다. 순서와 위치로 다루면 List, 같은 값을 하나만 두면 Set, 키로 찾으면 Map, 양쪽 끝에서 넣고 빼면 Deque입니다.
• List로 중복을 검사하면 원소 n개를 넣는 데 n²에 비례하는 비교가 듭니다. 중복 검사가 핵심이면 Set.add의 반환값을 씁니다.
• PriorityQueue는 poll로 꺼내는 순서만 우선순위를 따릅니다. 출력이나 반복자의 순서는 우선순위 순서가 아닙니다.
• 구현은 자주 하는 연산으로 고릅니다. List는 ArrayList, 큐와 스택은 ArrayDeque가 기본이고, Set·Map은 필요한 순회 순서에 따라 해시, 연결 해시, 트리 계열 가운데 고릅니다.
• 내부 컬렉션은 그대로 내보내지 말고 수정할 수 없는 사본을 돌려줍니다. 순서가 중요하면 Set.copyOf·Map.copyOf 대신 List.copyOf나 LinkedHashMap 사본을 씁니다.
• 반환값이 원본을 들여다보는 뷰인지 호출한 시점의 사본인지, 여러 스레드가 함께 쓰는지는 따로 따져야 할 질문입니다.

연습 문제

1. 최근 본 게시글을 최대 10개까지, 같은 게시글은 한 번만, 가장 최근에 본 것부터 보여 주세요. 또 slug로 게시글 상세를 바로 찾을 수 있어야 합니다. 순서를 기억하는 구조와 키로 찾는 구조를 컬렉션 하나에 억지로 몰아넣지 마세요.
2. 1번 해설의 RecentPostIndexSolution에서 main이 끝난 뒤 이어서 thread(제목 Thread)를 방문하고, 그다음 hash를 제목 Hash updated로 다시 방문한다고 합시다. 두 방문 직후 각각 recent, find("hash")의 결과, bySlug의 크기를 예상하세요.
3. LinkedHashMap<String, Integer>에 hash=50을 넣은 뒤, 이 원본을 그대로 감싼 수정 불가 뷰 live와 LinkedHashMap으로 복사한 뒤 감싼 수정 불가 사본 snapshot을 만드세요. 그다음 원본에서 hash를 60으로 바꾸고 queue=40을 추가합니다. 두 결과의 키 순서와 hash 값을 예상하고, live.put("set", 30)이 허용되는지 설명하세요.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public final class RecentPostIndexSolution {
    public static void main(String[] args) {
        Index index = new Index(3);
        index.visit(new Post("array", "Array"));
        index.visit(new Post("hash", "Hash"));
        index.visit(new Post("array", "Array"));
        index.visit(new Post("queue", "Queue"));
        System.out.println(index.recent);
        System.out.println(index.find("hash"));
    }

    private static final class Index {
        final int limit;
        final Deque<String> recent = new ArrayDeque<>();
        final Map<String, Post> bySlug = new HashMap<>();

        Index(int limit) {
            this.limit = limit;
        }

        void visit(Post post) {
            bySlug.put(post.slug(), post);
            recent.remove(post.slug());
            recent.addFirst(post.slug());
            if (recent.size() > limit) recent.removeLast();
        }

        Post find(String slug) {
            return bySlug.get(slug);
        }
    }

    private record Post(String slug, String title) {}
}

[queue, array, hash]
Post[slug=hash, title=Hash]

        final SequencedSet<String> recent = new LinkedHashSet<>();

        void visit(Post post) {
            bySlug.put(post.slug(), post);
            recent.addFirst(post.slug());
            if (recent.size() > limit) recent.removeLast();
        }

recent = [thread, queue, array]
find("hash") = Post[slug=hash, title=Hash]
bySlug 크기 = 4

recent = [hash, thread, queue]
find("hash") = Post[slug=hash, title=Hash updated]
bySlug 크기 = 4

import java.util.Collections;
import java.util.LinkedHashMap;

public class OrderedMapSnapshotSolution {
    public static void main(String[] args) {
        var source = new LinkedHashMap<String, Integer>();
        source.put("hash", 50);
        var live = Collections.unmodifiableMap(source);
        var snapshot = Collections.unmodifiableMap(new LinkedHashMap<>(source));

        source.put("hash", 60);
        source.put("queue", 40);
        System.out.println("live-keys=" + live.keySet());
        System.out.println("live-hash=" + live.get("hash"));
        System.out.println("snapshot-keys=" + snapshot.keySet());
        System.out.println("snapshot-hash=" + snapshot.get("hash"));
        try {
            live.put("set", 30);
        } catch (UnsupportedOperationException expected) {
            System.out.println("view-rejects-put");
        }
    }
}

live-keys=[hash, queue]
live-hash=60
snapshot-keys=[hash]
snapshot-hash=50
view-rejects-put

다음 장

여기까지 컬렉션을 순회하고 정렬하고 고르는 방법을 정리했습니다. 다음 장부터는 여러 작업을 동시에 실행하는 스레드를 다룹니다. 이 장에서 여러 번 '스레드 하나에서만 쓰는 예제'라고 단서를 단 이유가 거기서 드러납니다.