Foundations

HashMap과 ConcurrentHashMap에 대해서 설명해주세요

해시 버킷, 충돌 처리, Java 8 트리화(Treeification), 세그먼트 락에서 CAS 방식으로의 진화까지 — HashMap과 ConcurrentHashMap의 내부 동작 원리를 인터랙티브 시각화로 완전 정복합니다.

2026년 4월 19일 · 약 14분 읽기

Q. "HashMap과 ConcurrentHashMap의 내부 동작 원리 차이를 설명하고, 멀티스레드 환경에서 HashMap 사용 시 어떤 문제가 발생하는지 말씀해주세요."

예상 꼬리질문

답변 가이드

"HashMap은 해시 함수로 key를 버킷 인덱스에 매핑한 뒤, 충돌이 발생하면 연결 리스트로 체이닝합니다. Java 8부터는 한 버킷의 체인 길이가 8 이상이 되면 레드-블랙 트리(Red-Black Tree)로 자동 변환하여, 최악의 경우 탐색 성능이 O(n)에서 O(log n)으로 개선됩니다. 단, HashMap은 동기화 메커니즘이 없어 멀티스레드 환경에서는 사용해서는 안 됩니다."

"HashMap을 멀티스레드 환경에서 사용하면 두 스레드가 동시에 put()을 호출할 때 리해싱(rehashing) 과정에서 데이터가 유실되거나, Java 7 이하에서는 연결 리스트가 순환 참조로 변형되어 무한 루프가 발생합니다. ConcurrentHashMap은 이 문제를 해결하기 위해 Java 8에서 버킷 단위 CAS(Compare-And-Swap) + synchronized 방식을 채택했습니다."

"실무에서는 공유 상태를 멀티스레드에서 읽고 쓰는 경우 ConcurrentHashMap, 단일 스레드면 HashMap을 선택합니다. 또한 복합 연산은 computeIfAbsent(), merge() 같은 원자적 메서드를 사용해야 경쟁 조건(race condition)을 방지할 수 있습니다."

면접관이 HashMap과 ConcurrentHashMap을 묻는 건 "어떤 자료구조를 쓰는지 알고 있나요?"가 아닙니다. "멀티스레드 환경에서 데이터 안전성을 어떻게 설계하나요?"를 확인하는 겁니다.

이 아티클에서는 버킷 구조, 해시 충돌, 트리화, 그리고 Java 8 ConcurrentHashMap의 CAS 기반 잠금 전략까지 — 인터랙티브 시각화로 직접 눈으로 확인하며 학습합니다.

1. 해시 버킷의 구조와 충돌 처리

꼬리질문: "HashMap은 해시 충돌을 어떻게 처리하나요? Java 8에서 바뀐 점은 무엇인가요?"

HashMap의 핵심은 해시 함수(hash function)입니다. key를 입력받아 해시값을 계산하고, 그 값으로 버킷(bucket) 배열의 인덱스를 결정합니다. 서로 다른 key가 같은 버킷 인덱스로 매핑되는 해시 충돌(hash collision)이 발생하면 체이닝(chaining) 방식으로 연결 리스트에 이어 붙입니다.

버킷의 용량은 기본 16개이며, 부하 계수(load factor) 0.75를 초과하면 테이블 크기를 2배로 늘리는 리해싱(rehashing)이 발생합니다. 이 과정은 O(n)의 비용이 들고, 멀티스레드 환경에서는 데이터 유실이나 무한 루프의 원인이 됩니다.

key를 입력하여 버킷 인덱스 결정 과정을 직접 확인하고, 리해싱 시뮬레이션을 실행해보세요.

해시 버킷 시뮬레이터

key를 입력하면 해시 계산 → 버킷 인덱스 결정 과정을 확인할 수 있습니다

index = (capacity - 1) & (hashCode ^ (hashCode >>> 16))

항목 수: 0 / 임계값: 12 (capacity 16 × 0.75)0%

버킷 배열 (처음 16개 표시, capacity=16)

[0]

null

[1]

null

[2]

null

[3]

null

[4]

null

[5]

null

[6]

null

[7]

null

[8]

null

[9]

null

[10]

null

[11]

null

[12]

null

[13]

null

[14]

null

[15]

null

Java 8에서는 hash() 메서드가 h ^ (h >>> 16) 연산으로 상위 비트를 하위 비트에 XOR합니다. 이렇게 하면 비트 패턴이 고르게 분산되어 버킷 충돌 빈도를 줄입니다.

2. Java 8 트리화 — 연결 리스트에서 레드-블랙 트리로

꼬리질문: "Java 8의 트리화(Treeification) 메커니즘이란 무엇인가요?"

한 버킷에 항목이 너무 많이 몰리면 탐색 성능이 O(n)으로 저하됩니다. Java 8은 이를 해결하기 위해 트리화(Treeification) 메커니즘을 도입했습니다. 한 버킷의 체인 길이가 8 이상이고 전체 테이블 크기가 64 이상이면, 연결 리스트를 레드-블랙 트리(Red-Black Tree)로 변환합니다.

체인 길이가 6 이하로 줄어들면 다시 연결 리스트로 복원하는 언트리화(untreeify)가 이루어집니다. 이 임계값 차이(8 → 트리화, 6 → 언트리화)는 불필요한 전환을 방지하는 히스테리시스(hysteresis) 설계입니다.

노드를 추가하여 체인 길이 8에서 레드-블랙 트리로 자동 변환되는 과정을 확인하고, 탐색 시뮬레이션으로 O(n) vs O(log n)을 비교해보세요.

트리화(Treeification) 시뮬레이터

노드를 추가하여 체인 길이 8에서 레드-블랙 트리로 자동 변환되는 과정을 확인하세요

현재 구조

연결 리스트

체인 길이

현재 구조

—

트리화 임계값: 체인 ≥ 8 AND 테이블 크기 ≥ 64언트리화: 체인 ≤ 6

04/88

→

→ null

탐색: O(n) — 순차 방문

연결 리스트 탐색

O(n)

최악 n개 방문

레드-블랙 트리 탐색

O(log n)

균형 유지로 빠름

3. HashMap의 스레드 안전 문제

꼬리질문: "멀티스레드 환경에서 HashMap 사용 시 어떤 문제가 발생하나요?"

HashMap은 동기화 메커니즘이 전혀 없습니다. 두 스레드가 동시에 put()을 호출하고 리해싱이 트리거되면, 연결 리스트 재구성 과정에서 순환 참조(circular reference)가 형성될 수 있습니다(Java 7 이하). 이후 get()이 해당 버킷에서 무한 루프에 빠져 CPU 사용률이 100%로 치솟는 치명적인 버그가 발생합니다.

Java 8에서는 리해싱 방식이 개선되어 무한 루프 문제는 해결되었지만, 데이터 유실과 size() 불일치는 여전히 발생합니다. 동시에 put()이 실행되면 한 스레드의 쓰기가 다른 스레드의 쓰기를 덮어쓸 수 있기 때문입니다.

단일 스레드와 멀티스레드 모드를 전환하여 경쟁 조건(race condition)이 어떻게 데이터를 손상시키는지 확인해보세요.

스레드 안전성 시뮬레이터

단일 스레드 vs 멀티스레드 환경에서 HashMap에 동시 쓰기 시 무슨 일이 일어나는지 확인하세요

Thread-1

Thread-2

충돌 발생

시뮬레이션을 실행하면 타임라인이 표시됩니다

Collections.synchronizedMap(HashMap)은 모든 메서드에 단일 락을 걸어 스레드 안전성을 확보하지만, 동시에 하나의 스레드만 진입 가능하므로 ConcurrentHashMap에 비해 성능이 크게 떨어집니다.

4. ConcurrentHashMap의 진화 — 세그먼트 락에서 CAS로

꼬리질문: "ConcurrentHashMap이 Java 5에서 Java 8로 넘어가면서 내부 구현이 어떻게 바뀌었나요?"

Java 5에서 도입된 ConcurrentHashMap은 처음에 세그먼트(Segment) 기반 분할 잠금을 사용했습니다. 내부를 16개의 세그먼트로 나누고, 각 세그먼트가 독립적인 ReentrantLock을 보유합니다. 서로 다른 세그먼트에 속한 key는 동시에 쓸 수 있어 HashMap보다 동시성이 크게 향상되었습니다.

Java 8에서는 세그먼트를 완전히 제거하고 버킷 레벨 CAS + synchronized 방식으로 전환했습니다. 빈 버킷에 첫 번째 노드를 삽입할 때는 CAS(Compare-And-Swap) 연산으로 락 없이 처리하고, 이미 노드가 있는 버킷은 첫 번째 노드를 synchronized로 잠급니다.

두 버전의 구조를 탭으로 전환하여 비교하고, put() 동작 과정을 단계별로 확인해보세요.

ConcurrentHashMap 진화: Java 5-7 vs Java 8+

세그먼트 락 방식과 버킷 레벨 CAS 방식을 단계별로 비교합니다

Java 5-7 구조: 16개 세그먼트, 각각 ReentrantLock 보유

Seg[0]

🔒 Lock

Seg[1]

🔒 Lock

Seg[2]

🔒 Lock

Seg[3]

🔒 Lock

Seg[4]

🔒 Lock

Seg[5]

🔒 Lock

Seg[6]

🔒 Lock

Seg[7]

🔒 Lock

Seg[8]

🔒 Lock

Seg[9]

🔒 Lock

Seg[10]

🔒 Lock

Seg[11]

🔒 Lock

Seg[12]

🔒 Lock

Seg[13]

🔒 Lock

Seg[14]

🔒 Lock

Seg[15]

🔒 Lock

최대 동시 쓰기: 16개 (세그먼트 수)

put() 동작 시뮬레이션

1. 세그먼트 선택락 없음

hash로 16개 세그먼트 중 하나 선택

2. 세그먼트 락 획득ReentrantLock

ReentrantLock.lock() — 같은 세그먼트는 대기

3. 버킷 탐색 → 삽입ReentrantLock

세그먼트 내 버킷 배열에서 위치 찾아 삽입

4. 세그먼트 락 해제락 없음

ReentrantLock.unlock() — 대기 중인 Thread-2 진입

Java 5-7 최대 동시 쓰기

16개

세그먼트 수 고정

Java 8+ 최대 동시 쓰기

N개

버킷 수에 비례

Java 8 ConcurrentHashMap의 읽기(get())는 volatile 읽기만 수행하므로 락 없이 항상 안전합니다. 쓰기가 빈번하지 않고 읽기가 대부분인 시나리오에서 특히 성능이 우수합니다.

5. 원자적 복합 연산 — computeIfAbsent, merge, compute

꼬리질문: "ConcurrentHashMap에서 원자적 복합 연산을 사용해야 하는 이유는 무엇인가요?"

멀티스레드 환경에서 containsKey() + put()을 조합하면 경쟁 조건(race condition)이 발생합니다. 두 스레드가 동시에 containsKey()에서 false를 받고, 둘 다 put()을 호출하면 값이 중복 계산되거나 의도치 않은 덮어쓰기가 일어납니다.

ConcurrentHashMap은 이를 해결하는 원자적 복합 연산 메서드들을 제공합니다.computeIfAbsent()는 키가 없을 때만 값을 계산·삽입하고, merge()는 기존 값과 새 값을 원자적으로 결합합니다.

위험한 패턴과 안전한 패턴을 전환하여 경쟁 조건이 어떻게 발생하는지 비교해보세요.

원자적 복합 연산 데모

비원자적 패턴의 위험성과 ConcurrentHashMap 원자적 메서드의 안전성을 비교합니다

// ⚠ 위험: check-then-act가 원자적이지 않음
if (!map.containsKey(key)) {
    map.put(key, expensiveCompute(key));
    // 두 스레드가 동시에 이 블록 진입 가능!
}

시뮬레이션을 실행하면 타임라인이 표시됩니다

ConcurrentHashMap 원자적 복합 연산 메서드

computeIfAbsent(key, fn)— 키 없을 때만 fn 실행 후 저장

merge(key, val, remappingFn)— 기존 값과 새 값을 fn으로 결합

compute(key, remappingFn)— 키의 현재 값을 fn으로 업데이트

putIfAbsent(key, val)— 키 없을 때만 val 저장

자주 발생하는 문제

실무와 면접에서 자주 마주치는 HashMap/ConcurrentHashMap 관련 문제들입니다. 각 항목을 클릭하여 상황, 원인, 해결 방법을 확인하세요.

핵심 정리

— HashMap: 해시 함수로 버킷 인덱스 결정 → 충돌 시 체이닝 → Java 8에서 체인 8개 이상이면 레드-블랙 트리로 자동 전환 → 단일 스레드 전용
— ConcurrentHashMap: Java 5(세그먼트 락) → Java 8(버킷 레벨 CAS + synchronized)으로 진화 → 읽기는 락 없이 안전, 쓰기는 버킷 단위 분산 잠금
— 멀티스레드 환경 선택 기준: 동시 읽기·쓰기가 있으면 ConcurrentHashMap, 단일 스레드면 HashMap, synchronizedMap은 성능상 비추천
— 원자적 연산 필수: 복합 연산은 반드시 computeIfAbsent, merge, compute 사용
— null 주의: ConcurrentHashMap은 null key·value 모두 금지

더 알아볼 주제

레드-블랙 트리의 회전 알고리즘, LongAdder vs AtomicLong 성능 차이, Java의 volatile과 happens-before 관계, Lock-Free 알고리즘과 CAS의 ABA 문제

퀴즈로 확인하기

배운 내용을 실제 코드 시나리오에 적용해보세요.

Quiz 1

부하 계수와 리해싱

HashMap<String, Integer> map = new HashMap<>();
// 기본 capacity=16, loadFactor=0.75
// 몇 번째 put()에서 리해싱이 트리거되나요?

Quiz 2

트리화 조건

// 전체 테이블 크기가 32일 때
// 한 버킷에 노드가 8개 쌓였습니다.
// 트리화(Treeification)가 발생할까요?

Quiz 3

ConcurrentHashMap의 null 처리

ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
map.put("key", null); // 이 줄의 결과는?

Quiz 4

경쟁 조건 vs 원자적 연산

ConcurrentHashMap<String, Integer> visitCount = new ConcurrentHashMap<>();
// 여러 스레드가 동시에 "home" 페이지 방문을 카운트합니다.
// 어떤 코드가 올바른가요?

Quiz 5

ConcurrentHashMap get()의 락 여부

ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
// 1000개의 스레드가 동시에 get("key")를 호출합니다.
// 성능 병목이 발생할까요?

추가 학습 자료를 공유합니다.

Baeldung — Guide to java.util.concurrent.ConcurrentHashMap — ConcurrentHashMap의 원자적 연산 메서드(compute, merge, forEach)를 코드 예제 중심으로 상세히 설명한 실용 가이드입니다.
Baeldung — HashMap vs ConcurrentHashMap — 두 구현체의 차이를 코드와 함께 비교하는 입문용 가이드입니다. 스레드 안전성, null 처리, 성능 차이를 빠르게 파악할 수 있습니다.

의견을 들려주세요

서비스 개선에 큰 도움이 됩니다. 익명으로 자유롭게 남겨주세요.