3. Java Collections 내부 구조

"ArrayList랑 LinkedList 뭐가 달라요?", "HashMap이 왜 빠른가요?", "ConcurrentHashMap은 왜 Thread-safe한가요?" — 이 세 가지가 면접에서 가장 자주 나오는 Collections 질문입니다. 사용법은 다 알지만 "내부에서 어떻게 동작하는지"를 묻는 거라서, 원리만 이해하면 쉽게 답할 수 있습니다.

1. ArrayList vs LinkedList — 면접 단골 질문

결론부터: 대부분의 상황에서 ArrayList가 더 빠릅니다. 왜인지 이해하려면 내부 구조를 보면 됩니다.

ArrayList — 내부는 그냥 배열

ArrayList는 이름에 List가 붙어 있지만 내부는 배열(Object[])입니다. 인덱스로 접근하는 건 배열 주소 계산 한 번이라 O(1)으로 매우 빠릅니다.

// [A, B, C, D, E] 에서 인덱스 1 위치에 "X" 삽입
list.add(1, "X");

// 내부에서 일어나는 일:
// B, C, D, E를 전부 오른쪽으로 한 칸씩 밀어야 함
// → 요소가 100만 개면 100만 번 이동
// → O(n) 작업

// [A, X, B, C, D, E]  ← 결과

LinkedList — 노드를 체인처럼 연결

LinkedList의 각 요소는 "값 + 앞 노드 주소 + 뒤 노드 주소"를 담은 노드입니다. 메모리에 흩어져 있고 체인처럼 연결됩니다.

// B와 C 사이에 "X" 삽입
// → B의 next를 X로, C의 prev를 X로 바꾸면 끝
// → 요소가 100만 개여도 포인터 2개만 바꿈
// → O(1) (단, 삽입할 위치를 이미 알고 있을 때)

// 문제는 "위치를 찾는 것"이 O(n)
// list.get(500_000) → 앞에서부터 50만 번 이동 → O(n)

2. HashMap — "왜 O(1)인가"

HashMap은 내부에 배열(버킷 배열)을 갖고 있습니다. put("key", value)를 하면 key로 해시값을 계산하고, 그 해시값으로 배열의 어떤 칸(버킷)에 넣을지 결정합니다. 나중에 get("key")를 하면 같은 방식으로 해시값 계산 → 배열 해당 칸 바로 접근 → O(1).

Resize — 배열이 꽉 차면 2배로 늘림

Resize는 모든 항목을 다시 배치하는 O(n) 작업입니다. 넣을 항목 수를 미리 알면 new HashMap<>(1000)처럼 초기 크기를 지정해서 Resize를 막을 수 있습니다.

3. HashMap이 Thread-safe하지 않은 이유 + ConcurrentHashMap

멀티스레드 환경에서 두 스레드가 동시에 같은 HashMap에 put하면 한쪽 데이터가 유실되거나, Resize 중에 무한루프가 걸릴 수 있습니다. 이를 해결하는 게 ConcurrentHashMap입니다.

4. 순서가 있는 Map — LinkedHashMap, TreeMap

// 내부: HashMap + 이중 연결 리스트
// 삽입한 순서대로 꺼낼 수 있음

Map<String, Integer> map =
    new LinkedHashMap<>();
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);

// 삽입 순서대로: C → A → B
map.forEach((k, v) ->
    System.out.println(k)); // C, A, B

// accessOrder=true: 최근 접근 순서 유지
// → LRU 캐시 구현에 활용

// 내부: Red-Black Tree
// 키가 항상 정렬된 순서로 유지됨
// get/put: O(log n)

Map<String, Integer> map = new TreeMap<>();
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);

// 알파벳 오름차순: A → B → C
map.forEach((k, v) ->
    System.out.println(k)); // A, B, C

// 범위 조회도 가능
map.subMap("A", "C"); // A이상 C미만
map.headMap("B");     // B 미만

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        // accessOrder=true → 접근할 때마다 해당 항목이 맨 뒤로 이동
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity; // 가득 차면 가장 오래된 항목 자동 제거
    }
}

// 사용
LRUCache<Long, Product> cache = new LRUCache<>(100);
cache.put(1L, product);
cache.get(1L); // 접근 → 이 항목이 "최근"으로 이동

// ⚠️ 멀티스레드 환경에서는 Caffeine Cache 사용 권장

5. 어떤 컬렉션을 언제 쓰나?

6. 면접 대비 핵심 Q&A