컬렉션 구현 선택 기준

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

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

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

단일 `List` 검색의 비용

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

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

lab/ListForEveryRequirementBug.java

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이 요구를 직접 표현합니다.

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

인터페이스 선택 질문 네 개

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

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

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

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

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

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

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)은 비교자 규칙이 전제입니다.

src/CollectionChoiceScenarios.java

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

네 컬렉션에 넣은 값과 실제 출력
실제 변수·구현	원문에서 수행한 연산	표준 출력
`orderedTitles` `ArrayList`	`"array"` 두 번 추가 입력 순서와 중복 보존	`[array, array]`
`firstTags` `LinkedHashSet`	`addAll(orderedTitles)` 같은 값은 한 번만 보관	`[array]`
`totals` `HashMap`	각 제목에 `merge`로 1 누적 `1 + 1 = 2`	`{array=2}`
`pending` `ArrayDeque`	`offer("print")` `poll()`로 명령 제거·반환	`print`

orderedTitles ArrayList: 원문에서 수행한 연산:
"array" 두 번 추가
입력 순서와 중복 보존
표준 출력: [array, array]
firstTags LinkedHashSet: 원문에서 수행한 연산:
addAll(orderedTitles)
같은 값은 한 번만 보관
표준 출력: [array]
totals HashMap: 원문에서 수행한 연산:
각 제목에 merge로 1 누적
1 + 1 = 2
표준 출력: {array=2}
pending ArrayDeque: 원문에서 수행한 연산:
offer("print")
poll()로 명령 제거·반환
표준 출력: print

표의 네 출력은 원문 println 순서입니다. 앞의 세 컬렉션은 제목 array를 다루고, 큐의 입력은 print입니다. poll 뒤 큐가 빈다는 것은 소스 추적이며 따로 출력하지 않습니다. HashMap의 키는 하나뿐이라 여러 키의 반복 순서를 보여 주는 예제가 아닙니다.

예제의 네 컬렉션은 서로 다른 역할을 맡습니다. 앞의 세 컬렉션은 array를 다루고, 큐에는 print 명령을 넣습니다.

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

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

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

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

반대로 불변 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와 실제 작업 부하로 확인하고, 기능 결과가 같은지 먼저 확인합니다.

app/BoardCollectionDesign.java

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

두 게시글을 처리한 네 저장소의 최종 값
내부 필드·타입	처리·반환에서 맡은 역할	최종 값과 출력 여부
`pending` `Queue<Entry>`	`poll()`: hash → queue 마지막 빈 조회는 `null`	`[]` 소스 추적 · 출력하지 않음
`entries` `List<Entry>`	`add(e)`로 등록 순서 보관 `entries()`: `List.copyOf`	첫 게시글: `title=hash` `viewCount=50` `tags=[java, set]` 둘째 게시글: `title=queue` `viewCount=40` `tags=[java, deque]`
`tags` `Set<String>`	`addAll(e.tags())` 고유 값·첫 등장 순서 `tags()`: `List.copyOf`	`[java, set, deque]` 실제 둘째 출력
`totals` `Map<String, Integer>`	제목별 조회수 `merge` 복사한 LinkedHashMap을 `unmodifiableMap`으로 감쌈	`{hash=50, queue=40}` 실제 셋째 출력

pending Queue<Entry>: 처리·반환에서 맡은 역할:
poll(): hash → queue
마지막 빈 조회는 null
최종 값과 출력 여부:
[]
소스 추적 · 출력하지 않음
entries List<Entry>: 처리·반환에서 맡은 역할:
add(e)로 등록 순서 보관
entries(): List.copyOf
최종 값과 출력 여부:
첫 게시글: title=hash
viewCount=50
tags=[java, set]
둘째 게시글: title=queue
viewCount=40
tags=[java, deque]
tags Set<String>: 처리·반환에서 맡은 역할:
addAll(e.tags())
고유 값·첫 등장 순서
tags(): List.copyOf
최종 값과 출력 여부:
[java, set, deque]
실제 둘째 출력
totals Map<String, Integer>: 처리·반환에서 맡은 역할:
제목별 조회수 merge
복사한 LinkedHashMap을
unmodifiableMap으로 감쌈
최종 값과 출력 여부:
{hash=50, queue=40}
실제 셋째 출력

첫 출력은 두 Entry의 리스트이며 표에는 각 원소의 title, viewCount, tags 필드를 풀어 적었습니다. 태그 순서는 LinkedHashSet의 첫 등장 순서입니다. totals()는 새 LinkedHashMap 복사본을 감싸므로 내부 Map의 실시간 뷰를 반환하지 않습니다. 반환 뒤 변경을 시도하는 실험은 이 main에 없습니다.

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

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

연습 문제

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

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

정답과 해설

ArrayDeque에는 최근 slug 순서를, HashMap에는 slug별 상세를 저장합니다. 목록 상한은 visit의 크기 검사와 removeLast가 적용하며 ArrayDeque 자체의 고정 용량이 아닙니다.

재방문 slug는 Deque 기존 값을 지우고 앞에 넣습니다. 아래 main은 상한 3으로 실행한 작은 예이며, 문제의 10개 상한을 적용하려면 Index에 10을 전달합니다.

exercise/RecentPostIndexSolution.java

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

네 방문으로 최근 순서와 slug 사전을 갱신한다
visit 입력	recent · 최신 → 오래된 순	bySlug 관계 · 순서 비보장
첫 방문 `slug=array`, `title=Array`	`[array]`	`array → Array`
둘째 방문 `slug=hash`, `title=Hash`	`[hash, array]`	`array → Array` `hash → Hash`
재방문 `slug=array`, `title=Array`	`[array, hash]`	같은 slug의 Post 교체 `array → Array` `hash → Hash`
넷째 방문 `slug=queue`, `title=Queue`	`[queue, array, hash]`	`array → Array` `hash → Hash` `queue → Queue`

첫 방문 slug=array, title=Array: recent · 최신 → 오래된 순: [array]
bySlug 관계 · 순서 비보장: array → Array
둘째 방문 slug=hash, title=Hash: recent · 최신 → 오래된 순: [hash, array]
bySlug 관계 · 순서 비보장:
array → Array
hash → Hash
재방문 slug=array, title=Array: recent · 최신 → 오래된 순: [array, hash]
bySlug 관계 · 순서 비보장:
같은 slug의 Post 교체
array → Array
hash → Hash
넷째 방문 slug=queue, title=Queue: recent · 최신 → 오래된 순: [queue, array, hash]
bySlug 관계 · 순서 비보장:
array → Array
hash → Hash
queue → Queue

각 행은 visit 직후의 소스 추적이며 사전의 화살표는 slug와 Post의 title 관계입니다. 실제 출력은 [queue, array, hash]와 Post[slug=hash, title=Hash]의 두 줄입니다. limit=3에 고유 slug가 3개라 removeLast()는 실행되지 않습니다. 원문에는 bySlug에서 값을 지우는 코드가 없어 최근 목록과 상세 사전의 보관 범위가 다릅니다.

최신순은 queue, array, hash이고 Map 조회는 Hash 게시글을 반환합니다.

visit는 두 구조 갱신을 한 메서드에 모은 단일 스레드 예제이며 원자적 갱신을 보장하지 않습니다. recent에서 오래된 slug를 제거해도 bySlug에서는 지우지 않으므로 최근 목록과 상세 사전의 보관 범위가 다릅니다. 또한 recent.remove(slug)는 값을 찾아 순회하므로 방문 처리 전체가 O(1)은 아닙니다.

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

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

단일 List 검색의 비용