컬렉션 프레임워크 — List, Set, Map 제대로 쓰기

배열을 쓰다 보면 한 가지 답답한 순간이 온다. "크기를 미리 정해야 한다고?" 데이터가 몇 개 들어올지도 모르는데, 왜 처음부터 칸 수를 정해놔야 하는 걸까?

배열의 한계, 컬렉션이 필요한 이유

컬렉션 프레임워크 는 가변 크기 데이터를 다루기 위해 Java가 제공하는 자료구조 라이브러리예요. 배열의 고정 크기, 수동 삽입/삭제, 기능 부족 문제를 해결합니다.

배열이 왜 한계인지 코드로 볼게요.

String[] names = new String[3];
names[0] = "Alice";
names[1] = "Bob";
names[2] = "Charlie";
// names[3] = "Dave"; // ArrayIndexOutOfBoundsException!

배열은 고정 크기이기 때문에 초과하면 더 큰 배열을 새로 만들어 복사해야 해요. 중간 삽입/삭제도 직접 요소를 밀고 당겨야 하고, contains 같은 기본 기능도 반복문을 돌려야 합니다. 컬렉션 프레임워크는 이 모든 작업을 메서드로 추상화해요.

컬렉션 프레임워크 구조

컬렉션은 인터페이스 계층으로 설계되어 있어요. 용도에 따라 세 갈래로 나뉩니다.

Iterable
  └── Collection
        ├── List   — 순서 있음, 중복 허용
        ├── Set    — 순서 없음, 중복 불허
        └── Queue  — FIFO 구조

Map (별도 계층) — 키-값 쌍, 키 중복 불허

인터페이스로 분리한 이유는 구현체를 바꿔 끼울 수 있게 하기 위해서예요. List<String> names = new ArrayList<>()로 선언하면, 나중에 LinkedList로 교체해도 나머지 코드는 바뀌지 않습니다.

List — ArrayList

ArrayList는 내부적으로 Object[] 배열 을 사용하되, 꽉 차면 1.5배 크기의 새 배열을 만들어 복사하는 동적 배열이에요.

List<String> fruits = new ArrayList<>();
fruits.add("사과");
fruits.add("바나나");
fruits.add("체리");

fruits.get(0);             // "사과" — 인덱스로 접근
fruits.set(1, "블루베리");   // 수정
fruits.remove("사과");      // 값으로 삭제
fruits.contains("블루베리"); // true

내부 배열 구조를 그림으로 보면 이렇습니다.

초기 상태 (기본 용량 10):
[사과][바나나][체리][ ][ ][ ][ ][ ][ ][ ]

꽉 찼을 때 → 1.5배 배열 생성 후 복사:
[사과][바나나][체리][딸기][...][포도][ ][ ][ ][ ][ ]

배열 기반이기 때문에 인덱스 접근은 O(1)로 빠릅니다. 반면 중간 삽입/삭제 시에는 뒤의 요소를 전부 밀거나 당겨야 해서 O(n)이 돼요.

ArrayList 시간복잡도

핵심: ArrayList는 읽기가 빠르고, 중간 삽입/삭제가 느리다.

List — LinkedList

LinkedList는 ** 각 노드가 이전/다음 노드의 참조를 갖는 이중 연결 리스트 **예요. ArrayList와 정반대의 성능 특성을 가집니다.

내부 구조

[null|사과|→] ←→ [←|바나나|→] ←→ [←|체리|null]
 prev  data next

중간에 끼워넣거나 빼는 건 참조만 바꾸면 되므로, 위치를 이미 알고 있다면 O(1)이에요. 하지만 위치를 찾아가는 데 O(n)이 걸리기 때문에 인덱스 기반 삽입/삭제도 결국 O(n)입니다.

ArrayList vs LinkedList 비교

*LinkedList의 중간 삽입/삭제가 O(n)인 이유: 삽입 자체는 O(1)이지만, 해당 위치를 찾아가는 데 O(n)이 걸린다.

대부분의 경우 ArrayList를 쓰면 됩니다. LinkedList가 이론적으로 유리한 상황(맨 앞 삽입/삭제)에서도, ArrayList의 CPU 캐시 친화성 덕분에 실측 성능이 더 좋은 경우가 많아요.

Set — HashSet

HashSet 은 해시 테이블 기반으로 중복을 허용하지 않는 컬렉션이에요. 내부적으로 HashMap을 사용합니다.

Set<String> languages = new HashSet<>();
languages.add("Java");
languages.add("Python");
languages.add("Java");   // 중복 → 무시됨
languages.size();             // 2
languages.contains("Java");   // true — O(1)

중복 판단 기준: hashCode() + equals()

HashSet이 중복을 판단하는 과정은 두 단계예요.

1. hashCode()로 버킷(저장 위치)을 결정합니다
2. 같은 버킷에 이미 요소가 있으면 equals()로 실제 동등성을 비교합니다
3. 같으면 중복이므로 추가하지 않고, 다르면 같은 버킷에 추가합니다(해시 충돌)

이 흐름 때문에 커스텀 클래스를 HashSet에 넣으려면 hashCode()와 equals()를 반드시 둘 다 오버라이드해야 해요.

class Student {
    String name;
    int id;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Student s)) return false;
        return id == s.id && Objects.equals(name, s.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, id);
    }
}

equals()만 오버라이드하고 hashCode()를 빠뜨리면, 내용이 같아도 다른 버킷에 들어가서 중복으로 판단되지 않아요.

HashSet 시간복잡도

해시 충돌이 심하면 O(n)까지 나빠질 수 있지만, 보통은 O(1)로 생각하면 됩니다.

Set — TreeSet, LinkedHashSet

TreeSet 은 Red-Black 트리 기반으로 요소를 자동 정렬 합니다. 모든 연산이 O(log n)이에요. LinkedHashSet 은 HashSet에 연결 리스트를 더해 삽입 순서를 유지 해요. 성능은 HashSet과 거의 동일합니다.

Map — HashMap

HashMap 은 키-값 쌍을 해시 테이블에 저장하는 컬렉션이에요. HashSet의 내부도 사실 HashMap으로 구현되어 있습니다.

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 95);
scores.put("Bob", 87);
scores.get("Alice");                  // 95
scores.getOrDefault("Dave", 0);       // 0 — 없는 키에 기본값
scores.containsKey("Bob");            // true

put/get의 내부 동작

put("Alice", 95)를 호출하면 다음 순서로 동작해요.

1. "Alice".hashCode()로 해시값을 계산합니다
2. 해시값으로 버킷 인덱스를 결정합니다 (해시값 % 배열 크기)
3. 해당 버킷이 비어있으면 바로 저장합니다
4. 이미 차 있으면 equals()로 키를 비교합니다 -- 같은 키면 값을 덮어쓰고, 다른 키면 체이닝(연결 리스트 or 트리)합니다

null 허용 여부

HashMap은 key에 null 하나, value에 null 여러 개 를 허용해요. 반면 Hashtable이나 ConcurrentHashMap은 null을 아예 허용하지 않습니다. 멀티스레드 환경에서 null 키/값이 있으면 containsKey와 get의 의미가 모호해지기 때문이에요.

HashMap 시간복잡도

Map — TreeMap, LinkedHashMap

TreeMap 은 키 기준 자동 정렬(Red-Black 트리, O(log n)), LinkedHashMap 은 삽입 순서를 유지합니다. LinkedHashMap은 removeEldestEntry를 오버라이드하면 LRU 캐시를 간단히 구현할 수 있어요.

주의할 점

ConcurrentModificationException

for-each 순회 중 원본 컬렉션을 수정하면 이 예외가 발생해요.

List<String> names = new ArrayList<>(List.of("Alice", "Bob", "Charlie"));

for (String name : names) {
    if (name.equals("Bob")) {
        names.remove(name); // ConcurrentModificationException!
    }
}

for-each는 내부적으로 Iterator를 사용하는데, Iterator가 생성된 시점의 modCount와 현재 modCount가 다르면 예외를 던집니다. 해결 방법은 세 가지예요.

1. Iterator.remove() -- Iterator를 직접 사용하면서 삭제
2. removeIf() (Java 8+) -- 가장 깔끔
3. ** 새 컬렉션에 담기**

// removeIf — 가장 간결한 방법
names.removeIf(name -> name.equals("Bob"));

hashCode/equals 불일치

커스텀 객체를 HashSet이나 HashMap 키로 사용할 때, equals()만 오버라이드하고 hashCode()를 빠뜨리면 논리적으로 같은 객체가 중복으로 들어가요. 두 메서드는 반드시 함께 오버라이드해야 합니다.

ArrayList 초기 용량

대량 데이터를 넣을 걸 미리 안다면, new ArrayList<>(expectedSize)로 초기 용량을 지정하는 게 좋아요. 지정하지 않으면 기본 용량 10에서 시작해 계속 배열 복사가 일어나 GC 부담이 커집니다.

Collections 유틸리티

java.util.Collections 클래스는 정렬, 수정 불가 래핑, 빈 컬렉션 생성 등 편리한 정적 메서드를 제공합니다.

List<Integer> numbers = new ArrayList<>(List.of(30, 10, 20, 50, 40));
Collections.sort(numbers);                             // [10, 20, 30, 40, 50]
Collections.sort(numbers, Collections.reverseOrder());  // [50, 40, 30, 20, 10]

Collections.unmodifiableList()로 수정 불가 래퍼를 만들 수 있지만, 원본을 수정하면 래퍼에도 반영돼요. 진짜 불변이 아닌 점에 주의해야 합니다.

불변 컬렉션 (Java 9+)

Java 9부터 List.of(), Set.of(), Map.of()로 ** 진짜 불변 컬렉션 **을 만들 수 있어요.

List<String> fruits = List.of("사과", "바나나", "체리");
// fruits.add("딸기"); // UnsupportedOperationException!

Set<String> colors = Set.of("빨강", "파랑", "초록");
// Set.of("빨강", "빨강"); // IllegalArgumentException!

Collections.unmodifiableList()와의 차이점은 두 가지예요. List.of()는 원본이 없으므로 외부에서 수정할 통로가 없고, null 요소도 허용하지 않습니다.

선택 가이드

어떤 컬렉션을 쓸지 결정하는 기준은 단순해요.

순서가 필요하다 → 인덱스 접근 多 → ArrayList / 앞뒤 삽입삭제 多 → LinkedList
중복 제거가 필요하다 → 순서 무관 → HashSet / 삽입 순서 → LinkedHashSet / 정렬 → TreeSet
키-값 쌍이 필요하다 → 순서 무관 → HashMap / 삽입 순서 → LinkedHashMap / 키 정렬 → TreeMap

▸ TIP 이 글의 코드 예제를 직접 실행해보고 싶다면 Java 기본기 핸드북을 확인해보세요.

정리

다음 글에서는 ** 제네릭 **을 다뤄볼게요. 타입 소거가 뭔지, 와일드카드는 어떻게 쓰는지, PECS 원칙은 왜 필요한지 -- 컬렉션을 제대로 쓰려면 반드시 알아야 할 내용입니다.