컬렉션 구현 선택 기준

컬렉션 선택을 클래스 이름 암기로 시작하면 ArrayList와 LinkedList 비교에서 멈춥니다.

먼저 결과가 순서를 갖는지, 중복을 허용하는지, 키로 값을 찾는지, 양끝 제거가 필요한지 결정합니다.

인터페이스가 정해진 뒤 조회·삽입·범위 질의의 실제 비율로 구현을 고릅니다.

단일 List 검색의 비용

게시글 slug를 ArrayList에 저장하고 매번 포함 여부로 중복을 검사하면 n개 추가의 누적 검색이 커집니다.

키-값 관계까지 indexOf와 병렬 List로 표현하면 관계 불일치 위험도 생깁니다.

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;
            for (String existing : unique) {
                comparisons++;
                if (existing.equals(slug)) break;
            }
            if (!unique.contains(slug)) unique.add(slug);
        }
        System.out.println("size=" + unique.size() + ", manual-comparisons=" + comparisons);
    }
}

manual-comparisons=499500은 수동 for 루프의 comparisons++만 센 값입니다. 서로 다른 1,000개 slug에서 0 + ... + 999를 합한 결과이며, 바로 뒤 contains의 내부 비교는 포함하지 않습니다.

중복 없는 존재 검사가 본질이면 Set이 요구를 직접 표현합니다.

499,500은 1,000×999/2입니다. 원 코드는 같은 입력마다 뒤의 contains도 다시 검색하므로 이 숫자를 전체 문자열 비교 횟수나 시간으로 부르면 안 됩니다. 또한 이미 있던 slug를 넣는 별도 입력에서는 찾은 위치에서 비교가 멈춰 이 합과 달라집니다. 원 예제는 모두 다른 slug를 넣은 조건에서 누적 선형 탐색을 보여 줍니다.

순서가 필요하면 LinkedHashSet으로 세부 구현을 선택합니다.

인터페이스 선택 질문 네 개

원소를 index·순서로 다루고 중복을 허용하면 List입니다.

값 존재와 집합 연산이 중심이면 Set입니다.

키와 값 관계를 저장하면 Map입니다.

최근/가장 오래된 원소를 양끝에서 처리하면 Deque입니다.

PriorityQueue는 입력 순서가 아니라 우선순위 제거가 필요할 때 별도 후보입니다.

우선순위 큐는 향상된 for문으로 읽은 순서까지 우선순위 정렬을 보장하는 구조가 아닙니다. 우선순위대로 처리하는 요구는 poll을 반복해 꺼내는 순서로 판단해야 합니다. “FIFO 대기 명령”과 “기한이 가장 빠른 작업부터 꺼내기”는 서로 다른 제거 규칙이므로 같은 Queue라는 이름만 보고 바꾸지 않습니다.

인터페이스는 불필요한 연산도 제한합니다.

Queue 매개변수는 소비자가 index get에 의존하지 않게 하고, Set은 중복 add의 의미를 boolean으로 보여 줍니다.

변수 타입을 가장 넓은 Collection로 무조건 올리면 키 조회나 양끝 의미가 사라져 오히려 규칙이 약해질 수 있습니다.

구현 선택 기준: 연산 분포·규모

List의 일반 기본값은 ArrayList입니다.

임의 조회와 전체 순회가 빠르고 메모리 효율이 좋습니다.

이미 원하는 위치로 이동한 ListIterator에서 중간 추가·삭제를 반복하는 등 구체 요구가 있을 때 LinkedList를 검토합니다. 위치까지 이동하는 비용은 별도입니다.

Queue·Stack에는 ArrayDeque가 기본입니다.

Set과 Map은 순서가 없으면 Hash 계열, 최초 삽입 순서면 LinkedHash 계열, 정렬·범위면 Tree 계열을 고려합니다.

평균 O(1)은 좋은 hashCode와 적절한 적재 계수가 전제이고 Tree의 O(log n)은 비교자 규칙이 전제입니다.

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를 다루고, 큐에는 print 명령을 넣습니다.

이 예제에서 List는 제목 중복을 보존하고, Set은 고유 값을 모으며, Map은 제목별 횟수를 세고, Queue는 처리할 명령을 보관합니다.

불변 반환·가변 내부 저장 결정

내부 구현이 ArrayList라고 반환값도 가변일 필요는 없습니다.

List.copyOf, Set.copyOf, Map.copyOf로 원본의 이후 구조 변경을 반영하지 않는 수정 불가 스냅샷을 만들 수 있습니다. 원소를 깊게 복사하는 것은 아닙니다.

순서까지 반환 계약인 경우: Map.copyOf는 매핑의 순회 순서를 보장하지 않습니다. 아래 저장소가 Collections.unmodifiableMap(new LinkedHashMap<>(totals))를 사용하는 이유는 복사본에서 첫 삽입 순서를 보존하고, 호출자가 그 복사본을 수정하지 못하게 하기 위해서입니다. Collections.unmodifiableMap(totals)만 반환하면 수정 불가인 것은 같지만 원본의 이후 변경을 그대로 보는 뷰가 됩니다. 복사와 수정 방지는 각각 확인해야 합니다. Map의 수정 불가 팩터리 계약과 unmodifiableMap의 뷰 계약은 이 둘을 구분합니다.

반대로 불변 List를 받아 내부에서 추가해야 한다면 new ArrayList<>(source)로 내부에서 소유할 복사본을 만듭니다.

뷰와 스냅샷 차이도 확인합니다.

Map.keySet은 원본 Map의 실시간 뷰여서 Map 변경이 반영됩니다.

List.copyOf는 이후 원본 구조 변경을 반영하지 않습니다.

API 사용자는 어느 시점의 결과인지 알아야 합니다.

동기화 요구는 자료 구조 선택의 별도 축입니다.

synchronized 래퍼, 동시성 컬렉션, 불변 스냅샷은 서로 다른 의미입니다.

단순히 “스레드 안전”이라는 한 단어로 복합 연산 원자성과 반복자 일관성을 가정하지 않습니다.

컬렉션 성능 표를 읽는 법

Big-O 한 칸은 위치 탐색 포함 여부, 평균·최악, 확장 비용, 비교 함수 비용을 생략할 수 있습니다.

LinkedList의 중간 삽입 O(1)은 ListIterator가 삽입 위치에 이미 도달했을 때의 연결 변경 비용입니다. index로 위치를 찾는 탐색은 별도이고, ArrayList 끝 add O(1)은 상환 비용입니다.

HashMap get 평균 O(1)은 해시 분산이 전제입니다.

작은 데이터에서는 코드 단순성·캐시 지역성·할당 수가 복잡도 차이보다 중요할 수 있습니다.

벽시계 측정은 JMH와 실제 작업 부하로 확인하고, 기능 결과가 같은지 먼저 확인합니다.

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

한 애플리케이션에서 자료 구조 하나만 고집하지 않습니다.

대기 작업은 FIFO, 게시글은 중복 허용·등록 순서, tags는 고유·첫 등장 순서, totals는 제목별 조회수 합계를 각각 맡습니다.

record와 원소 소유권: Entry의 record 필드는 다른 값으로 다시 대입할 수 없지만, record라는 이유만으로 필드가 가리키는 목록까지 수정 불가가 되지는 않습니다. 생성자의 tags = List.copyOf(tags)는 호출자가 전달한 원본 목록의 이후 추가·삭제가 이 Entry에 반영되지 않게 하여 태그 구성을 고정합니다. 호출자는 자기 원본 목록을 여전히 바꿀 수 있고, Entry가 보관한 목록만 수정 불가입니다. 여기서는 원소가 수정 불가인 String이어서 충분합니다. 가변 객체를 원소로 담는다면 그 객체의 변경은 별도로 다뤄야 합니다. 이 Repository도 단일 스레드 예제입니다. processAll()의 poll()·목록 추가·집합 추가·누적 갱신은 하나의 원자적 연산으로 묶인 것이 아닙니다. ArrayDeque가 null 원소를 받지 않으므로 이 예제에서 poll()의 null은 빈 큐를 뜻합니다.

연습 문제

“최근 본 게시글 10개를 중복 없이 최신순으로 보이고, slug로 게시글 상세를 즉시 찾는다”를 구현하세요.

순서 구조와 키 조회 구조를 하나로 억지로 합치지 않습니다.

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 i = new Index(3);
        i.visit(new Post("array", "Array"));
        i.visit(new Post("hash", "Hash"));
        i.visit(new Post("array", "Array"));
        i.visit(new Post("queue", "Queue"));
        System.out.println(i.recent);
        System.out.println(i.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) {}
}

최종 선택 순서는 인터페이스 의미, 순서·중복·키·양끝 규칙, 실제 연산 분포, 반환 소유권, 동시성 요구입니다.

클래스 이름을 외우는 것보다 이 질문을 반복하면 새로운 구현도 같은 기준으로 평가할 수 있습니다.

추가 연습: 순서를 보존하는 뷰와 스냅샷

LinkedHashMap<String, Integer>에 먼저 hash=50을 넣습니다. 그때 같은 원본을 감싸는 수정 불가 뷰 live와, LinkedHashMap으로 복사한 뒤 감싸는 수정 불가 스냅샷 snapshot을 각각 만드세요. 이후 원본에서 hash=60으로 바꾸고 queue=40을 추가합니다. 두 결과의 키 순서와 hash 값을 예상하고, live.put("set", 30)이 허용되는지 설명하세요. 모든 작업은 한 스레드에서 이 순서대로 실행합니다.

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