Java Collections Framework, 하나의 철학으로 읽는다

Java Collections Framework는 단순한 자료구조 모음이 아니다. 인터페이스 계층, 구현체 선택, 유틸리티 메서드 모두 하나의 원칙 위에 서 있다 — “무엇을 보장하느냐가 설계를 결정한다”. 순서를 보장하면 비용이 붙고, 중복을 막으면 해시가 개입하고, 정렬을 제공하면 트리가 필요하다. 이 16개 챕터는 그 트레이드오프의 반복적인 표현이다. 과연 어떤 기준이 올바른 컬렉션 선택을 만드는가?

인터페이스 계층이 말하는 것

Collection은 List, Set, Queue의 공통 조상이다. Map은 별도 계층이다. 이 분리는 임의적이지 않다. Collection이 다루는 건 단일 원소의 집합이고, Map이 다루는 건 키-값 쌍이다. 근본적으로 다른 질문에 대한 답이다.

Iterable<E>
  └─ Collection<E>
      ├─ List<E>     // 순서 O, 중복 O
      ├─ Set<E>      // 중복 X
      └─ Queue<E>    // FIFO

Map<K,V>             // 키-값, 별도 계층

List는 인덱스를 약속한다. Set은 중복 없음을 약속한다. Queue는 FIFO를 약속한다. 각 인터페이스가 어떤 **보장(guarantee)**을 선택하느냐에 따라 내부 구조와 허용 연산이 달라진다. 그리고 이 보장들은 공짜가 아니다. 인덱스 접근을 약속하려면 연속 메모리가 필요하고, 중복 금지를 약속하려면 동등성 비교가 필요하고, FIFO를 약속하려면 삽입·제거 순서를 추적해야 한다.

순서·중복 축으로 구현체 읽기

보장의 종류는 두 축으로 정리된다 — 순서 여부와 중복 허용 여부.

ArrayList는 인덱스 기반 동적 배열이므로 get(i)가 O(1)이다. 초기 용량 10에서 시작해 75%가 차면 1.5배로 확장된다. 중간 삽입·삭제는 뒤 원소를 전부 밀거나 당겨야 하므로 O(n)이다. 반면 LinkedList는 이중 연결 리스트 구조라 앞·뒤 삽입·삭제가 O(1)이지만 인덱스 조회는 head에서 순차 탐색해야 하므로 O(n)이다. 실제 벤치마크에서 끝에 추가하는 작업은 ArrayList가 더 빠른 경우가 많다. 연속 메모리는 CPU 캐시 친화적이기 때문이다.

HashSet은 순서를 포기한 대신 add·contains·remove 모두 평균 O(1)을 얻는다. LinkedHashSet은 삽입 순서를 유지하려고 해시 테이블에 이중 연결 리스트를 추가로 붙인다 — 메모리를 더 쓰는 대신 예측 가능한 순회를 얻는다. TreeSet은 레드-블랙 트리로 자동 정렬을 제공하는 대신 모든 연산이 O(log n)이다. Map 계열도 정확히 같은 패턴이 반복된다. HashMap → LinkedHashMap → TreeMap 순으로 보장이 추가되고, 그에 따라 비용이 올라간다.

hashCode·equals가 계약인 이유

HashSet과 HashMap이 O(1) 성능을 제공하는 전제 조건이 있다. 객체가 hashCode()와 equals()를 올바르게 구현해야 한다는 것이다. 두 객체가 equals()로 같다면 hashCode()도 반드시 같아야 한다. 이 계약이 깨지면 같은 논리적 객체가 서로 다른 버킷에 저장되고, contains는 false를 반환한다. 중복을 제거하려고 HashSet에 넣었는데 중복이 그대로 남는 버그의 근원이 여기에 있다.

@Override
public boolean equals(Object o) { ... }

@Override
public int hashCode() {
    return Objects.hash(name, age); // equals에 사용한 필드와 동일하게
}

TreeSet·TreeMap에서는 이 계약이 다른 형태로 나타난다. 정렬 순서가 equals와 일관되어야 한다. Comparator가 0을 반환하는 두 객체는 equals()도 true여야 한다. 그렇지 않으면 Set임에도 중복이 허용되는 기이한 동작이 발생한다. Java 공식 문서는 이를 “consistent with equals”라는 표현으로 명시한다.

Queue와 Deque — 단방향에서 양방향으로

Queue는 FIFO다. offer로 뒤에 넣고 poll로 앞에서 꺼낸다. Deque는 양방향 큐다. 앞·뒤 모두 삽입·삭제가 가능하므로 Queue도 되고 Stack도 된다. 메서드 쌍이 두 종류인 것도 이 때문이다. offer/poll/peek는 실패 시 null을 반환하고, add/remove/element는 실패 시 예외를 던진다. 용량 제한 없는 ArrayDeque에서는 사실상 동일하게 동작하지만, BlockingQueue 계열을 쓸 때 차이가 드러난다.

Stack 클래스는 Java 1.0 유산이다. Vector를 상속하기 때문에 모든 메서드가 synchronized다 — 단일 스레드에서도 불필요한 동기화 비용을 지불한다. 게다가 Vector 상속으로 인해 중간 삽입·삭제 메서드가 공개돼 있어 스택의 의미론을 위반하는 코드가 쓰여질 수 있다.

// ❌ 레거시
Stack<String> stack = new Stack<>();

// ✅ 현대적
Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.pop();

ArrayDeque는 순환 배열 구조로 LinkedList보다 메모리 효율이 높고 캐시 친화적이다. PriorityQueue는 힙 구조로 우선순위에 따라 자동 정렬된다. 기본은 최소 힙이며, Collections.reverseOrder()를 넘기면 최대 힙이 된다. offer와 poll 모두 O(log n)이지만 peek는 O(1)이다. Top K 문제, 중앙값 추적, 작업 스케줄러 모두 이 구조로 자연스럽게 모델링된다.

Collections 유틸 — 보일러플레이트를 없애는 정적 도구들

java.util.Collections는 정적 메서드 모음이다. sort·reverse·shuffle·rotate·swap 같은 변환, binarySearch·min·max·frequency 같은 검색, 그리고 unmodifiableList·synchronizedMap 같은 래퍼를 제공한다. binarySearch는 정렬된 리스트에서만 의미가 있고, 찾지 못하면 삽입 위치에 기반한 음수를 반환한다.

불변 컬렉션이 필요하다면 Java 9+ List.of()·Set.of()·Map.of()가 더 명확하다. Collections.unmodifiableList는 원본 리스트에 여전히 의존하기 때문에 원본이 바뀌면 래퍼를 통한 읽기 결과도 바뀐다. List.of()는 처음부터 독립적인 불변 인스턴스를 만든다.

정리

• List vs Set: 중복이 필요하면 List, 필요 없으면 Set. 순서가 필요하면 Linked*, 정렬이 필요하면 Tree*.
• HashMap이 기본값: 순서·정렬이 필요할 때만 LinkedHashMap·TreeMap으로 변경한다.
• Stack 클래스는 쓰지 않는다: ArrayDeque가 더 빠르고 명확하며 의미론도 정확하다.
• hashCode·equals 계약은 해시 기반 컬렉션 정확성의 전제 조건이다. 어기면 contains가 거짓말을 한다.
• 보장에는 비용이 따른다: 무엇을 보장받으려는지 먼저 결정하고, 그 보장을 제공하는 구현체를 선택한다.

다음 글에서는 ArrayList의 동적 배열 확장 메커니즘과 LinkedList의 이중 연결 리스트 내부 구조를 구체적으로 추적한다.