컬렉션 구현 선택 기준
`List`·`Set`·`Map`·`Deque` 선택을 순서·중복·조회 키·양끝 연산에서 시작하고 실제 연산 분포로 구현을 좁힙니다.
컬렉션 선택을 클래스 이름 암기로 시작하면 ArrayList와 LinkedList 비교에서 멈춥니다.
먼저 결과가 순서를 갖는지, 중복을 허용하는지, 키로 값을 찾는지, 양끝 제거가 필요한지 결정합니다.
인터페이스가 정해진 뒤 조회·삽입·범위 질의의 실제 비율로 구현을 고릅니다.
단일 List 검색의 비용
완료 주제를 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 topic = "topic-" + value;
for (String existing : unique) {
comparisons++;
if (existing.equals(topic)) break;
}
if (!unique.contains(topic)) unique.add(topic);
}
System.out.println("size=" + unique.size() + ", manual-comparisons=" + comparisons);
}
}코드는 포함 여부에서도 다시 비교해 실제 비용을 더 늘립니다.
중복 없는 존재 검사가 본질이면 Set이 요구를 직접 표현합니다.
순서가 필요하면 LinkedHashSet으로 세부 구현을 선택합니다.
인터페이스 선택 질문 네 개
원소를 index·순서로 다루고 중복을 허용하면 List입니다.
값 존재와 집합 연산이 중심이면 Set입니다.
키와 값 관계를 저장하면 Map입니다.
최근/가장 오래된 원소를 양끝에서 처리하면 Deque입니다.
PriorityQueue는 입력 순서가 아니라 우선순위 제거가 필요할 때 별도 후보입니다.
인터페이스는 불필요한 연산도 제한합니다.
Queue 매개변수는 소비자가 index get에 의존하지 않게 하고, Set은 중복 add의 의미를 boolean으로 보여 줍니다.
변수 타입을 가장 넓은 Collection로 무조건 올리면 키 조회나 양끝 의미가 사라져 오히려 규칙이 약해질 수 있습니다.
구현 선택 기준: 연산 분포·규모
List의 일반 기본값은 ArrayList입니다.
임의 조회와 전체 순회가 빠르고 메모리 효율이 좋습니다.
이미 Node 위치를 가진 빈번한 중간 변경처럼 구체 증거가 있을 때 LinkedList를 검토합니다.
Queue·Stack에는 ArrayDeque가 기본입니다.
Set과 Map은 순서가 없으면 Hash 계열, 최초 삽입 순서면 LinkedHash 계열, 정렬·범위면 Tree 계열을 고려합니다.
평균 O(1)은 좋은 hashCode와 적절한 적재 계수가 전제이고 Tree의 O(로그 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> orderedSessions = new ArrayList<>();
orderedSessions.add("array");
orderedSessions.add("array");
Set<String> firstTags = new LinkedHashSet<>();
firstTags.addAll(orderedSessions);
Map<String, Integer> totals = new HashMap<>();
for (String topic : orderedSessions) {
totals.merge(topic, 1, Integer::sum);
}
Queue<String> pending = new ArrayDeque<>();
pending.offer("print");
System.out.println(orderedSessions);
System.out.println(firstTags);
System.out.println(totals);
System.out.println(pending.poll());
}
}같은 문자열도 네 자료 구조에서 의미가 다릅니다.
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)은 Node를 이미 알 때이고, ArrayList 끝 add O(1)은 상환 비용입니다.
HashMap get 평균 O(1)은 해시 분산이 전제입니다.
작은 데이터에서는 코드 단순성·캐시 지역성·할당 수가 복잡도 차이보다 중요할 수 있습니다. 벽시계 측정은 JMH와 실제 작업 부하로 확인하고, 기능 결과가 같은지 먼저 확인합니다.
import java.util.ArrayDeque;
import java.util.ArrayList;
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 StudyCollectionDesign {
public static void main(String[] args) {
Log log = new Log();
log.enqueue(new Entry("hash", 50, List.of("java", "set")));
log.enqueue(new Entry("queue", 40, List.of("java", "deque")));
log.processAll();
System.out.println(log.entries());
System.out.println(log.tags());
System.out.println(log.totals());
}
private static final class Log {
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.topic(), e.minutes(), Integer::sum);
}
}
List<Entry> entries() {
return List.copyOf(entries);
}
Set<String> tags() {
return Set.copyOf(tags);
}
Map<String, Integer> totals() {
return Map.copyOf(totals);
}
}
private record Entry(String topic, int minutes, List<String> tags) {
Entry {
tags = List.copyOf(tags);
}
}
}한 애플리케이션에서 자료 구조 하나만 고집하지 않습니다. 대기 중은 FIFO, 항목은 중복·순서, tags는 고유·첫 등장, totals는 주제 관계를 각각 맡습니다.
연습 문제
“최근 본 문서 10개를 중복 없이 최신순으로 보이고, slug로 문서 상세를 즉시 찾는다”를 구현하세요.
순서 구조와 키 조회 구조를 하나로 억지로 합치지 않습니다.
정답과 해설
ArrayDeque는 최신순·용량을, HashMap은 slug 조회를 담당합니다.
재방문 slug는 Deque 기존 값을 지우고 앞에 넣습니다.
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
public final class RecentDocumentIndexSolution {
public static void main(String[] args) {
Index i = new Index(3);
i.visit(new Doc("array", "Array"));
i.visit(new Doc("hash", "Hash"));
i.visit(new Doc("array", "Array"));
i.visit(new Doc("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, Doc> bySlug = new HashMap<>();
Index(int limit) {
this.limit = limit;
}
void visit(Doc d) {
bySlug.put(d.slug(), d);
recent.remove(d.slug());
recent.addFirst(d.slug());
if (recent.size() > limit) recent.removeLast();
}
Doc find(String slug) {
return bySlug.get(slug);
}
}
private record Doc(String slug, String title) {}
}최신순은 큐,배열,해시이고 Map 조회는 Hash 문서를 반환합니다.
두 구조의 일관성 갱신은 Index 한 메서드 안에 모았습니다.
최종 선택 순서는 인터페이스 의미, 순서·중복·키·양끝 규칙, 실제 연산 분포, 반환 소유권, 동시성 요구입니다. 클래스 이름을 외우는 것보다 이 질문을 반복하면 새로운 구현도 같은 기준으로 평가할 수 있습니다.