[큐CS 1주차] 자료구조와 시간복잡도

취업 준비를 위한 CS 스터디를 시작했다. 14주 커리큘럼이고, 1~7주차는 Frontend와 Backend가 공통 CS를 함께 학습한 뒤 직군별 심화 키워드를 선택해서 추가로 파는 구조다. 매주 정리한 내용을 개인 브랜치에 올려 PR을 보내고, 최소 한 명의 PR을 리뷰한다.

1주차 주제는 자료구조 / 시간복잡도.

## 공통 키워드
- Big-O
- Array
- LinkedList
- Stack
- Queue
- Hash Table
- Tree
- Heap

## Backend 심화 (선택)
- Java Collection Framework
- HashMap 내부 구조
- ConcurrentHashMap

나는 백엔드라 Backend 심화까지 다뤘다. 코드는 전부 Java 기준이다.

---

1. 시간복잡도

1-1. Big-O 표기법

참고: 알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기

알고리즘의 수행 시간을 대략적으로 나타내는 방법이다. 표기법은 세 가지가 있다.

• O (Big O) 표기법: 알고리즘 성능이 최악인 경우를 나타낼 때 사용
  • 모든 경우에서 보장되는 성능 지표
• Ω (Big Omega) 표기법: 알고리즘의 성능이 최선인 경우를 나타낼 때 사용
• Θ (Big Theta) 표기법: 알고리즘이 처리해야 하는 수행 시간의 상한과 하한을 동시에 나타냄

셋 중 Big-O를 주로 쓰는 이유는, 최선의 경우는 운에 가깝고 실무에서 중요한 건 “이 알고리즘이 아무리 느려도 이 정도는 보장된다”는 상한선이기 때문이다.

또 Big-O는 입력이 충분히 커졌을 때의 증가 추세만 본다. 그래서 두 가지를 버린다.

• 상수 계수: 3n → O(n)
• 낮은 차수 항: n² + 100n + 5000 → O(n²)

n이 작을 땐 100n이 더 크지만, n이 커지면 n²이 압도한다. 그 지점부터가 Big-O의 관심사다.

💬 그래서 n이 작으면 Big-O가 뒤집힐 수 있다. 실제로 Java의 Arrays.sort()도 배열이 작으면 O(n²)인 삽입 정렬로 처리한다. 재귀 호출·분할 오버헤드보다 그냥 훑는 게 빠르기 때문. “점근적 복잡도”라는 단서가 붙는 이유다.

1-2. 복잡도 등급

• O(1) : 해시테이블
• O(log₂ n) : 이진탐색
  • n이 증가하는 속도보다 수행 시간이 천천히 증가
• O(n) : 순차탐색
  • n이 증가하는 속도만큼 수행 시간도 증가함
• O(n log n) : 병합 정렬, 퀵 정렬
  • 로그함수이나, 앞선 알고리즘보다 수행시간이 큼
• O(n²) : 버블 정렬, 삽입 정렬
  • for 문의 2회 중첩인 경우
• O(n³) : 행렬 곱셈
• O(2ⁿ) : brute-force algorithm

말로만 보면 감이 안 오니 실제 연산 횟수로 비교해봤다.

n	O(log n)	O(n)	O(n log n)	O(n²)	O(2ⁿ)
10	3	10	33	100	1,024
100	7	100	664	10,000	10³⁰
1,000	10	1,000	9,966	1,000,000	—
1,000,000	20	10⁶	2×10⁷	10¹²	—

n = 1,000,000일 때 O(log n)은 20번이면 끝나는데 O(n²)은 1조 번이다. 코딩테스트에서 “입력이 10만이면 O(n²)은 버린다”는 감각이 여기서 나온다.

1-3. 공간복잡도

시간만 자원이 아니다. 컴퓨터의 메모리도 유한한 자원이므로, 알고리즘의 실행을 완료할 때까지 필요한 자원의 양도 따져야 한다.

• 고정 공간: 프로그램 자체가 차지하는 메모리
• 자료구조 공간: 탐색의 대상이 되는 리스트를 저장하는 데 필요한 메모리
• 임시 공간: 알고리즘에서 중간 처리를 위해 사용하는 메모리

시간과 공간은 보통 트레이드오프 관계다. 메모이제이션이 대표적인데, 계산 결과를 저장해두는 공간을 더 써서 시간을 줄인다.

---

2. Array (배열)

Java 기준으로 알아봤다. ^.^ 참고: 자바 배열(Array) 문법 & 응용 총정리

int[] score = new int[5];
int[] score2 = {10, 20, 30};

• println으로 그냥 출력하면 포인터값(해시코드) 이 나온다.
  • for문을 이용하여 순회하도록 하드코딩 하거나
  • Arrays.toString()을 이용하여 배열을 문자열 형식으로 만들어 출력하도록 할 수 있다.

2-1. 왜 인덱스 접근이 O(1)인가

배열의 핵심은 연속된 메모리 공간에 같은 크기의 원소를 나란히 놓는다는 것이다. 그래서 몇 번째 원소든 주소를 곧바로 계산할 수 있다.

주소 = 시작주소 + (인덱스 × 원소크기)

int[] (4바이트) 시작주소가 1000이라면
arr[0] → 1000    arr[1] → 1004    arr[2] → 1008

찾아 들어가는 게 아니라 곱셈 한 번이라 인덱스가 몇이든 O(1)이다. LinkedList가 이걸 못 하는 이유이기도 하다.

2-2. 배열은 길이가 고정이다

• 미리 length를 지정해야 한다.
  • javascript의 경우 공간의 제약이 있지만 자동으로 늘였다 줄였다 해주기 때문에.. 못 느끼는 것

⇒ 배열을 확장하려면? 큰 배열을 새로 만들어 기존 배열을 새 배열에 복사하는 식으로 확장한다.

• for문 하드코딩
• System.arraycopy()
• Arrays.copyOf()

class Test {
    public static void main(String[] args) {
        int[] arr1 = {10, 20, 30, 40, 50};

        int[] arr2 = new int[arr1.length * 2]; // 초기 배열보다 길이가 두 배인 새 배열 선언

        // System.arraycopy() 메서드 사용
        System.arraycopy(arr1, 0, arr2, 0, arr1.length);
        /*
        - 첫번째 인자 : 복사할 배열
        - 두번째 인자 : 복사를 시작할 배열의 위치
        - 세번째 인자 : 붙여넣을 배열
        - 네번째 인자 : 복사된 배열값들이 붙여질 시작위치 (차례대로 붙여 넣어진다)
        - 다섯번째 인자 : 지정된 길이만큼 값들이 복사된다.
        */

        // Arrays.copyOf() 메서드 사용
        arr2 = Arrays.copyOf(arr1, arr1.length); // arr1을 전체 길이만큼 복사해서 arr2에 할당
        System.out.println(Arrays.toString(arr2)); // [10, 20, 30, 40, 50]

        arr2 = Arrays.copyOfRange(arr1, 1, 3); // 시작점 포함, 끝점 제외 → 인덱스 1, 2만 복사
        System.out.println(Arrays.toString(arr2)); // [20, 30]
    }
}

⚠️ copyOfRange(arr, 1, 3)은 시작 포함 / 끝 제외라 [20, 30]이 나온다. 처음 정리할 때 [10, 20, 30, 40, 50]으로 잘못 적어놨었는데, 직접 돌려보고 고쳤다. Java에서 범위를 받는 API는 대부분 이 규칙(substring, subList, IntStream.range)이라 같이 묶어서 외우는 게 낫다.

2-3. 정렬

int[] arr = {3, 1, 2};
Arrays.sort(arr);              // 오름차순
Arrays.sort(arr, 0, 3);        // 0~2까지 부분 정렬 (끝 인덱스 제외)

내림차순은 함정이 있다.

// ❌ 컴파일 에러 - 원시타입 배열엔 Comparator를 넘길 수 없다
int[] arr = {3, 1, 2};
Arrays.sort(arr, Collections.reverseOrder());

// ✅ 래퍼 타입 배열이어야 한다
Integer[] arr = {3, 1, 2};
Arrays.sort(arr, Collections.reverseOrder());  // [3, 2, 1]

Comparator는 객체를 비교하는 인터페이스라 int 같은 원시타입에는 쓸 수 없다. int[]를 내림차순으로 정렬하려면 Integer[]로 박싱하거나, 오름차순 정렬 후 뒤집어야 한다.

💡 참고로 Arrays.sort()는 타입에 따라 다른 알고리즘을 쓴다.

• 원시타입: Dual-Pivot Quicksort — 평균 O(n log n), 메모리를 덜 씀
• 객체타입: TimSort — 안정 정렬(stable), 즉 같은 값의 원래 순서가 보존됨

객체는 “같은 값”이어도 구별되는 인스턴스라 순서 보존이 중요하기 때문이다.

2-4. 시간복잡도 정리

연산	복잡도	이유
인덱스 접근	O(1)	주소 계산 한 번
탐색 (값으로 찾기)	O(n)	처음부터 훑어야 함
맨 뒤 삽입/삭제	O(1)	뒤에 붙이면 끝
중간 삽입/삭제	O(n)	뒤 원소를 전부 밀거나 당겨야 함

---

3. LinkedList (연결 리스트)

배열과 정반대 성격이다. 원소를 연속으로 두지 않고, 각 노드가 다음 노드의 주소를 들고 있는 형태다.

[10|●]──▶[20|●]──▶[30|null]
 data next

• 단일 연결 리스트: 다음 노드만 가리킴
• 이중 연결 리스트: 이전/다음을 모두 가리킴 → 역순 순회 가능
• 원형 연결 리스트: 마지막 노드가 첫 노드를 가리킴

Java의 LinkedList는 이중 연결 리스트로 구현되어 있다.

3-1. Array vs LinkedList

	Array (ArrayList)	LinkedList
메모리 배치	연속	흩어져 있음
인덱스 접근	O(1)	O(n)
중간 삽입/삭제	O(n)	O(1) (위치를 알 때)
맨 앞 삽입/삭제	O(n)	O(1)
추가 메모리	없음	포인터 공간 필요

⚠️ LinkedList의 중간 삽입이 O(1)이라는 말엔 조건이 붙는다. 삽입할 위치를 이미 알고 있을 때만 O(1)이다. list.add(500, x)처럼 인덱스로 접근하면 그 자리까지 O(n)으로 걸어가야 하므로 결국 O(n)이다.

그래서 실무에서는 거의 항상 ArrayList가 낫다. 연속된 메모리는 CPU 캐시 적중률이 높아서, 이론상 O(n)인 연산도 실제로는 LinkedList보다 빠른 경우가 많다. LinkedList는 Deque로 쓸 때 정도가 제 몫을 한다.

---

4. Stack (스택)

LIFO(Last In First Out), 후입선출. 나중에 넣은 게 먼저 나온다. 접시 쌓기를 떠올리면 된다.

연산	설명	복잡도
push	맨 위에 삽입	O(1)
pop	맨 위 꺼내며 제거	O(1)
peek	맨 위 확인 (제거 X)	O(1)

활용처

• 함수 호출 스택: 메서드가 호출되면 쌓이고, 끝나면 위에서부터 걷힌다. 재귀가 깊어지면 StackOverflowError가 나는 이유.
• 괄호 검사, 수식 계산(후위 표기법)
• 브라우저 뒤로가기, 에디터 Undo
• DFS(깊이 우선 탐색)

// ❌ Stack은 레거시 클래스
Stack<Integer> stack = new Stack<>();

// ✅ ArrayDeque 권장
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop()); // 2

⚠️ java.util.Stack은 Vector를 상속한 레거시 클래스다. 모든 메서드에 synchronized가 걸려 있어 단일 스레드에서도 락 비용을 낸다. 게다가 Vector를 상속한 탓에 인덱스로 중간 접근이 가능해서, 스택인데 스택이 아닌 짓을 할 수 있다. Java 공식 문서도 ArrayDeque 사용을 권장한다.

---

5. Queue (큐)

FIFO(First In First Out), 선입선출. 먼저 넣은 게 먼저 나온다. 줄 서기와 같다.

연산	설명	복잡도
enqueue (offer)	뒤에 삽입	O(1)
dequeue (poll)	앞에서 꺼내며 제거	O(1)
peek	앞 확인	O(1)

변형

• 원형 큐(Circular Queue): 배열로 큐를 구현하면 앞에서 빼는 만큼 앞쪽 공간이 낭비된다. 끝과 시작을 이어 붙여 재사용하는 방식.
• 덱(Deque, Double-Ended Queue): 양쪽에서 넣고 뺄 수 있음
• 우선순위 큐(Priority Queue): 들어온 순서가 아니라 우선순위가 높은 것부터 나옴 → 내부는 힙

활용처: BFS(너비 우선 탐색), 작업 대기열, 메시지 큐, 프린터 스풀러

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
System.out.println(queue.poll()); // 1

💡 offer/poll/peek vs add/remove/element 기능은 같지만 실패했을 때가 다르다. 앞쪽은 false나 null을 반환하고, 뒤쪽은 예외를 던진다. 큐가 비거나 가득 차는 게 정상 흐름이라면 앞쪽을 쓰는 게 맞다.

---

6. Hash Table (해시 테이블)

키를 해시 함수에 넣어 나온 값을 인덱스로 삼아, 배열의 해당 위치(버킷)에 값을 저장하는 구조다.

"apple" ──hash()──▶ 3 ──▶ bucket[3] = "사과"

탐색할 때도 키를 해시 함수에 넣으면 위치가 바로 나오므로, 배열을 훑지 않고 평균 O(1) 에 접근한다.

6-1. 해시 충돌

서로 다른 키가 같은 인덱스로 매핑되는 상황이다. 키의 경우의 수는 무한한데 버킷은 유한하므로 충돌은 반드시 일어난다. (비둘기집 원리)

① 체이닝 (Separate Chaining)

버킷마다 연결 리스트를 두고 충돌한 원소를 이어 붙인다. Java HashMap이 쓰는 방식.

bucket[3] ──▶ ("apple", 사과) ──▶ ("grape", 포도)

② 개방 주소법 (Open Addressing)

충돌하면 다른 빈 버킷을 찾아 들어간다. 다음 칸을 보면 선형 탐사, 제곱 간격이면 제곱 탐사, 다른 해시 함수를 쓰면 이중 해싱.

	체이닝	개방 주소법
추가 메모리	포인터 필요	불필요
적재율 1 초과	가능	불가능
캐시 효율	낮음	높음
삭제	간단	까다로움(삭제 표시 필요)

6-2. 적재율과 리사이징

적재율(Load Factor) = 저장된 원소 수 / 버킷 수

적재율이 높아지면 충돌이 잦아져 O(1)이 무너진다. 그래서 일정 기준을 넘으면 버킷 배열을 키우고 모든 원소를 다시 해싱(rehashing) 한다. 이 작업 자체는 O(n)이지만 가끔 일어나므로, 분할 상환하면 여전히 평균 O(1)이다.

연산	평균	최악
삽입/삭제/탐색	O(1)	O(n)

최악이 O(n)인 건 모든 키가 한 버킷에 몰린 경우다. 실제로 이걸 악용해 서버를 마비시키는 HashDoS 공격이 있었고, 그래서 Java 8부터 대응책이 들어갔다(아래 참고).

---

7. Tree (트리)

노드와 간선으로 이루어진 계층적·비선형 자료구조. 사이클이 없다.

        A        ← 루트(root)
      /   \
     B     C     ← A의 자식(child), 서로 형제(sibling)
    / \
   D   E         ← 리프(leaf), 자식이 없는 노드

• 깊이(depth): 루트에서 해당 노드까지의 간선 수
• 높이(height): 해당 노드에서 가장 깊은 리프까지의 간선 수
• 차수(degree): 자식 노드의 개수

7-1. 이진 탐색 트리 (BST)

모든 노드가 최대 2개의 자식을 갖고, 왼쪽 서브트리 < 부모 < 오른쪽 서브트리를 만족하는 트리.

      8
    /   \
   3     10
  / \      \
 1   6      14

찾는 값이 부모보다 작으면 왼쪽, 크면 오른쪽으로만 가면 되므로 한 번 비교할 때마다 후보가 절반으로 줄어든다 → O(log n).

단, 균형이 깨지면 이야기가 달라진다.

1 → 3 → 6 → 8 → 10   (정렬된 데이터를 순서대로 삽입한 경우)

이러면 사실상 연결 리스트라 O(n) 이 된다. 그래서 삽입/삭제 때 스스로 균형을 맞추는 균형 이진 탐색 트리가 필요하다.

• AVL 트리: 좌우 높이 차를 1 이하로 엄격하게 유지 → 탐색이 빠름
• Red-Black 트리: 균형 조건이 느슨함 → 삽입/삭제가 빠름

Java의 TreeMap과 TreeSet이 Red-Black 트리로 구현되어 있다. 그래서 HashMap과 달리 키가 정렬된 상태로 유지된다.

7-2. 순회 (Traversal)

방식	순서	위 트리 결과
전위 (Preorder)	부모 → 왼쪽 → 오른쪽	8, 3, 1, 6, 10, 14
중위 (Inorder)	왼쪽 → 부모 → 오른쪽	1, 3, 6, 8, 10, 14
후위 (Postorder)	왼쪽 → 오른쪽 → 부모	1, 6, 3, 14, 10, 8

💡 BST를 중위 순회하면 오름차순 정렬 결과가 나온다. BST의 정의를 생각하면 당연한 건데, 면접 단골 질문이다.

---

8. Heap (힙)

완전 이진 트리 형태로, 부모와 자식 간에 대소 관계가 정해진 자료구조.

• 최대 힙(Max Heap): 부모 ≥ 자식 → 루트가 항상 최댓값
• 최소 힙(Min Heap): 부모 ≤ 자식 → 루트가 항상 최솟값

⚠️ BST와 헷갈리면 안 된다. 힙은 부모-자식 관계만 보장하고 형제 간 순서는 보장하지 않는다. 그래서 힙에서 최댓값/최솟값은 O(1)에 꺼낼 수 있지만, 특정 값을 찾는 건 O(n) 이다. “정렬된 구조”가 아니라 “최댓값만 위로 올려두는 구조”다.

8-1. 배열로 표현하기

완전 이진 트리라 중간에 빈 자리가 없으므로, 포인터 없이 배열 하나로 표현할 수 있다.

      9              index:  0  1  2  3  4
    /   \            배열:  [9, 7, 5, 3, 1]
   7     5
  / \
 3   1

0-based 인덱스 기준 관계식은 이렇다.

왼쪽 자식 = 2i + 1
오른쪽 자식 = 2i + 2
부모 = (i - 1) / 2

8-2. 삽입과 삭제

• 삽입: 배열 맨 뒤에 넣고, 부모와 비교하며 위로 올린다 (sift-up) → O(log n)
• 삭제: 루트를 꺼내고, 맨 마지막 원소를 루트로 올린 뒤 아래로 내린다 (sift-down) → O(log n)

트리의 높이만큼만 이동하므로 둘 다 O(log n)이다.

활용처: 우선순위 큐, 힙 정렬, 다익스트라 알고리즘, 스케줄러

PriorityQueue<Integer> minHeap = new PriorityQueue<>();          // 기본은 최소 힙
PriorityQueue<Integer> maxHeap =
        new PriorityQueue<>(Comparator.reverseOrder());          // 최대 힙

minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
System.out.println(minHeap.poll()); // 1

⚠️ PriorityQueue를 순회(for, toString)하면 정렬된 순서로 나오지 않는다. 힙은 부모-자식 관계만 지킬 뿐 배열 전체가 정렬된 게 아니기 때문이다. 정렬된 순서로 보려면 poll()을 반복해야 한다.

---

9. Backend 심화

9-1. Java Collection Framework

Collection (interface)
├── List    - 순서 O, 중복 O
│   ├── ArrayList     : 배열 기반, 조회 빠름
│   ├── LinkedList    : 이중 연결 리스트, 앞뒤 삽입/삭제 빠름
│   └── Vector        : 레거시, 동기화됨
├── Set     - 순서 X, 중복 X
│   ├── HashSet       : 해시 기반, 순서 보장 X
│   ├── LinkedHashSet : 삽입 순서 유지
│   └── TreeSet       : Red-Black 트리, 정렬 유지
└── Queue   - FIFO
    ├── ArrayDeque    : 배열 기반 덱 (Stack/Queue 모두 권장)
    └── PriorityQueue : 힙 기반 우선순위 큐

Map (interface)  ← Collection을 상속하지 않음
├── HashMap           : 해시 기반, 순서 보장 X
├── LinkedHashMap     : 삽입 순서 유지
├── TreeMap           : Red-Black 트리, 키 정렬 유지
├── Hashtable         : 레거시, 메서드 전체 동기화
└── ConcurrentHashMap : 동시성 지원

💡 Map은 Collection을 상속하지 않는다. Collection은 원소 하나를 다루는 인터페이스인데 Map은 키-값 쌍을 다루기 때문에 계약이 맞지 않는다. 그래서 Map은 별도 최상위 인터페이스다. 이것도 면접에서 종종 나온다.

ArrayList의 확장 방식도 알아두면 좋다. 내부 배열이 꽉 차면 oldCapacity + (oldCapacity >> 1), 즉 1.5배로 늘린 새 배열에 복사한다. 이 복사 때문에 개별 add()는 O(n)이 될 수 있지만, 분할 상환하면 평균 O(1)이다.

9-2. HashMap 내부 구조

HashMap은 버킷 배열 + 연결 리스트(또는 트리) 로 이루어져 있다.

① 해시값 계산 — 보조 해시

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hashCode()를 그대로 쓰지 않고 상위 16비트를 하위 16비트에 XOR 한다. 왜냐하면 버킷 인덱스를 구할 때 이렇게 하기 때문이다.

index = (n - 1) & hash    // n은 버킷 개수(2의 거듭제곱)

n이 16이면 (n-1)은 0000...1111이라 하위 4비트만 인덱스에 반영된다. 상위 비트가 아무리 잘 흩어져 있어도 버려지는 것이다. 그래서 상위 비트 정보를 하위로 한 번 섞어주는 것이 보조 해시의 역할이다.

② 주요 상수

상수	값	의미
DEFAULT_INITIAL_CAPACITY	16	기본 버킷 개수
DEFAULT_LOAD_FACTOR	0.75	적재율 임계치
TREEIFY_THRESHOLD	8	리스트 → 트리 전환 기준
UNTREEIFY_THRESHOLD	6	트리 → 리스트 복귀 기준
MIN_TREEIFY_CAPACITY	64	트리화를 위한 최소 버킷 수

리사이징은 크기 > 버킷 수 × 0.75일 때 일어난다. 버킷을 2배로 늘리고 전체를 재배치한다.

왜 하필 0.75인가? 낮추면 충돌은 줄지만 메모리가 낭비되고, 높이면 메모리는 아끼지만 충돌이 늘어난다. 0.75가 그 절충점이라고 JDK 주석에 적혀 있다.

③ Java 8의 트리화 (Treeify)

한 버킷의 노드가 8개를 넘고 전체 버킷 수가 64개 이상이면, 그 버킷의 연결 리스트를 Red-Black 트리로 전환한다.

버킷이 리스트일 때  → 최악 O(n)
버킷이 트리일 때    → 최악 O(log n)

앞서 말한 HashDoS 공격에 대한 대응이다. 공격자가 일부러 같은 버킷으로 몰리는 키를 대량 삽입해도 O(log n)으로 방어된다.

전환 기준이 8인데 복귀 기준이 6인 이유는, 7에서 삽입·삭제가 반복될 때 트리화와 리스트화가 계속 왔다 갔다 하는 것을 막기 위해서다. (히스테리시스)

④ equals()와 hashCode() 계약

// 반드시 함께 재정의해야 한다
@Override public int hashCode() { return Objects.hash(id); }
@Override public boolean equals(Object o) { ... }

HashMap은 hashCode()로 버킷을 찾고, 그 안에서 equals()로 정확한 키를 찾는다. 그래서 둘 중 하나만 재정의하면 깨진다.

• hashCode()만 재정의 → 같은 버킷엔 가지만 equals()가 false라 다른 키로 취급
• equals()만 재정의 → 애초에 버킷이 달라서 만나지도 못함

규칙: equals()가 true면 hashCode()도 반드시 같아야 한다. (역은 성립하지 않아도 된다 — 그게 해시 충돌)

9-3. ConcurrentHashMap

HashMap은 스레드 안전하지 않다. 여러 스레드가 동시에 리사이징하면 데이터가 유실되거나, Java 7 시절엔 연결 리스트에 순환 참조가 생겨 무한 루프에 빠지는 문제까지 있었다.

동기화 대안 3가지 비교

	Hashtable	Collections. synchronizedMap	ConcurrentHashMap
락 범위	메서드 전체	객체 전체	버킷 단위
동시 읽기	❌	❌	✅ (락 없음)
null 키/값	❌	원본 따름	❌
성능	낮음	낮음	높음

앞의 두 개는 맵 전체에 락을 걸어서, 스레드가 많아질수록 서로 기다리느라 병목이 된다.

ConcurrentHashMap의 전략 (Java 8 기준)

• 읽기: 락을 걸지 않는다. 내부 노드의 value와 next가 volatile이라, 다른 스레드가 쓴 값을 즉시 볼 수 있다.
• 빈 버킷에 삽입: CAS(Compare-And-Swap) 로 락 없이 처리
• 이미 노드가 있는 버킷: 그 버킷의 첫 노드에만 synchronized

즉 서로 다른 버킷에 쓰는 스레드는 전혀 경합하지 않는다.

📌 Java 7 → 8의 변화도 자주 묻는다. Java 7까지는 맵을 16개의 Segment로 쪼개고 각 세그먼트마다 ReentrantLock을 뒀다(=동시에 16개까지). Java 8부터는 세그먼트를 없애고 버킷 단위 락 + CAS로 바꿔서, 버킷 수만큼 동시성이 올라갔다.

null을 허용하지 않는 이유도 짚어둘 만하다. map.get(key)가 null을 반환했을 때, 단일 스레드라면 containsKey()로 “값이 null인지, 키가 없는지” 확인할 수 있다. 하지만 동시성 환경에서는 그 사이에 다른 스레드가 값을 바꿀 수 있어 확인 자체가 무의미해진다. 그래서 아예 모호함을 없앴다.

---

10. 면접 대비 정리

스터디에서 서로 꼬리질문을 던지기로 해서, 나올 법한 것들을 정리해봤다.

시간복잡도

• Big-O를 주로 쓰는 이유는? → 최악의 경우가 모든 경우에서 보장되는 지표라서
• 시간복잡도가 낮으면 항상 빠른가? → 아니다. 점근적 표기라 n이 작으면 뒤집힐 수 있다

자료구조 선택

• ArrayList와 LinkedList 중 무엇을 쓰겠는가? → 대부분 ArrayList. 인덱스 접근이 O(1)이고 캐시 지역성이 좋다
• Stack 대신 ArrayDeque를 쓰는 이유는? → Stack은 Vector 상속 레거시라 불필요한 동기화 비용과 잘못된 접근이 가능

해시

• HashMap이 O(1)인 이유와 최악이 O(n)인 이유는? → 해시로 위치를 바로 계산 / 모든 키가 한 버킷에 몰릴 때
• equals()와 hashCode()를 같이 재정의해야 하는 이유는? → 버킷은 hashCode로, 키 비교는 equals로 하기 때문
• Java 8에서 HashMap이 달라진 점은? → 버킷이 8개를 넘으면 Red-Black 트리로 전환해 최악 O(log n) 보장

트리/힙

• BST의 최악이 O(n)인 경우는? → 정렬된 데이터를 순서대로 삽입해 한쪽으로 치우친 경우
• 힙과 이진 탐색 트리의 차이는? → 힙은 부모-자식 관계만 보장, BST는 전체 순서 보장
• TreeMap과 HashMap의 차이는? → TreeMap은 Red-Black 트리라 키가 정렬되지만 O(log n)

동시성

• ConcurrentHashMap이 Hashtable보다 빠른 이유는? → 맵 전체가 아니라 버킷 단위로만 락을 걸고, 읽기는 락이 없음
• ConcurrentHashMap이 null을 막는 이유는? → 동시성 환경에선 containsKey()로 모호함을 해소할 수 없어서

---

마무리

1주차라 익숙한 내용이 많을 줄 알았는데, “왜 그런가”를 붙잡고 들어가니 모르는 게 계속 나왔다. HashMap의 보조 해시가 왜 상위 16비트를 XOR하는지, 트리화 기준이 8인데 복귀 기준이 왜 6인지 같은 건 이번에 처음 코드를 열어봤다.

정리하다가 예전에 잘못 적어둔 것도 두 개 고쳤다. Arrays.copyOfRange의 끝 인덱스가 제외라는 것, Arrays.sort에 Collections.reverseOrder()를 넘기려면 원시타입이 아니라 래퍼 타입 배열이어야 한다는 것. 직접 돌려보지 않고 옮겨 적기만 하면 이런 게 남는다는 걸 새삼 느꼈다.

다음 주는 OS - Process / Thread / 동시성이다. 이번 주 마지막에 본 ConcurrentHashMap이 자연스럽게 이어질 것 같다.