Tabiro’s BLOG
Tabiro’s BLOG/
ConcurrentHashMap 동작 원리 - CAS와 synchronized로 동시성을 보장하는 방법
ConcurrentHashMap 동작 원리 - CAS와 synchronized로 동시성을 보장하는 방법
Search
ConcurrentHashMap 동작 원리 - CAS와 synchronized로 동시성을 보장하는 방법

ConcurrentHashMap 동작 원리 - CAS와 synchronized로 동시성을 보장하는 방법

Published
2026/08/09
Public
Public
put()은 어떻게 동시성을 보장할까putVal()의 전체 흐름왜 빈 버킷은 CAS일까왜 값이 있는 버킷은 synchronized일까왜 락을 잡은 뒤 다시 확인할까put()은 왜 CAS와 synchronized를 함께 사용할까get()은 왜 락을 잡지 않을까get() 코드그런데 왜 안전할까리사이즈는 어떻게 여러 스레드가 같이 할까MOVED는 무엇일까helpTransfer()리사이즈 중에도 synchronized를 사용한다그런데 왜 전체가 멈추지 않을까그런데 왜 전체가 멈추지 않을까마무리
ConcurrentHashMap의 동시성 제어는 두 가지로 요약된다. CAS와 synchronized다.
버킷이 비어 있는지에 따라 CAS 또는 synchronized를 선택한다.
  • 빈 버킷이면 CAS로 노드를 넣는다.
  • 값이 있는 버킷이면 첫 번째 Node를 synchronized로 잠근다.
  • 읽기(get)는 둘 다 사용하지 않는다.
JDK 7까지는 Segment + ReentrantLock 구조였지만, JDK 8에서 현재 구조로 변경됐다. 이 글은 JDK 17과 21 구현을 기준으로 put(), get(), 리사이즈가 각각 어떤 방식으로 동시성을 보장하는지 살펴본다.

put()은 어떻게 동시성을 보장할까

putVal()의 전체 흐름

put()은 putVal()을 호출한다. 이 메서드는 성공할 때까지 반복해서 시도하는 구조다.
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh; K fk; V fv;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    ...
                }
            }
            ...
        }
    }
    addCount(1L, binCount);
    return null;
}
먼저 tabAt(tab, i = (n - 1) & hash)에서 (n - 1) & hash는 해시값으로 버킷 인덱스를 계산하는 코드다. 그리고 tabAt()은 그 인덱스에 있는 버킷의 첫 번째 Node를 읽어 온다.
버킷 상태에 따라 처리 경로가 네 가지로 나뉜다.
1. 테이블이 아직 없으면 initTable()로 초기화한다.
2. 버킷이 비어 있으면 CAS로 노드를 넣는다.
3. 버킷의 첫 노드 해시가 MOVED면 리사이즈 중이다. 현재 스레드도 helpTransfer()를 통해 리사이즈 작업에 참여한다. (helpTransfer()는 뒤에서 자세히 본다.)
4. 그 외에는 첫 노드를 synchronized로 잠근다.
for (;;)는 삽입에 성공할 때까지 현재 버킷 상태를 다시 확인하기 위한 무한 루프다. 예를 들어 CAS가 실패하면 다른 스레드가 먼저 노드를 넣었다는 뜻이다. 또는 락을 잡고 보니 그 사이 버킷 상태가 이미 바뀌었을 수도 있다. 이런 경우에는 현재 상태를 다시 읽고 처음부터 다시 시도해야 한다. 그래서 break에 도달할 때까지 루프를 반복한다.
spread()는 해시를 분산시킨다.
static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}
상위 16비트를 하위로 섞는다. 해시가 특정 비트에 몰려도 버킷에 더 고르게 분산되도록 하기 위한 처리다. 그리고 HASH_BITS(0x7fffffff)와 AND 연산으로 최상위 비트를 지워 항상 양수로 만든다. 이유는 ConcurrentHashMap이 첫 번째 노드의 해시(f.hash)를 보고 특수 노드인지 일반 노드인지 구분하기 때문이다. MOVED는 -1, TREEBIN은 -2다. 일반 노드의 해시는 항상 양수이므로 f.hash < 0이면 특수 노드라고 판단할 수 있다.

왜 빈 버킷은 CAS일까

빈 버킷에 노드를 넣는 경로는 다음과 같다.
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
    if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
        break;                   // no lock when adding to empty bin
}
casTabAt()은 Unsafe(JVM의 저수준 메모리 연산을 제공하는 내부 클래스)의 CAS를 호출한다.
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                    Node<K,V> c, Node<K,V> v) {
    return U.compareAndSetReference(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
compareAndSetReference()는 “이 위치의 값이 아직 c라면 v로 바꿔라”를 하나의 원자적 연산으로 수행한다. 여기서는 c가 null이므로, 버킷이 비어 있을 때만 새 Node가 들어간다.
두 스레드가 동시에 같은 빈 버킷에 삽입을 시도하면 CAS는 하나만 성공한다.
notion image
  • CAS에 성공한 스레드는 break로 루프를 빠져나간다.
  • 실패한 스레드는 break에 도달하지 못하고 루프를 다시 돈다. 이번에는 tabAt()이 null이 아닌 값을 반환한다. 그래서 synchronized 경로로 들어간다.
락이 필요 없는 이유는 참조값 하나를 바꾸는 것으로 끝나기 때문이다. 리스트를 순회할 필요도, 노드를 연결할 필요도 없다. 단일 연산이라면 CAS로 충분하다.
이 경로가 중요한 이유는 실제로 가장 자주 실행되기 때문이다. (Overview 주석)
OpenJDK는 같은 Overview 주석에서 버킷 크기의 분포도 분석한다. 부하율(load factor) 0.75에서는 버킷당 노드 수가 평균 0.5의 푸아송 분포를 따른다고 가정하며, 이 경우 버킷의 약 60%는 비어 있고 약 30%는 노드 하나만 가진다. 즉 대부분의 put()은 빈 버킷에 첫 번째 노드를 넣는 경우이므로, 락을 잡지 않고 CAS만으로 끝난다.

왜 값이 있는 버킷은 synchronized일까

버킷에 이미 노드가 있으면 CAS로 처리할 수 없다. 리스트를 순회하며 같은 키를 찾아야 하고, 없으면 꼬리에 새 노드를 연결해야 한다. 연산이 여러 단계다. 이때 synchronized를 사용한다.
else {
    V oldVal = null;
    synchronized (f) {
        if (tabAt(tab, i) == f) {
            if (fh >= 0) {
                binCount = 1;
                for (Node<K,V> e = f;; ++binCount) {
                    K ek;
                    if (e.hash == hash &&
                        ((ek = e.key) == key ||
                         (ek != null && key.equals(ek)))) {
                        oldVal = e.val;
                        if (!onlyIfAbsent)
                            e.val = value;
                        break;
                    }
                    Node<K,V> pred = e;
                    if ((e = e.next) == null) {
                        pred.next = new Node<K,V>(hash, key, value);
                        break;
                    }
                }
            }
            ...
        }
    }
    ...
}
주목할 부분은 synchronized (f)다. f는 별도로 만든 락 객체가 아니라 그 버킷의 첫 번째 노드다.
table[i]
   ↓
  Node   ← 이 객체를 잠근다
   ↓
  Node
   ↓
  Node
버킷마다 별도의 락 객체를 두면 메모리 사용량이 크게 늘어난다. 테이블 크기가 100만이면 락 객체도 100만 개가 필요하다. 그런데 앞서 본 것처럼 버킷의 약 60%는 비어 있으므로, 그만큼의 락 객체는 한 번도 사용되지 않는다.
그래서 별도의 락 객체를 만들지 않는다. 버킷에 노드가 있다면 그 첫 번째 Node 자체를 락으로 사용한다. 자바의 모든 객체는 모니터를 가지므로 Node도 그대로 synchronized의 대상이 될 수 있다.
락의 범위는 버킷 하나다. 다른 버킷을 수정하는 스레드는 영향을 받지 않는다. OpenJDK는 무작위 해시를 가정하면 서로 다른 버킷에 접근하는 두 스레드가 같은 락을 두고 경쟁할 확률도 매우 낮다고 설명한다.
Lock contention probability for two threads accessing distinct elements is roughly 1 / (8 * #elements) under random hashes.
여기서 ‘락이 테이블 크기만큼 생긴다’는 표현은 정확하지 않다. 버킷마다 락 객체를 만드는 것이 아니라, 값이 있는 버킷의 첫 번째 Node를 잠그는 것이다. 따라서 빈 버킷에는 잠글 대상 자체가 없다.

왜 락을 잡은 뒤 다시 확인할까

synchronized (f) {
    if (tabAt(tab, i) == f) {
이미 락을 잡았는데도 tabAt(tab, i) == f를 다시 확인한다. f를 읽은 시점과 synchronized(f)의 락을 획득한 시점 사이에는 시간이 있기 때문이다. 따라서 락을 획득한 뒤에도 f가 여전히 현재 버킷의 첫 번째 Node인지 재검증한다.
A가 f를 읽은 뒤 아직 락을 획득하지 못한 사이, B가 먼저 락을 잡고 첫 번째 Node를 변경할 수 있다. 이후 A가 예전에 읽어 둔 f의 락을 획득하더라도, 그 f는 더 이상 현재 버킷의 첫 번째 Node가 아닐 수 있다. 그래서 락을 획득한 뒤 tabAt(tab, i) == f를 다시 확인한다..
첫 노드가 바뀌는 경우는 두 가지다.
  • remove()로 첫 노드가 삭제된 경우. 두 번째 노드가 새로운 첫 노드가 된다. 잠근 f는 이미 리스트에서 분리된 노드다. 여기에 새 노드를 연결해도 맵에 반영되지 않는다.
  • 리사이즈로 버킷이 옮겨진 경우. 그 자리에는 ForwardingNode가 들어간다.
두 경우 모두 tabAt(tab, i) != f가 된다. 그러면 블록 안에서 아무 일도 하지 않고 빠져나온다. binCount가 0인 채로 남으므로 break에 도달하지 못하고, 루프의 처음으로 돌아가 다시 시도한다.
반대로 노드가 추가되는 경우는 문제가 되지 않는다. 새 노드는 항상 리스트의 꼬리에 붙기 때문이다. 첫 노드는 삭제되거나 리사이즈되기 전까지 계속 첫 노드다.
정리하면 putVal()은 두 단계로 안전성을 확보한다. 락으로 버킷을 잠그고, 잠근 뒤 그 락이 여전히 유효한지 검증한다. 검증에 실패하면 재시도한다.

put()은 왜 CAS와 synchronized를 함께 사용할까

CAS는 참조값 하나를 원자적으로 바꾸는 연산이다. 빈 버킷에 노드를 넣는 작업은 배열의 한 칸을 null에서 새 Node로 바꾸는 것이 전부이므로 CAS만으로 충분하다.
반면 값이 있는 버킷은 다르다. 리스트를 순회하며 같은 키를 찾고, 없으면 꼬리 노드의 next를 연결해야 한다. 여러 번의 읽기와 쓰기가 하나의 작업으로 이어지므로 CAS 하나만으로는 처리할 수 없다. 이 구간은 한 번에 하나의 스레드만 수행해야 하므로 synchronized를 사용한다.
그렇다고 모든 put()을 synchronized로 처리하는 것도 비효율적이다. 앞에서 본 것처럼 버킷의 약 60%는 비어 있으므로, 가장 흔한 삽입까지 모두 락을 획득하면 대부분의 put()이 불필요한 락 비용을 지불하게 된다.
그래서 ConcurrentHashMap은 경로를 나눴다.
  • 빈 버킷은 CAS
  • 값이 있는 버킷은 synchronized
단순한 연산은 CAS로 빠르게 처리하고, 여러 단계가 필요한 연산만 synchronized로 처리한다.

get()은 왜 락을 잡지 않을까

get() 코드

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}
get()은 동기화 장치가 하나도 없다.
앞에서 본 것처럼 일반 Node의 해시는 spread() 때문에 항상 양수다. 따라서 eh < 0이면 일반 노드가 아니라 ForwardingNode나 TreeBin 같은 특수 노드라는 뜻이다.
이 경우 get()은 직접 처리하지 않고 find()에 위임한다.
  • ForwardingNode라면 이미 해당 버킷이 새 테이블로 이동한 상태다. find()는 nextTable을 따라가 새 테이블에서 다시 조회한다.
  • TreeBin이라면 연결 리스트 대신 Red-Black Tree로 변환된 버킷이다. find()는 트리 탐색으로 원하는 노드를 찾는다.
두 경우 모두 읽기만 수행한다. ForwardingNode는 이미 완성된 새 테이블을 가리키고, TreeBin.find()도 조회 전용으로 동작한다. 이 경로에서도 synchronized는 사용하지 않는다.

그런데 왜 안전할까

Node의 필드 선언에 답이 있다.
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
hash와 key는 final이다. 생성 이후 바뀌지 않는다. 값이 바뀌는 val과 next는 volatile이다. 쓰기 스레드가 값을 바꾸면 읽기 스레드가 즉시 본다.
tabAt()도 일반 배열 접근이 아니다.
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getReferenceAcquire(tab, ((long)i << ASHIFT) + ABASE);
}.
배열 참조에는 volatile을 붙일 수 있지만 배열의 각 요소에는 volatile을 적용할 수 없다. 따라서 table[i]를 volatile처럼 읽는 방법이 필요하다.
ConcurrentHashMap은 이를 위해 Unsafe.getReferenceAcquire()를 사용한다. 이 메서드는 배열 요소를 메모리 가시성이 보장되는 방식으로 읽는다. 즉, 다른 스레드가 먼저 기록한 값을 현재 스레드가 올바르게 볼 수 있도록 보장한다.
즉 읽기의 안전성은 락이 아니라 메모리 가시성으로 확보한다. 읽기는 상태를 바꾸지 않으므로 상호 배제가 필요하지 않다.
javadoc도 이를 명시한다.
ConcurrentHashMap은 읽기가 쓰기에 의해 막히지 않도록 설계됐다. 따라서 쓰기 작업이 진행 중이어도 get()은 대기하지 않는다.

리사이즈는 어떻게 여러 스레드가 같이 할까

MOVED는 무엇일까

putVal()에서 아직 설명하지 않은 경로가 하나 있다.
else if ((fh = f.hash) == MOVED)
    tab = helpTransfer(tab, f);
MOVED는 -1이다. 일반 노드의 해시는 spread() 때문에 항상 양수이므로, f.hash == MOVED라면 일반 노드가 아니라 ForwardingNode라는 뜻이다.
static final class ForwardingNode<K,V> extends Node<K,V> {
    final Node<K,V>[] nextTable;
    ForwardingNode(Node<K,V>[] tab) {
        super(MOVED, null, null);
        this.nextTable = tab;
    }
리사이즈는 기존 테이블의 버킷을 새 테이블로 하나씩 옮긴다. 전송이 끝난 버킷에는 ForwardingNode를 넣는다. 이 노드는 키와 값은 없고, 새 테이블(nextTable)만 가리킨다. 즉 '이 버킷은 이미 새 테이블로 이동했다'는 표시다.
버킷을 단순히 비워 버리면, 다른 스레드는 해당 버킷에 데이터가 없는 것으로 잘못 판단할 수 있다. ForwardingNode는 이런 상황을 막기 위해 새 테이블의 위치를 알려 주는 역할을 한다.
그래서 get()은 리사이즈 중에도 막히지 않는다. ForwardingNode를 만나면 find()가 nextTable을 따라가 새 테이블에서 조회를 이어서 수행한다.

helpTransfer()

쓰기 스레드는 다르다. ForwardingNode를 만나면 새 테이블로 넘어가지 않고 리사이즈 작업에 참여한다.
helpTransfer()는 이름 그대로 리사이즈를 도와주는 메서드다. 실제로 버킷을 옮기는 작업은 transfer()가 수행하며, helpTransfer()는 현재 스레드를 그 작업에 참여시키는 역할을 한다.
helpTransfer()
      ↓
  transfer()
      ↓
   버킷 이동
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
    Node<K,V>[] nextTab; int sc;
    if (tab != null && (f instanceof ForwardingNode) &&
        (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
        int rs = resizeStamp(tab.length) << RESIZE_STAMP_SHIFT;
        while (nextTab == nextTable && table == tab &&
               (sc = sizeCtl) < 0) {
            ...
            if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) {
                transfer(tab, nextTab);
                break;
            }
        }
        return nextTab;
    }
    return table;
}
리사이즈가 진행 중이면 sizeCtl을 CAS로 갱신해 현재 스레드가 리사이즈 작업에 참여했음을 기록한다. 이후 transfer()를 호출해 버킷 일부를 직접 옮긴다. 작업이 끝나면 putVal()의 루프로 돌아가 원래 하려던 삽입을 다시 시도한다.
리사이즈는 여러 스레드가 작업을 나눠 수행한다. 이를 위해 한 스레드가 한 번에 맡을 버킷 수(stride)를 계산한다.
int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
    stride = MIN_TRANSFER_STRIDE; // subdivide range
한 스레드가 한 번에 맡는 버킷 개수는 n / 8 / CPU 개수이며, 최소 16개다. 각 스레드는 transferIndex를 CAS로 갱신해 아직 처리되지 않은 구간을 하나씩 가져간다. 덕분에 여러 스레드가 같은 버킷을 중복해서 옮기지 않고 리사이즈를 함께 수행할 수 있다.

리사이즈 중에도 synchronized를 사용한다

리사이즈는 기존 버킷의 노드를 새 테이블로 옮기는 작업이다. 이때 다른 스레드가 같은 기존 버킷을 동시에 수정하면, 옮기는 도중 노드가 추가되거나 삭제될 수 있다.
그래서 transfer()도 값이 있는 버킷을 옮길 때 첫 번째 노드를 synchronized로 잠근다.
else if ((f = tabAt(tab, i)) == null)
    advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
    advance = true;
else {
    synchronized (f) {
기존 버킷이 비어 있으면 옮길 노드가 없으므로 CAS로 ForwardingNode만 넣으면 된다. 반대로 노드가 있으면, 해당 버킷을 잠근 상태에서 노드를 새 테이블로 옮긴 뒤 기존 자리를 ForwardingNode로 바꾼다. 즉 synchronized는 새 테이블을 잠그는 것이 아니라, 옮기는 동안 기존 버킷이 바뀌지 않도록 잠그는 것이다.
  • 예시
기존 버킷
A → B → C

↓ synchronized(A)

A, B, C를 새 테이블로 이동

↓

기존 버킷 자리를 ForwardingNode로 변경

↓

락 해제

그런데 왜 전체가 멈추지 않을까

그런데 왜 전체가 멈추지 않을까

리사이즈 중에도 잠기는 것은 현재 옮기고 있는 버킷 하나뿐이다. 다른 버킷에 접근하는 스레드는 영향을 받지 않는다.
다만 리사이즈 중에 쓰기가 전혀 막히지 않는 것은 아니다. 쓰려는 버킷이 지금 전송 중이라면 해당 버킷의 synchronized (f)에서 잠시 대기할 수 있다. OpenJDK의 Overview 주석도 이를 설명한다.
즉 리사이즈가 테이블 전체를 멈추지는 않는다. 전송 중인 버킷에서는 잠시 대기할 수 있지만, 다른 스레드는 helpTransfer()를 통해 리사이즈에 참여한다. 덕분에 작업이 여러 스레드로 분산되어 리사이즈가 진행될수록 평균 대기 시간도 줄어든다.
읽기는 이 경우에도 영향을 받지 않는다. ForwardingNode가 새 테이블을 가리키므로 get()은 nextTable을 따라가 조회를 이어서 수행한다.

마무리

ConcurrentHashMap의 동시성 제어는 두 가지로 정리된다.
상황
동작
이유
빈 버킷에 추가
CAS
참조값 하나만 바꾸면 되므로 단일 원자 연산으로 충분하다
값이 있는 버킷 수정
synchronized(첫 노드)
리스트 순회와 연결이 필요해 여러 단계로 나뉜다
조회
락 없음
volatile 필드와 acquire 읽기로 가시성만 보장하면 된다
리사이즈
helpTransfer() + 버킷별 synchronized
여러 스레드가 작업을 나눠 수행하면서, 전송 중인 버킷만 잠근다
ConcurrentHashMap은 모든 연산에 하나의 동기화 방식을 적용하지 않는다. 단순한 연산은 CAS, 여러 단계의 연산은 synchronized, 읽기는 메모리 가시성만으로 처리하도록 경로를 나눴다.
이렇게 상황에 맞는 동기화 방식을 선택해 읽기 성능은 유지하면서도 쓰기와 리사이즈의 안전성을 확보한다.
 
Copyright 2026 Tabiro