컬렉션 선택

자료구조 선택의 기준은 메모리에 어떻게 놓이는가다.

List — 거의 항상 ArrayList

• ArrayList — 연속된 배열. 인덱스 접근 O(1) · 캐시 지역성이 좋다

  • 중간 삽입/삭제는 뒤를 밀어야 해 O(n)

• LinkedList — 노드가 흩어져 있고 포인터로 이어진다

  • 중간 삽입/삭제 O(1) — 단, 그 위치를 '찾는' 데 O(n)
  • 노드마다 객체 헤더 + 포인터 2개 → 메모리를 3~4배 쓴다
  • 캐시 미스가 잦아 실측이 대체로 느리다

"중간 삽입이 많으면 LinkedList"는 교과서적 답이지만 실무에서는 거의 틀린다. 위치를 찾는 비용과 캐시 미스가 이득을 삼킨다. 큐가 필요하면 ArrayDeque가 낫다.

Map — HashMap의 내부

버킷 배열 + 각 버킷의 연결 리스트

• ① hashCode 로 버킷을 고른다
• ② 그 안에서 equals 로 찾는다

한 버킷에 8개 이상 쌓이고 전체 용량이 64 이상이면

• 연결 리스트를 '레드-블랙 트리' 로 바꾼다 (Java 8+)
• 최악의 경우도 O(log n) 이 된다 (해시 충돌 공격 방어)

// 크기를 알면 미리 잡는다 — 리사이징(전체 재해싱)을 피한다
new HashMap<>(expectedSize / 0.75f + 1);

순서가 필요하면

• HashMap — 순서 없음 (사실상 예측 불가)
• LinkedHashMap — 삽입 순서 유지. accessOrder=true 로 LRU 캐시를 만들 수 있다
• TreeMap — 키 정렬 순서. O(log n) · 범위 조회 가능

// LRU 캐시 5줄
new LinkedHashMap<K,V>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry<K,V> e) { return size() > MAX; }
};

동시성 컬렉션

• ConcurrentHashMap — 버킷 단위 락 + CAS. 읽기는 대체로 락 없음
• CopyOnWriteArrayList 쓸 때마다 전체 복사 → 읽기 압도적·쓰기 드묾 (리스너 목록 등)
• BlockingQueue — 생산자-소비자에 wait/notify 를 직접 쓰지 않게 해 준다

Collections.synchronizedMap 은 메서드마다 락을 걸 뿐이라

• 복합 연산(get 후 put)은 여전히 원자적이지 않다

fail-fast — 순회 중 변경

for (String s : list) { if (cond) list.remove(s); }   // ConcurrentModificationException

컬렉션은 구조 변경 횟수(modCount)를 센다 이터레이터는 자기가 만들어질 때의 값을 기억한다

• 다르면 즉시 예외를 던진다 (fail-fast)

"조용히 잘못 도는 것보다 즉시 터지는 게 낫다" 는 설계다

list.removeIf(cond);                       // ✅ 가장 간단
Iterator<String> it = list.iterator();     // ✅ 이터레이터의 remove 는 안전
while (it.hasNext()) if (cond) it.remove();

면접 함정

• ❌ "삽입/삭제가 많으면 LinkedList" → 실측하면 대개 ArrayList가 빠르다.
• ❌ "ConcurrentModificationException은 멀티스레드 문제" → 단일 스레드에서도 난다.