자바 컬렉션 내부 — ArrayList, HashMap, ConcurrentHashMap의 구현 원리

HashMap의 시간 복잡도가 O(1)이라고 배웠는데, 내부적으로 어떻게 그게 가능할까요? 해시 충돌이 나면 어떻게 되나요?

ArrayList 내부 구조

핵심: 동적 배열

ArrayList는 내부적으로 Object[] 배열을 사용합니다.

JAVA

// ArrayList 내부 (간소화)
public class ArrayList<E> {
    Object[] elementData;  // 실제 데이터 저장
    int size;              // 현재 요소 수

    // 기본 용량: 10
    private static final int DEFAULT_CAPACITY = 10;
}

배열 확장 (grow)

배열이 가득 차면 1.5배 크기의 새 배열을 만들고 복사합니다.

PLAINTEXT

초기:     [a][b][c][d][e][f][g][h][i][j]  (용량 10, size 10)
add(k):   새 배열 생성 (용량 15)
          [a][b][c][d][e][f][g][h][i][j][k][ ][ ][ ][ ]
          ↑ Arrays.copyOf()로 복사

배열 복사는 O(n)이지만 자주 발생하지 않으므로 분할 상환(amortized) O(1) 입니다.

중간 삽입/삭제

PLAINTEXT

add(2, "x"):  [a][b][c][d][e]
              → [a][b][ ][c][d][e]  // 뒤로 밀기: System.arraycopy
              → [a][b][x][c][d][e]

remove(2):    [a][b][x][c][d][e]
              → [a][b][c][d][e][ ]  // 앞으로 당기기

중간 삽입/삭제는 O(n)입니다. 끝에 추가하는 것만 O(1)입니다.

HashMap 내부 구조

핵심: 버킷 배열 + 연결 리스트/트리

JAVA

// HashMap 내부 (간소화)
public class HashMap<K,V> {
    Node<K,V>[] table;       // 버킷 배열
    int size;                // 요소 수
    float loadFactor = 0.75f; // 적재율
    int threshold;            // size > threshold이면 리사이즈

    static class Node<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;      // 연결 리스트
    }
}

put() 동작

PLAINTEXT

1. hash = key.hashCode() ^ (key.hashCode() >>> 16)  // 해시값 계산
2. index = hash & (table.length - 1)                  // 버킷 인덱스
3. table[index]가 비어있으면 → Node 생성
4. table[index]에 이미 있으면 → 해시 충돌!
   - 같은 키 → 값 덮어쓰기
   - 다른 키 → 연결 리스트에 추가 (또는 트리)
5. size > threshold이면 → 배열 2배 확장 (리해싱)

해시 충돌 처리

Java 8부터 연결 리스트 길이가 8개 를 넘으면 레드-블랙 트리 로 변환됩니다.

PLAINTEXT

버킷[3]: Node(A) → Node(B) → Node(C) → ...
         연결 리스트: O(n) 탐색

         길이 > 8이면 트리로 변환
버킷[3]: TreeNode 구조
         레드-블랙 트리: O(log n) 탐색

트리 노드 수가 6개 이하로 줄면 다시 연결 리스트로 복원합니다.

리사이즈 (rehash)

PLAINTEXT

기존: table[16], loadFactor=0.75, threshold=12
size가 13이 되면:
→ table[32]로 확장
→ 모든 노드의 인덱스를 재계산 (rehash)
→ threshold = 32 * 0.75 = 24

초기 용량을 적절히 설정하면 리사이즈를 줄일 수 있습니다:

JAVA

// 100개를 넣을 예정이면
int capacity = (int) (100 / 0.75) + 1; // 134
Map<String, String> map = new HashMap<>(capacity);

// 또는 Java 19+
Map<String, String> map = HashMap.newHashMap(100); // 자동 계산

ConcurrentHashMap 내부 구조

핵심: 버킷 단위 잠금

Java 8부터 버킷 하나에만 synchronized를 거는 세밀한 잠금을 사용합니다.

JAVA

// ConcurrentHashMap의 put (간소화)
final V putVal(K key, V value) {
    int hash = spread(key.hashCode());
    Node<K,V>[] tab = table;
    int i = (tab.length - 1) & hash;

    if (tab[i] == null) {
        // CAS(Compare-And-Swap)로 원자적 삽입
        casTabAt(tab, i, null, new Node<>(hash, key, value));
    } else {
        synchronized (tab[i]) {  // 해당 버킷만 잠금
            // 연결 리스트/트리에 추가
        }
    }
}

HashMap vs ConcurrentHashMap

항목	HashMap	ConcurrentHashMap
스레드 안전	X	O
잠금 방식	없음	버킷 단위
null 키	허용 (1개)	불허
null 값	허용	불허
Iterator	fail-fast	weakly consistent
성능 (단일 스레드)	빠름	약간 느림

null 불허 이유

map.get(key)가 null을 반환하면, "키가 없는 것인지" vs "값이 null인 것인지" 구분할 수 없습니다. 단일 스레드에서는 containsKey()로 확인할 수 있지만, 멀티스레드에서는 확인과 조회 사이에 다른 스레드가 변경할 수 있어서 안전하지 않습니다.

자주 헷갈리는 포인트

ArrayList 초기 용량: 기본 10이지만, 많은 데이터를 넣을 예정이면 new ArrayList<>(1000) 처럼 초기 용량을 지정하면 배열 복사를 줄입니다.
HashMap의 해시 분산: hashCode()가 나쁘면 같은 버킷에 몰려서 O(n)이 됩니다. String, Integer의 hashCode는 잘 분산됩니다.
Collections.synchronizedMap vs ConcurrentHashMap: synchronizedMap은 모든 연산에 전체 잠금을 걸어서 동시성이 낮습니다. ConcurrentHashMap이 항상 더 나은 선택입니다.
LinkedHashMap: HashMap + 삽입 순서 보장. 내부적으로 이중 연결 리스트를 추가로 관리합니다. LRU 캐시를 만들 때 사용합니다.

정리

컬렉션	내부 구조	조회	삽입	특징
ArrayList	동적 배열	O(1)	O(1)*	*끝에 추가, 중간은 O(n)
HashMap	배열 + 연결 리스트/트리	O(1)	O(1)	해시 충돌 시 트리 변환
ConcurrentHashMap	배열 + CAS/sync	O(1)	O(1)	버킷 단위 잠금, null 불허

References

HashMap Javadoc