자료구조 & 알고리즘 면접 가이드: HashMap 내부 동작부터 정렬 알고리즘까지
자료구조 & 알고리즘 면접 가이드: HashMap 내부 동작부터 정렬 알고리즘까지
코딩 테스트가 끝나도 면접에서는 “HashMap의 시간복잡도가 O(1)인 이유를 설명해주세요”, “ArrayList와 LinkedList는 언제 쓰나요?” 같은 질문이 나온다. 코드를 외우는 것이 아니라 왜 그런 성능이 나오는지, 내부에서 어떤 일이 벌어지는지를 이해해야 답할 수 있다.
Java Collections Framework 글에서 List, Set, Map의 사용법을 다루었다. 이 글은 그 내부 구조와 알고리즘적 원리에 집중한다.
1. 시간 복잡도 (Big-O)
1.1 Big-O란
알고리즘의 성능을 입력 크기(n)가 커질 때 연산 횟수가 어떻게 증가하는지로 표현하는 표기법이다. 상수와 낮은 차수 항은 무시한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
┌────────────────────────────────────────────────────────────────────────┐
│ 시간 복잡도 비교 │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ n = 1,000일 때 대략적인 연산 횟수 │
│ │
│ O(1) → 1 (상수) │
│ O(log n) → 10 (로그) │
│ O(n) → 1,000 (선형) │
│ O(n log n) → 10,000 (선형 로그) │
│ O(n²) → 1,000,000 (이차) │
│ O(2ⁿ) → 우주가 멸망해도... (지수) │
│ │
│ 속도 순서: │
│ O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) │
│ │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ 면접 팁: "최악의 경우"를 물어볼 때가 많다 │ │
│ │ │ │
│ │ • 평균(Average): 일반적인 입력에서의 성능 │ │
│ │ • 최악(Worst): 가장 안 좋은 입력에서의 성능 │ │
│ │ • 최선(Best): 가장 좋은 입력에서의 성능 (잘 안 물어봄) │ │
│ │ │ │
│ │ 예: QuickSort │ │
│ │ 평균: O(n log n) — 대부분의 경우 │ │
│ │ 최악: O(n²) — 이미 정렬된 배열 + 첫 원소를 피벗으로 │ │
│ └─────────────────────────────────────────────────────────────┘ │
└────────────────────────────────────────────────────────────────────────┘
1.2 자주 나오는 시간 복잡도 패턴
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
┌────────────────────────────────────────────────────────────────────────┐
│ 코드 패턴별 시간 복잡도 │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ O(1) — 인덱스 접근, HashMap get/put │
│ int x = arr[5]; │
│ map.get("key"); │
│ │
│ O(log n) — 이진 탐색, 균형 트리 탐색 │
│ while (left <= right) { │
│ mid = (left + right) / 2; │
│ if (arr[mid] == target) return mid; │
│ // 매 반복마다 탐색 범위가 절반으로 줄어듦 │
│ } │
│ │
│ O(n) — 단일 반복문, 선형 탐색 │
│ for (int i = 0; i < n; i++) { ... } │
│ │
│ O(n log n) — 효율적 정렬 (Merge Sort, Quick Sort 평균) │
│ Arrays.sort(arr); // Java: Dual-Pivot QuickSort │
│ │
│ O(n²) — 이중 반복문, 버블/선택/삽입 정렬 │
│ for (int i = 0; i < n; i++) │
│ for (int j = 0; j < n; j++) { ... } │
│ │
│ O(2ⁿ) — 재귀적 피보나치 (메모이제이션 없이) │
│ fib(n) = fib(n-1) + fib(n-2) │
└────────────────────────────────────────────────────────────────────────┘
2. 배열 기반 자료구조
2.1 Array vs ArrayList vs LinkedList
면접에서 “ArrayList와 LinkedList의 차이”는 매우 자주 나온다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
┌────────────────────────────────────────────────────────────────────────┐
│ Array vs ArrayList vs LinkedList │
├───────────────┬───────────────────┬───────────────────┬────────────────┤
│ │ Array (배열) │ ArrayList │ LinkedList │
├───────────────┼───────────────────┼───────────────────┼────────────────┤
│ 크기 │ 고정 (생성 시 결정)│ 가변 (자동 확장) │ 가변 │
├───────────────┼───────────────────┼───────────────────┼────────────────┤
│ 메모리 구조 │ 연속 메모리 블록 │ 연속 메모리 블록 │ 노드가 흩어져 │
│ │ │ (내부 배열) │ 있음 (포인터) │
├───────────────┼───────────────────┼───────────────────┼────────────────┤
│ 인덱스 접근 │ O(1) │ O(1) │ O(n) │
│ get(i) │ │ │ 처음부터 순회 │
├───────────────┼───────────────────┼───────────────────┼────────────────┤
│ 맨 뒤 추가 │ 불가 (고정 크기) │ O(1) (amortized) │ O(1) │
│ add(e) │ │ 확장 시 O(n) 복사 │ │
├───────────────┼───────────────────┼───────────────────┼────────────────┤
│ 중간 삽입/삭제│ O(n) 시프트 │ O(n) 시프트 │ O(1) 연결 변경 │
│ add(i,e) │ │ │ (위치 찾기 O(n))│
├───────────────┼───────────────────┼───────────────────┼────────────────┤
│ 탐색 │ O(n) │ O(n) │ O(n) │
│ contains(e) │ │ │ │
├───────────────┼───────────────────┼───────────────────┼────────────────┤
│ 캐시 친화성 │ ✅ 좋음 │ ✅ 좋음 │ ❌ 나쁨 │
│ │ (연속 메모리) │ (연속 메모리) │ (노드 흩어짐) │
├───────────────┼───────────────────┼───────────────────┼────────────────┤
│ 메모리 사용 │ 최소 │ 약간의 여유 공간 │ 노드당 prev, │
│ │ │ (capacity > size) │ next 포인터 │
└───────────────┴───────────────────┴───────────────────┴────────────────┘
2.2 ArrayList의 동적 확장 (Amortized O(1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
┌────────────────────────────────────────────────────────────────────────┐
│ ArrayList 내부 동작 │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ 초기 capacity = 10 (기본값) │
│ │
│ add("A"): [A, _, _, _, _, _, _, _, _, _] size=1, capacity=10 │
│ add("B"): [A, B, _, _, _, _, _, _, _, _] size=2, capacity=10 │
│ ... │
│ add("J"): [A, B, C, D, E, F, G, H, I, J] size=10, capacity=10 │
│ │
│ add("K"): 공간 부족! → 새 배열(capacity = 10 × 1.5 = 15) 생성 │
│ → 기존 원소 10개 복사 (O(n)) │
│ → [A, B, C, D, E, F, G, H, I, J, K, _, _, _, _] │
│ size=11, capacity=15 │
│ │
│ 확장 규칙: newCapacity = oldCapacity + (oldCapacity >> 1) │
│ = oldCapacity × 1.5 │
│ │
│ 왜 Amortized O(1)인가? │
│ → 확장은 가끔만 발생 (n번 추가하면 확장은 log n번) │
│ → n번 추가의 총 비용: O(n) (확장 복사 합산) │
│ → 1번당 평균: O(n) / n = O(1) │
│ │
│ ⚠️ 대량 추가가 예상되면 초기 capacity 지정: │
│ List<String> list = new ArrayList<>(10000); │
│ → 확장 복사 횟수 감소 │
└────────────────────────────────────────────────────────────────────────┘
2.3 LinkedList의 구조
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
┌────────────────────────────────────────────────────────────────────────┐
│ Java LinkedList = Doubly Linked List (이중 연결 리스트) │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ head tail │
│ ↓ ↓ │
│ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
│ │ prev:null│ │ prev: ←──┼─────│ prev: ←──┼─────│ prev: ←──│ │
│ │ data: A │ │ data: B │ │ data: C │ │ data: D │ │
│ │ next: ──┼─────→│ next: ──┼─────→│ next: ──┼─────→│next:null │ │
│ └──────────┘ └──────────┘ └──────────┘ └──────────┘ │
│ │
│ get(2): head → A → B → C (3번 이동) → O(n) │
│ add(0, X): head 앞에 새 노드 연결 → O(1) │
│ add(2, X): head → A → B (위치 찾기 O(n)) + 연결 변경 O(1) → O(n) │
│ │
│ 실무에서의 선택: │
│ → 대부분의 경우 ArrayList가 유리 (캐시 친화성, 인덱스 접근) │
│ → LinkedList가 유리한 경우: 맨 앞/뒤 삽입 삭제가 빈번 (Deque 용도) │
│ → Java의 LinkedList는 List + Deque 인터페이스 모두 구현 │
└────────────────────────────────────────────────────────────────────────┘
3. 스택과 큐
3.1 스택 (Stack) — LIFO
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
┌────────────────────────────────────────────────────────────────────────┐
│ Stack (LIFO: Last In, First Out) │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ push(A) → push(B) → push(C) pop() → C, pop() → B │
│ │
│ ┌───┐ │
│ │ C │ ← top (가장 나중에 들어온 것이 먼저 나옴) │
│ ├───┤ │
│ │ B │ │
│ ├───┤ │
│ │ A │ │
│ └───┘ │
│ │
│ push(): O(1) │
│ pop(): O(1) │
│ peek(): O(1) (제거하지 않고 top 확인) │
│ │
│ Java 구현: │
│ Deque<Integer> stack = new ArrayDeque<>(); // Stack 클래스 대신 권장 │
│ stack.push(1); │
│ stack.pop(); │
│ │
│ ⚠️ java.util.Stack은 Vector 기반 → synchronized → 느림 │
│ → ArrayDeque를 스택으로 사용하는 것이 권장됨 │
│ │
│ 활용: │
│ • 함수 호출 스택 (재귀) │
│ • 괄호 매칭 (유효성 검사) │
│ • 뒤로 가기 (브라우저, Undo) │
│ • DFS 구현 │
│ • 후위 표기법 계산 │
└────────────────────────────────────────────────────────────────────────┘
3.2 큐 (Queue) — FIFO
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
┌────────────────────────────────────────────────────────────────────────┐
│ Queue (FIFO: First In, First Out) │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ offer(A) → offer(B) → offer(C) poll() → A, poll() → B │
│ │
│ front rear │
│ ↓ ↓ │
│ ┌───┬───┬───┐ │
│ │ A │ B │ C │ → 먼저 들어온 것이 먼저 나옴 │
│ └───┴───┴───┘ │
│ │
│ offer()/add(): O(1) — 뒤에 추가 │
│ poll()/remove(): O(1) — 앞에서 제거 │
│ peek(): O(1) — 앞 확인 │
│ │
│ Java 구현: │
│ Queue<Integer> queue = new LinkedList<>(); │
│ Queue<Integer> queue = new ArrayDeque<>(); // 더 빠름 (권장) │
│ │
│ 활용: │
│ • BFS 구현 │
│ • 작업 스케줄링 (프린터 큐, CPU 스케줄링) │
│ • 메시지 큐 (Kafka, RabbitMQ의 기본 개념) │
│ • 버퍼 (생산자-소비자 패턴) │
│ │
│ ■ PriorityQueue (우선순위 큐) │
│ → 내부적으로 힙(Heap) 구조 │
│ → 삽입/삭제: O(log n), peek: O(1) │
│ → 항상 가장 작은(또는 큰) 원소가 먼저 나옴 │
│ │
│ PriorityQueue<Integer> pq = new PriorityQueue<>(); // 최소 힙 │
│ pq.offer(3); pq.offer(1); pq.offer(2); │
│ pq.poll(); // → 1 (가장 작은 값) │
└────────────────────────────────────────────────────────────────────────┘
4. HashMap 내부 동작 (면접 단골)
4.1 해시 테이블의 원리
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
┌────────────────────────────────────────────────────────────────────────┐
│ Hash Table 기본 구조 │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ key → hashCode() → hash값 → bucket index → value 저장 │
│ │
│ 예: put("name", "김철수") │
│ "name".hashCode() = 3373707 → 3373707 % 16 = 11 → bucket[11] │
│ │
│ bucket (배열) │
│ ┌────────────────────────────────────────────────────┐ │
│ │ [0] → null │ │
│ │ [1] → null │ │
│ │ [2] → (key="age", value=25) │ │
│ │ [3] → null │ │
│ │ ... │ │
│ │ [11] → (key="name", value="김철수") │ │
│ │ ... │ │
│ │ [15] → null │ │
│ └────────────────────────────────────────────────────┘ │
│ │
│ get("name"): │
│ "name".hashCode() → 3373707 % 16 = 11 → bucket[11] → "김철수" │
│ → 배열 인덱스 접근이므로 O(1) │
│ │
│ 핵심: 해시 함수가 key를 배열 인덱스로 변환하여 │
│ 탐색 없이 바로 접근하므로 O(1) │
└────────────────────────────────────────────────────────────────────────┘
4.2 해시 충돌 (Hash Collision)
서로 다른 키가 같은 bucket 인덱스로 매핑되는 것이다. “HashMap의 시간복잡도가 O(1)인 이유와 O(n)이 될 수 있는 경우”는 면접에서 매우 자주 나온다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
┌────────────────────────────────────────────────────────────────────────┐
│ 해시 충돌과 해결 방법 │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ 충돌 예시: │
│ "Aa".hashCode() = 2112 │
│ "BB".hashCode() = 2112 ← 같은 해시값! │
│ → 같은 bucket에 들어감 │
│ │
│ ■ 해결 1: Separate Chaining (체이닝) — Java HashMap 방식 │
│ │
│ bucket[5] → [Aa:1] → [BB:2] → [Cc:3] (연결 리스트) │
│ │
│ get("BB"): │
│ bucket[5] → "Aa"와 equals() 비교 → 불일치 │
│ → "BB"와 equals() 비교 → 일치! → 값 반환 │
│ │
│ → 최악의 경우(모든 키가 같은 bucket): O(n) │
│ → 이래서 hashCode()와 equals()를 함께 오버라이드해야 하는 것! │
│ │
│ ■ 해결 2: Open Addressing (개방 주소법) │
│ │
│ 충돌 시 다른 빈 bucket을 찾아서 저장 │
│ • Linear Probing: 충돌 → index+1, index+2, ... 순서로 탐색 │
│ • Quadratic Probing: 충돌 → index+1², index+2², ... 으로 탐색 │
│ • Double Hashing: 두 번째 해시 함수로 건너뛸 간격 결정 │
│ │
│ Java HashMap은 Separate Chaining 사용 │
│ Python dict는 Open Addressing 사용 │
└────────────────────────────────────────────────────────────────────────┘
4.3 Java HashMap의 진화 — 연결 리스트 → 레드블랙 트리
Java 8부터 하나의 bucket에 노드가 많아지면 연결 리스트를 레드블랙 트리로 변환한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
┌────────────────────────────────────────────────────────────────────────┐
│ Java 8+ HashMap 내부 구조 변화 │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ bucket에 노드 수 ≤ 8개: 연결 리스트 (Linked List) │
│ bucket[5] → [A] → [B] → [C] → ... → [H] │
│ 탐색: O(n) — 순차 비교 │
│ │
│ bucket에 노드 수 > 8개: 레드블랙 트리 (Red-Black Tree)로 변환 │
│ bucket[5] → [D] │
│ / \ │
│ [B] [F] │
│ / \ / \ │
│ [A] [C] [E] [G] │
│ \ │
│ [H] │
│ 탐색: O(log n) — 이진 탐색 │
│ │
│ 역변환: 노드 수 ≤ 6개가 되면 다시 연결 리스트로 │
│ → 8/6 히스테리시스로 빈번한 변환 방지 │
│ │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ 왜 8개? │ │
│ │ 해시가 잘 분산되면 한 bucket에 8개 이상 쌓일 확률은 │ │
│ │ 약 0.00000006 (600만분의 1) │ │
│ │ → 거의 발생 안 하지만, 발생 시 성능 보장을 위해 │ │
│ │ → O(n) → O(log n)으로 개선 (worst case 방어) │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │
│ 정리: │
│ HashMap 시간복잡도 = O(1) (평균) │
│ = O(log n) (최악, Java 8+) │
│ = O(n) (최악, Java 7 이하) │
└────────────────────────────────────────────────────────────────────────┘
4.4 HashMap의 리사이징 (Rehashing)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
┌────────────────────────────────────────────────────────────────────────┐
│ HashMap 리사이징 │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ 초기 capacity = 16, load factor = 0.75 (기본값) │
│ → 16 × 0.75 = 12개 원소가 들어가면 리사이징 발생 │
│ │
│ 리사이징 과정: │
│ ① 새 배열 생성 (capacity × 2 = 32) │
│ ② 모든 원소를 새 배열에 재배치 (rehash) │
│ → hash % 32 (기존 hash % 16과 다를 수 있음) │
│ ③ 기존 배열 해제 │
│ │
│ 비용: O(n) — 모든 원소를 재배치 │
│ → ArrayList와 마찬가지로 Amortized O(1) │
│ │
│ ⚠️ 대량 삽입이 예상되면 초기 capacity 지정: │
│ Map<String, Object> map = new HashMap<>(1000); │
│ → 리사이징 횟수 감소, 성능 향상 │
│ │
│ load factor를 낮추면? │
│ → 충돌 확률 감소 → 탐색 빨라짐 │
│ → 메모리 사용 증가 (빈 bucket이 많아짐) │
│ → 0.75가 시간/공간 트레이드오프의 최적값 │
└────────────────────────────────────────────────────────────────────────┘
4.5 hashCode()와 equals() 계약
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
┌────────────────────────────────────────────────────────────────────────┐
│ hashCode()와 equals()의 관계 — 면접 필수 │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ 규칙 (Java 명세): │
│ ① equals()가 true면 hashCode()도 같아야 한다 │
│ a.equals(b) == true → a.hashCode() == b.hashCode() │
│ │
│ ② hashCode()가 같아도 equals()는 다를 수 있다 (충돌) │
│ a.hashCode() == b.hashCode() ↛ a.equals(b) == true │
│ │
│ ③ equals()를 오버라이드하면 hashCode()도 반드시 오버라이드 │
│ │
│ ■ 위반 시 문제: │
│ class User { │
│ String name; │
│ // equals()만 오버라이드, hashCode() 미구현 │
│ } │
│ │
│ User a = new User("김철수"); │
│ User b = new User("김철수"); │
│ a.equals(b); // true (이름이 같으므로) │
│ │
│ map.put(a, "값"); │
│ map.get(b); // null! ← 찾지 못함! │
│ │
│ 이유: │
│ a.hashCode() = 1234 → bucket[1234 % 16] = bucket[2]에 저장 │
│ b.hashCode() = 5678 → bucket[5678 % 16] = bucket[6]에서 찾음 │
│ → 다른 bucket을 탐색하므로 찾지 못함 │
│ │
│ ■ 올바른 구현: │
│ @Override │
│ public int hashCode() { │
│ return Objects.hash(name); // equals에 사용한 필드로 계산 │
│ } │
└────────────────────────────────────────────────────────────────────────┘
4.6 HashMap vs HashTable vs ConcurrentHashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
┌────────────────────────────────────────────────────────────────────────┐
│ HashMap vs HashTable vs ConcurrentHashMap │
├───────────────┬──────────────┬───────────────┬─────────────────────────┤
│ │ HashMap │ HashTable │ ConcurrentHashMap │
├───────────────┼──────────────┼───────────────┼─────────────────────────┤
│ 동기화 │ ✗ │ ✓ (전체 락) │ ✓ (세그먼트/버킷 락) │
├───────────────┼──────────────┼───────────────┼─────────────────────────┤
│ null 허용 │ key: 1개 │ key: ✗ │ key: ✗ │
│ │ value: 다수 │ value: ✗ │ value: ✗ │
├───────────────┼──────────────┼───────────────┼─────────────────────────┤
│ 성능 │ 가장 빠름 │ 느림 │ 멀티스레드에서 빠름 │
│ │ (단일 스레드)│ (전체 락) │ (세밀한 락) │
├───────────────┼──────────────┼───────────────┼─────────────────────────┤
│ 사용 시기 │ 단일 스레드 │ 레거시 │ 멀티스레드 환경 │
│ │ (대부분) │ (사용 금지) │ (실무 표준) │
├───────────────┼──────────────┼───────────────┼─────────────────────────┤
│ Java 버전 │ 1.2+ │ 1.0+ │ 1.5+ │
└───────────────┴──────────────┴───────────────┴─────────────────────────┘
ConcurrentHashMap (Java 8+):
→ 버킷 단위 락 (synchronized + CAS)
→ 읽기: 락 없이 (volatile 보장)
→ 쓰기: 해당 버킷만 락 → 다른 버킷은 동시 접근 가능
→ HashTable처럼 전체 Map을 잠그지 않으므로 훨씬 빠름
5. 트리 자료구조
5.1 이진 트리와 이진 탐색 트리 (BST)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
┌────────────────────────────────────────────────────────────────────────┐
│ 이진 탐색 트리 (Binary Search Tree) │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ 규칙: 왼쪽 자식 < 부모 < 오른쪽 자식 │
│ │
│ 8 │
│ / \ │
│ 3 10 │
│ / \ \ │
│ 1 6 14 │
│ / \ / │
│ 4 7 13 │
│ │
│ 탐색 예: find(6) │
│ 8 → 6 < 8, 왼쪽 → 3 → 6 > 3, 오른쪽 → 6 → 찾음! │
│ → 3번 비교 (매번 절반 제거 → O(log n)) │
│ │
│ 시간 복잡도: │
│ ┌──────────────────────────────────────────────┐ │
│ │ 평균 최악 (편향 트리) │ │
│ │ 탐색 O(log n) O(n) │ │
│ │ 삽입 O(log n) O(n) │ │
│ │ 삭제 O(log n) O(n) │ │
│ └──────────────────────────────────────────────┘ │
│ │
│ 최악이 O(n)인 이유 — 편향 트리: │
│ 1 → 2 → 3 → 4 → 5 (정렬된 순서로 삽입) │
│ → 한쪽으로만 뻗어서 사실상 연결 리스트 │
│ → 이를 해결하기 위해 "균형 트리" 사용 │
└────────────────────────────────────────────────────────────────────────┘
5.2 레드블랙 트리 (Red-Black Tree)
Java의 TreeMap, TreeSet, HashMap(충돌 시)이 내부적으로 사용하는 자가 균형 이진 탐색 트리다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
┌────────────────────────────────────────────────────────────────────────┐
│ 레드블랙 트리 │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ BST의 편향 문제를 해결하기 위한 규칙: │
│ ① 모든 노드는 Red 또는 Black │
│ ② 루트는 항상 Black │
│ ③ Red 노드의 자식은 모두 Black (Red-Red 금지) │
│ ④ 루트에서 모든 리프까지의 Black 노드 수가 같다 │
│ ⑤ 리프(NIL)는 Black │
│ │
│ 8(B) │
│ / \ │
│ 3(R) 10(B) │
│ / \ \ │
│ 1(B) 6(B) 14(R) │
│ / \ / │
│ 4(R) 7(R) 13(B) │
│ │
│ 삽입/삭제 시 규칙이 깨지면: │
│ → 색상 변경 (Recoloring) + 회전 (Rotation)으로 균형 유지 │
│ → 높이가 항상 O(log n) 이하로 유지됨 │
│ → 최악에도 O(log n) 보장 (BST의 O(n)과 차이) │
│ │
│ Java에서의 사용: │
│ • TreeMap — 키가 정렬된 Map (Red-Black Tree) │
│ • TreeSet — 정렬된 Set (내부적으로 TreeMap 사용) │
│ • HashMap — bucket에 8개 이상 충돌 시 Red-Black Tree 변환 │
│ │
│ 면접에서는 내부 구현을 상세히 물어보진 않지만, │
│ "왜 O(log n)이 보장되는지" = "자가 균형 트리이기 때문" 정도는 필수 │
└────────────────────────────────────────────────────────────────────────┘
5.3 힙 (Heap)과 PriorityQueue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
┌────────────────────────────────────────────────────────────────────────┐
│ 힙 (Heap) — 최솟값/최댓값을 O(1)로 접근 │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ ■ 최소 힙 (Min-Heap): 부모 ≤ 자식 │
│ │
│ 1 │
│ / \ │
│ 3 2 │
│ / \ / │
│ 7 4 5 │
│ │
│ → 루트가 항상 최솟값 → peek() = O(1) │
│ │
│ ■ 삽입 (offer): O(log n) │
│ ① 맨 마지막에 추가 │
│ ② 부모와 비교, 부모보다 작으면 교환 (위로 올라감) │
│ → "Bubble Up" (최대 트리 높이만큼 = log n) │
│ │
│ ■ 삭제 (poll): O(log n) │
│ ① 루트 제거 (최솟값) │
│ ② 마지막 원소를 루트로 이동 │
│ ③ 자식과 비교, 자식보다 크면 교환 (아래로 내려감) │
│ → "Bubble Down" (최대 log n) │
│ │
│ ■ 배열로 구현 (완전 이진 트리 특성 이용) │
│ 인덱스 i의 부모: (i - 1) / 2 │
│ 인덱스 i의 왼쪽 자식: 2i + 1 │
│ 인덱스 i의 오른쪽 자식: 2i + 2 │
│ │
│ [1, 3, 2, 7, 4, 5] ← 위 트리의 배열 표현 │
│ │
│ Java PriorityQueue = 최소 힙 │
│ 최대 힙: new PriorityQueue<>(Comparator.reverseOrder()) │
└────────────────────────────────────────────────────────────────────────┘
6. 그래프 탐색 — BFS와 DFS
6.1 BFS vs DFS 비교
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
┌────────────────────────────────────────────────────────────────────────┐
│ BFS vs DFS │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ 그래프: │
│ 1 │
│ / \ │
│ 2 3 │
│ / \ \ │
│ 4 5 6 │
│ │
│ ■ BFS (Breadth-First Search, 너비 우선) │
│ 탐색 순서: 1 → 2 → 3 → 4 → 5 → 6 │
│ → 가까운 노드부터 (레벨 순서) │
│ → 큐(Queue) 사용 │
│ → 최단 경로 보장 (가중치 없는 그래프) │
│ │
│ ■ DFS (Depth-First Search, 깊이 우선) │
│ 탐색 순서: 1 → 2 → 4 → 5 → 3 → 6 │
│ → 깊이 끝까지 가고 돌아옴 (백트래킹) │
│ → 스택(Stack) 또는 재귀 사용 │
│ → 경로 탐색, 사이클 감지에 유용 │
│ │
│ ┌───────────────┬──────────────────┬──────────────────────┐ │
│ │ │ BFS │ DFS │ │
│ ├───────────────┼──────────────────┼──────────────────────┤ │
│ │ 자료구조 │ Queue │ Stack / 재귀 │ │
│ ├───────────────┼──────────────────┼──────────────────────┤ │
│ │ 시간 복잡도 │ O(V + E) │ O(V + E) │ │
│ ├───────────────┼──────────────────┼──────────────────────┤ │
│ │ 공간 복잡도 │ O(V) (큐) │ O(V) (스택/콜스택) │ │
│ ├───────────────┼──────────────────┼──────────────────────┤ │
│ │ 최단 경로 │ ✅ 보장 │ ✗ 보장 안 됨 │ │
│ ├───────────────┼──────────────────┼──────────────────────┤ │
│ │ 사용 사례 │ 최단 경로, 레벨 │ 순열/조합, 미로 탐색 │ │
│ │ │ 순회, 가까운 노드│ 사이클 감지, 위상 정렬│ │
│ └───────────────┴──────────────────┴──────────────────────┘ │
└────────────────────────────────────────────────────────────────────────┘
6.2 구현 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// BFS — 큐 사용
public void bfs(Map<Integer, List<Integer>> graph, int start) {
Queue<Integer> queue = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : graph.getOrDefault(node, List.of())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
}
}
}
// DFS — 재귀 사용
public void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) {
visited.add(node);
System.out.print(node + " ");
for (int neighbor : graph.getOrDefault(node, List.of())) {
if (!visited.contains(neighbor)) {
dfs(graph, neighbor, visited);
}
}
}
7. 정렬 알고리즘
7.1 정렬 알고리즘 비교
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
┌────────────────────────────────────────────────────────────────────────┐
│ 정렬 알고리즘 비교 │
├──────────────┬──────────┬──────────┬──────────┬───────┬───────────────┤
│ │ 평균 │ 최악 │ 공간 │ 안정 │ 특징 │
├──────────────┼──────────┼──────────┼──────────┼───────┼───────────────┤
│ Bubble Sort │ O(n²) │ O(n²) │ O(1) │ ✅ │ 가장 단순 │
├──────────────┼──────────┼──────────┼──────────┼───────┼───────────────┤
│ Selection │ O(n²) │ O(n²) │ O(1) │ ✗ │ 교환 횟수 최소│
├──────────────┼──────────┼──────────┼──────────┼───────┼───────────────┤
│ Insertion │ O(n²) │ O(n²) │ O(1) │ ✅ │ 거의 정렬 시 │
│ │ │ │ │ │ O(n)으로 빠름 │
├──────────────┼──────────┼──────────┼──────────┼───────┼───────────────┤
│ Merge Sort │ O(n logn)│ O(n logn)│ O(n) │ ✅ │ 항상 O(n logn)│
├──────────────┼──────────┼──────────┼──────────┼───────┼───────────────┤
│ Quick Sort │ O(n logn)│ O(n²) │ O(logn) │ ✗ │ 실전 최고 속도│
├──────────────┼──────────┼──────────┼──────────┼───────┼───────────────┤
│ Heap Sort │ O(n logn)│ O(n logn)│ O(1) │ ✗ │ 추가 메모리 X │
├──────────────┼──────────┼──────────┼──────────┼───────┼───────────────┤
│ Tim Sort │ O(n logn)│ O(n logn)│ O(n) │ ✅ │ Java 기본 │
│ (Merge+Insert│ │ │ │ │ Arrays.sort() │
│ 혼합) │ │ │ │ │ 실데이터 최적 │
└──────────────┴──────────┴──────────┴──────────┴───────┴───────────────┘
안정(Stable) 정렬: 같은 값의 원소가 원래 순서를 유지
→ (3,A) (1,B) (3,C) 정렬 시 → (1,B) (3,A) (3,C) ← A가 C 앞 유지
7.2 핵심 알고리즘 원리
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
┌────────────────────────────────────────────────────────────────────────┐
│ Quick Sort — 면접에서 가장 자주 물어보는 정렬 │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ 원리: 분할 정복 (Divide and Conquer) │
│ │
│ ① 피벗(pivot) 선택 │
│ ② 피벗보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 분할 (Partition) │
│ ③ 왼쪽과 오른쪽을 각각 재귀적으로 정렬 │
│ │
│ 예시: [5, 3, 8, 1, 9, 2, 7] 피벗 = 5 │
│ │
│ Partition: │
│ [3, 1, 2] 5 [8, 9, 7] │
│ ← 작은 것 ↑ 큰 것 → │
│ 피벗 │
│ │
│ 재귀: │
│ [3, 1, 2] → 피벗=3 → [1, 2] 3 → [1, 2] → 피벗=1 → 1 [2] │
│ [8, 9, 7] → 피벗=8 → [7] 8 [9] │
│ │
│ 결과: [1, 2, 3, 5, 7, 8, 9] │
│ │
│ 왜 평균 O(n log n)? │
│ → 매번 절반으로 분할되면 log n 레벨 │
│ → 각 레벨에서 n개 원소를 한 번씩 비교 │
│ → n × log n │
│ │
│ 왜 최악 O(n²)? │
│ → 이미 정렬된 배열에서 첫 원소를 피벗으로 선택 │
│ → 분할이 1:n-1로 됨 → n 레벨 → n × n │
│ → 해결: 랜덤 피벗, 3-median 피벗 선택 │
│ │
│ 왜 실전에서 가장 빠른가? │
│ → In-place (추가 메모리 O(log n) — 스택만) │
│ → 캐시 친화적 (연속 메모리 접근) │
│ → Merge Sort는 O(n) 추가 메모리 필요 │
└────────────────────────────────────────────────────────────────────────┘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
┌────────────────────────────────────────────────────────────────────────┐
│ Merge Sort — 항상 O(n log n) 보장 │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ 원리: 분할 → 정복 → 병합 │
│ │
│ [5, 3, 8, 1, 9, 2, 7, 4] │
│ / \ │
│ [5, 3, 8, 1] [9, 2, 7, 4] │
│ / \ / \ │
│ [5,3] [8,1] [9,2] [7,4] │
│ / \ / \ / \ / \ │
│ [5][3] [8][1] [9][2] [7][4] │
│ \ / \ / \ / \ / │
│ [3,5] [1,8] [2,9] [4,7] ← 정렬하며 병합 │
│ \ / \ / │
│ [1,3,5,8] [2,4,7,9] │
│ \ / │
│ [1,2,3,4,5,7,8,9] │
│ │
│ 항상 절반으로 분할 → 최악에도 O(n log n) │
│ 단점: O(n) 추가 메모리 (병합 시 임시 배열 필요) │
│ 장점: 안정 정렬, LinkedList 정렬에 적합 │
└────────────────────────────────────────────────────────────────────────┘
7.3 Java의 정렬 — Arrays.sort()와 Collections.sort()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
┌────────────────────────────────────────────────────────────────────────┐
│ Java 내부 정렬 알고리즘 │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ ■ Arrays.sort(int[]) — 기본 타입 배열 │
│ → Dual-Pivot QuickSort (Java 7+) │
│ → 안정 정렬이 아니지만, 기본 타입은 값이 같으면 구분 불필요 │
│ │
│ ■ Arrays.sort(Object[]) — 객체 배열 │
│ → TimSort (Java 7+) │
│ → Merge Sort + Insertion Sort 혼합 │
│ → 안정 정렬 보장 (같은 값의 순서 유지) │
│ │
│ ■ Collections.sort(List) — 리스트 정렬 │
│ → 내부적으로 list.toArray() → Arrays.sort(Object[]) → 복사 │
│ → 즉, TimSort 사용 │
│ │
│ ■ TimSort란? │
│ → 실제 데이터는 부분적으로 정렬되어 있는 경우가 많다는 관찰에서 출발│
│ → "Run" (이미 정렬된 부분 수열)을 찾아서 Merge │
│ → 짧은 Run은 Insertion Sort로 확장 (작은 배열에 빠름) │
│ → 최선: O(n) (이미 정렬된 경우) │
│ → 평균/최악: O(n log n) │
│ → Python, Java, Android, Swift 등 대부분의 언어가 채택 │
└────────────────────────────────────────────────────────────────────────┘
8. 이진 탐색 (Binary Search)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
┌────────────────────────────────────────────────────────────────────────┐
│ 이진 탐색 — O(log n) 탐색의 대표 │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ 전제: 배열이 정렬되어 있어야 한다 │
│ │
│ 예시: [1, 3, 5, 7, 9, 11, 13, 15] 에서 9를 찾기 │
│ │
│ 1단계: left=0, right=7, mid=3 → arr[3]=7 │
│ 9 > 7 → left = mid+1 = 4 │
│ │
│ 2단계: left=4, right=7, mid=5 → arr[5]=11 │
│ 9 < 11 → right = mid-1 = 4 │
│ │
│ 3단계: left=4, right=4, mid=4 → arr[4]=9 │
│ 9 == 9 → 찾음! 인덱스 4 │
│ │
│ 8개 원소에서 3번 비교로 찾음 (log₂8 = 3) │
│ │
│ 1,000,000개 원소 → 최대 20번 비교 (log₂1,000,000 ≈ 20) │
└────────────────────────────────────────────────────────────────────────┘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 기본 이진 탐색
public int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 오버플로우 방지
// (left + right) / 2 는 left + right가 int 범위를 넘을 수 있음
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1; // 찾지 못함
}
// Java 내장: Arrays.binarySearch(arr, target)
// → 정렬된 배열에서 사용, 없으면 -(삽입 위치) - 1 반환
9. Java Collections 시간 복잡도 요약
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
┌────────────────────────────────────────────────────────────────────────┐
│ Java 주요 컬렉션 시간 복잡도 정리 │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ ■ List │
│ ┌───────────────┬──────────┬──────────┬──────────┬──────────┐ │
│ │ │ get(i) │ add(끝) │ add(중간)│ contains │ │
│ ├───────────────┼──────────┼──────────┼──────────┼──────────┤ │
│ │ ArrayList │ O(1) │ O(1)* │ O(n) │ O(n) │ │
│ │ LinkedList │ O(n) │ O(1) │ O(n)† │ O(n) │ │
│ └───────────────┴──────────┴──────────┴──────────┴──────────┘ │
│ * amortized † 위치 찾기 O(n) + 연결 변경 O(1) │
│ │
│ ■ Set │
│ ┌───────────────┬──────────┬──────────┬──────────┐ │
│ │ │ add │ remove │ contains │ │
│ ├───────────────┼──────────┼──────────┼──────────┤ │
│ │ HashSet │ O(1) │ O(1) │ O(1) │ │
│ │ LinkedHashSet │ O(1) │ O(1) │ O(1) │ + 삽입순서 유지 │
│ │ TreeSet │ O(log n) │ O(log n) │ O(log n) │ + 정렬 유지 │
│ └───────────────┴──────────┴──────────┴──────────┘ │
│ │
│ ■ Map │
│ ┌───────────────┬──────────┬──────────┬──────────┐ │
│ │ │ put │ get │ remove │ │
│ ├───────────────┼──────────┼──────────┼──────────┤ │
│ │ HashMap │ O(1) │ O(1) │ O(1) │ │
│ │ LinkedHashMap │ O(1) │ O(1) │ O(1) │ + 순서 유지 │
│ │ TreeMap │ O(log n) │ O(log n) │ O(log n) │ + 키 정렬 │
│ │ ConcurrentHM │ O(1) │ O(1) │ O(1) │ + 스레드 안전 │
│ └───────────────┴──────────┴──────────┴──────────┘ │
│ │
│ ■ Queue │
│ ┌───────────────┬──────────┬──────────┬──────────┐ │
│ │ │ offer │ poll │ peek │ │
│ ├───────────────┼──────────┼──────────┼──────────┤ │
│ │ ArrayDeque │ O(1) │ O(1) │ O(1) │ │
│ │ PriorityQueue │ O(log n) │ O(log n) │ O(1) │ │
│ └───────────────┴──────────┴──────────┴──────────┘ │
└────────────────────────────────────────────────────────────────────────┘
10. 면접 질문 & 답변
Q1. HashMap의 시간복잡도가 O(1)인 이유를 설명해주세요. O(1)이 아닌 경우는?
HashMap은 키의 hashCode()를 배열 인덱스로 변환하여, 배열의 인덱스 접근(O(1))으로 값을 찾습니다. hash(key) % capacity로 bucket 위치를 계산하고, 해당 bucket에서 값을 가져옵니다.
하지만 서로 다른 키가 같은 bucket에 매핑되는 해시 충돌이 발생하면 O(1)이 아닙니다. Java 7까지는 충돌 시 연결 리스트로 저장하여 최악 O(n)이었지만, Java 8부터는 하나의 bucket에 8개 이상 쌓이면 레드블랙 트리로 변환하여 최악에도 O(log n)을 보장합니다.
그래서 hashCode()가 잘 분산되도록 구현하는 것이 중요하고, equals()를 오버라이드하면 hashCode()도 반드시 함께 오버라이드해야 합니다.
Q2. ArrayList와 LinkedList는 각각 언제 사용하나요?
ArrayList는 인덱스 기반 접근이 O(1)이고 메모리가 연속적이어서 CPU 캐시 친화적입니다. 대부분의 경우 ArrayList가 유리하며, 특히 조회가 많고 중간 삽입/삭제가 적은 경우에 적합합니다.
LinkedList는 노드가 힙에 흩어져 있어 캐시 효율이 낮고 인덱스 접근이 O(n)이지만, 맨 앞/뒤 삽입/삭제가 O(1)입니다. Deque(양방향 큐)으로 사용할 때 유리합니다.
실무에서는 거의 항상 ArrayList를 사용합니다. LinkedList가 이론적으로 중간 삽입이 O(1)이라고 하지만, 위치를 찾는 데 O(n)이 걸리므로 실질적으로 O(n)이고, 캐시 미스까지 고려하면 ArrayList의 시프트가 더 빠른 경우가 대부분입니다.
Q3. Quick Sort와 Merge Sort의 차이를 설명해주세요.
둘 다 분할 정복 기반의 O(n log n) 정렬입니다.
Quick Sort는 피벗을 기준으로 작은 것/큰 것을 분할하고 각각 재귀 정렬합니다. In-place로 동작하여 추가 메모리가 O(log n)(스택)이고, 연속 메모리 접근으로 캐시 효율이 좋아 실전에서 가장 빠릅니다. 단, 피벗 선택이 나쁘면 최악 O(n²)이 될 수 있습니다.
Merge Sort는 배열을 절반으로 나누고 각각 정렬한 뒤 병합합니다. 항상 절반 분할이므로 최악에도 O(n log n)을 보장하고, 안정 정렬입니다. 대신 O(n) 추가 메모리가 필요합니다.
Java는 기본 타입 배열(int[])에 Dual-Pivot QuickSort를, 객체 배열(Object[])에 TimSort(Merge + Insertion 혼합)를 사용합니다. 객체는 안정 정렬이 필요하기 때문입니다.
Q4. hashCode()와 equals()는 왜 함께 오버라이드해야 하나요?
HashMap/HashSet은 hashCode()로 bucket 위치를 결정하고, 같은 bucket 안에서 equals()로 동일 키를 구분합니다.
equals()만 오버라이드하고 hashCode()를 안 하면, 논리적으로 같은 객체가 다른 bucket에 들어갑니다. 예를 들어 new User("김철수")로 put하고 다른 new User("김철수")로 get하면, hashCode가 다르므로 다른 bucket을 탐색하여 null을 반환합니다.
규칙은 equals()가 true이면 hashCode()도 반드시 같아야 한다는 것입니다. 역은 성립하지 않아도 됩니다(해시 충돌 허용). equals()에 사용하는 필드로 Objects.hash()를 호출하면 됩니다.
Q5. 스택과 큐의 차이, 각각 어디에 사용하나요?
스택(LIFO)은 마지막에 넣은 것이 먼저 나옵니다. 함수 호출 스택(재귀), 괄호 매칭, 브라우저 뒤로 가기, DFS 구현에 사용합니다. Java에서는 java.util.Stack 대신 ArrayDeque를 스택으로 사용하는 것이 권장됩니다. Stack 클래스는 Vector 기반이라 모든 메서드가 synchronized되어 불필요하게 느립니다.
큐(FIFO)는 먼저 넣은 것이 먼저 나옵니다. BFS 구현, 작업 스케줄링, 생산자-소비자 패턴, 메시지 큐에 사용합니다. PriorityQueue는 힙 기반으로 삽입/삭제 O(log n)이며, 항상 최솟값(또는 최댓값)이 먼저 나옵니다.
Q6. 이진 탐색의 전제 조건과 시간 복잡도를 설명해주세요.
이진 탐색은 정렬된 배열에서만 사용할 수 있습니다. 중간값과 비교하여 탐색 범위를 절반으로 줄여가므로 O(log n)입니다. n=1,000,000이어도 최대 20번의 비교로 찾을 수 있습니다.
주의할 점으로 (left + right) / 2는 left + right가 int 범위를 초과할 수 있어, left + (right - left) / 2로 계산해야 오버플로우를 방지할 수 있습니다. Java에서는 Arrays.binarySearch()로 사용할 수 있으며, 찾지 못하면 -(삽입 위치) - 1을 반환합니다.
Q7. Java에서 ConcurrentHashMap이 HashTable보다 나은 이유는?
HashTable은 모든 메서드에 synchronized가 걸려 있어 전체 Map에 하나의 락만 존재합니다. 스레드 하나가 put하면 다른 모든 스레드는 get조차 할 수 없습니다.
ConcurrentHashMap(Java 8+)은 버킷 단위로 세밀한 락을 사용합니다. 읽기(get)는 volatile로 락 없이 수행하고, 쓰기(put)는 해당 버킷만 synchronized + CAS로 잠급니다. 다른 버킷은 동시에 접근할 수 있으므로 멀티스레드 환경에서 압도적으로 빠릅니다. 또한 null 키/값을 허용하지 않아 NullPointerException 가능성을 줄입니다.
정리
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
┌────────────────────────────────────────────────────────────────────────┐
│ 핵심 요약 │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ 1. HashMap = 배열 + 해시 함수 → O(1) 평균 │
│ 충돌 시: 연결 리스트(≤8) → 레드블랙 트리(>8) → O(log n) 최악 │
│ hashCode()와 equals()는 반드시 함께 오버라이드 │
│ │
│ 2. ArrayList vs LinkedList → 대부분 ArrayList 승 │
│ 캐시 친화성 + O(1) 인덱스 접근이 실전에서 결정적 │
│ │
│ 3. Quick Sort: 평균 O(n log n), 실전 최고 속도, 불안정 │
│ Merge Sort: 항상 O(n log n), 안정, O(n) 추가 메모리 │
│ Java: 기본 타입 → QuickSort, 객체 → TimSort(Merge 기반) │
│ │
│ 4. BST → 최악 O(n) → 레드블랙 트리로 O(log n) 보장 │
│ TreeMap, TreeSet, HashMap(충돌) = 레드블랙 트리 │
│ │
│ 5. 스택(LIFO) = DFS, 큐(FIFO) = BFS │
│ PriorityQueue = 힙 = O(log n) 삽입/삭제, O(1) 최솟값 │
│ │
│ 6. 이진 탐색 = 정렬 전제 + 절반 제거 → O(log n) │
│ mid = left + (right - left) / 2 (오버플로우 방지) │
└────────────────────────────────────────────────────────────────────────┘