컬렉션 프레임워크 딥다이브

2. 핵심 원리

2.1 계층 구조

Iterable
└── Collection
    ├── List          순서 있음, 중복 허용, 인덱스 접근
    │   ├── ArrayList       동적 배열
    │   ├── LinkedList      이중 연결 리스트 (Deque도 구현)
    │   └── (Vector/Stack)  레거시, 쓰지 않음
    ├── Set           중복 없음
    │   ├── HashSet         해시 기반, 순서 없음
    │   ├── LinkedHashSet   삽입 순서 유지
    │   └── TreeSet         정렬 순서 (SortedSet/NavigableSet)
    └── Queue         FIFO
        ├── Deque           양방향 큐
        │   └── ArrayDeque  스택/큐 용도의 기본 선택
        └── PriorityQueue   힙 기반 우선순위

Map (Collection과 별개 계층)   키-값 쌍, 키 중복 없음
├── HashMap            해시 기반, 순서 없음
├── LinkedHashMap      삽입 순서 (또는 접근 순서) 유지
├── TreeMap            키 정렬 순서 (SortedMap/NavigableMap)
└── (Hashtable)        레거시, 쓰지 않음

Map이 Collection을 상속하지 않는 이유: Collection은 "원소의 모음"이고 Map은 "키→값 매핑"이라 add(E) 같은 메서드가 의미상 맞지 않는다. 대신 map.keySet(), map.values(), map.entrySet()으로 Collection 뷰를 얻는다.

2.2 ArrayList 내부: 동적 배열

ArrayList는 내부에 Object[] elementData 배열과 int size를 갖는다. 배열은 크기가 고정이므로 "동적"으로 보이게 하려면 꽉 찼을 때 더 큰 배열을 만들고 복사해야 한다.

확장 정책: 기본 초기 용량 10(첫 add 시점에 할당). 꽉 차면 newCapacity = oldCapacity + (oldCapacity >> 1), 즉 1.5배로 확장하고 Arrays.copyOf로 복사한다. 1.5배 확장은 드물게 일어나므로 n번 add의 총 복사 비용은 O(n), 1회당 상각 O(1)이다. 최종 크기를 알면 new ArrayList<>(expectedSize)로 확장을 없앨 수 있다.

중간 삽입이 O(n)인 이유: 배열은 연속 메모리다. 인덱스 3에 넣으려면 3 이후의 모든 원소를 한 칸씩 뒤로 옮겨야 한다. 앞쪽에 삽입할수록 옮길 원소가 많다. 그러나 System.arraycopy는 네이티브 메모리 블록 복사라 실제로는 매우 빠르며, 수천 개 수준에서는 체감이 안 된다.

2.3 LinkedList: 왜 실무에서 거의 안 쓰는가

LinkedList는 각 원소를 Node{item, prev, next}로 감싸 이중 연결한다. 이론적으로 "삽입/삭제 O(1)"이 장점이라고 배우지만, 그 O(1)은 삽입할 위치의 노드를 이미 알고 있을 때의 이야기다. list.add(5000, x)는 인덱스 5000까지 노드를 따라가야 하므로(랜덤 접근 불가) O(n)이다.

현대 CPU는 연속 메모리를 순차 접근할 때 캐시 프리페칭으로 극도로 빠르다. LinkedList는 노드마다 포인터를 따라 힙의 임의 위치로 점프하므로 캐시 미스가 반복된다.

결과적으로 거의 모든 실측에서 ArrayList가 빠르다. Iterator로 순회하면서 삭제하는 특수한 경우조차 ArrayList.removeIf가 더 빠른 경우가 많다. LinkedList의 저자인 Joshua Bloch 본인이 "쓴 적이 없다"고 말한 것은 유명하다.

큐/스택이 필요하면 ArrayDeque를 쓴다. 원형 배열 기반으로 양 끝 삽입/삭제가 O(1)이며 LinkedList보다 빠르고 메모리도 적다.

2.4 HashMap 내부: 해시 버킷

HashMap은 Node<K,V>[] table 배열(버킷 배열)을 갖는다. 각 Node는 {hash, key, value, next}다.

put(key, value) 과정:

1. key.hashCode()를 호출해 해시값 h를 얻는다.
2. h ^ (h >>> 16)으로 상위 비트를 하위에 섞는다(보조 해시, 하위 비트만 쓰는 인덱스 계산에서 분포를 고르게).
3. index = hash & (table.length - 1)로 버킷 인덱스를 계산한다(테이블 크기가 2의 거듭제곱이라 % 대신 비트 AND).
4. 그 버킷이 비어 있으면 새 Node를 넣는다.
5. 비어 있지 않으면(충돌) 연결 리스트를 따라가며 hash가 같고 equals가 true인 노드를 찾는다. 있으면 값 교체, 없으면 리스트 끝에 추가.
6. size > threshold(capacity × loadFactor)면 테이블을 2배로 확장하고 모든 노드를 재배치(rehash)한다.

get(key) 은 1~3까지 같고, 버킷의 리스트를 따라가며 hash == && equals로 찾는다.

여기서 hashCode/equals 규약이 왜 필요한지 명확해진다. equals가 true인데 hashCode가 다르면 다른 버킷에 들어가서 영원히 못 찾는다. 반대로 hashCode가 항상 같은 값을 반환하면 모든 원소가 한 버킷에 몰려 O(n)이 된다.

JDK 8의 트리화(treeification): 악의적이거나 나쁜 hashCode로 한 버킷에 원소가 몰리면 조회가 O(n)이 된다. 이를 완화하기 위해 버킷의 리스트가 8을 넘으면 레드-블랙 트리로 바꿔 최악을 O(log n)으로 보장한다. 단, 트리화되려면 키가 Comparable이거나, 아니면 System.identityHashCode로 순서를 정한다.

초기 용량 지정: 원소 개수 n을 안다면 new HashMap<>(n / 0.75 + 1) 정도로 잡으면 확장(rehash)이 없다. 실무에서는 HashMap.newHashMap(n)(JDK 19+)이 이 계산을 해 준다.

null: HashMap은 null 키 1개와 null 값을 허용한다(null 키는 해시 0, 버킷 0). Hashtable과 ConcurrentHashMap은 둘 다 금지.

2.5 HashSet은 HashMap 위에 있다

HashSet<E>의 소스를 열면 private transient HashMap<E,Object> map;이 있고, add(e)는 map.put(e, PRESENT)(PRESENT는 더미 Object)이다. 즉 HashSet은 값이 없는 HashMap이다.

따라서 HashSet의 성능 특성, hashCode/equals 의존성, 초기 용량/로드 팩터가 전부 HashMap과 같다. LinkedHashSet은 LinkedHashMap 위에, TreeSet은 TreeMap 위에 같은 방식으로 구현되어 있다.

2.6 순서 보장: LinkedHashMap, TreeMap

LinkedHashMap은 HashMap을 상속하고 각 노드에 before/after 참조를 추가해 삽입 순서를 연결 리스트로 유지한다. 순회는 이 리스트를 따르므로 삽입 순서가 보존된다.

생성자 new LinkedHashMap<>(cap, 0.75f, true)로 accessOrder = true를 주면 get할 때마다 그 엔트리를 리스트 끝으로 옮긴다. 이것과 removeEldestEntry() 오버라이딩을 결합하면 몇 줄로 LRU 캐시가 만들어진다.

TreeMap은 키를 Comparable(또는 생성자로 넘긴 Comparator)로 비교해 균형 이진 탐색 트리에 넣는다. 해시를 쓰지 않으므로 hashCode/equals가 아니라 compareTo가 0인지로 같은 키를 판단한다. equals와 compareTo가 일관되지 않으면 HashMap과 TreeMap에서 동작이 달라진다.

2.7 시간 복잡도 비교표

"평균"은 해시 분포가 좋을 때. 최악(모두 충돌)은 JDK 8+에서 O(log n).

2.8 Iterator와 ConcurrentModificationException

for (E e : collection)은 컴파일러가 Iterator로 변환한다. ArrayList, HashMap 등의 Iterator는 fail-fast다. 컬렉션 내부에 modCount(구조 변경 횟수)가 있고, Iterator는 생성 시점의 modCount를 기억한다. next()마다 현재 modCount와 비교해 다르면 ConcurrentModificationException을 던진다.

for (String s : list) {
    if (s.startsWith("tmp")) list.remove(s);   // modCount 변경 → 다음 next()에서 CME
}

이름에 "Concurrent"가 있지만 단일 스레드에서 순회 중 수정해도 발생한다. 해결책:

CopyOnWriteArrayList나 ConcurrentHashMap의 Iterator는 fail-safe(스냅샷 또는 약한 일관성)라 예외가 없지만, 동시성 레슨의 주제다.

2.9 불변 컬렉션

JDK 9의 List.of, Set.of, Map.of, JDK 10의 List.copyOf 등은 진짜 불변(수정 메서드 호출 시 UnsupportedOperationException) 컬렉션을 만든다. Collections.unmodifiableList(list)는 원본을 감싸는 뷰라서 원본을 바꾸면 뷰도 바뀌지만, List.of/copyOf는 복사본이라 원본과 독립적이다.

불변 컬렉션은 방어적 복사, 상수 정의, 메서드 반환값에 쓴다. "이 리스트는 바뀌지 않는다"를 타입이 아닌 런타임 예외로 보장한다는 점은 아쉽지만, 실수를 즉시 드러낸다는 점에서 유용하다.

2.10 정렬: Comparable vs Comparator

JDK 8+의 Comparator 조합 API가 사실상 표준이다.

orders.sort(Comparator.comparing(Order::status)
                      .thenComparing(Order::amount, Comparator.reverseOrder())
                      .thenComparing(Order::id));

compareTo는 음수/0/양수를 반환하며, a.compareTo(b) == 0이면 a.equals(b)가 true인 것이 권장된다(TreeSet이 compareTo로 중복을 판단하기 때문). List.sort와 Collections.sort는 TimSort(안정 정렬, O(n log n))를 쓴다.