ConcurrentHashMap은 실무에서 처음 사용해 봤었다. 코드리뷰를 진행하다가 HashMap을 사용한 코드에 대해서 Thread-Safe한 HashMap인 ConcurrentHashMap을 사용해야 한다고 피드백을 받았다. 그 후로 동시성 문제가 발생할 만한 곳은 ConcurrentHashMap을 사용하여 해결했다.
그러다 문득 동시성 문제를 어떻게 해결하는지 궁금해져서 파헤쳐 보기로 했다.
JDK 21 기준
일단 키-값 쌍 구조인 HashTable을 구현한 클래스는 크게 3가지가 있다.
- HashMap (Thread-Unsafe)
- HashTable (Thread-Safe)
- ConcurrentHashMap (Thread-Safe)
ConcurrentHashMap이 Thread-Safe한 HashMap이라고 했는데, HashTable은 뭘까?
사실 ConcurrentHashMap 이전에 JDK 1.0 버전에 Thread-Safe한 HashMap이 있었다.
바로 `HashTable`이다.
왜 Thread-Safe한 HashMap이 두 개나 있는 걸까?
HashTable부터 파헤쳐 보자.
HashTable
public class Hashtable<K,V> extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
public synchronized int size() {
...
}
public synchronized boolean isEmpty() {
...
}
public synchronized boolean containsKey(Object key) {
...
}
public synchronized V get(Object key) {
...
}
public synchronized V put(K key, V value) {
...
}
...
}HashTable의 코드를 파헤쳐 보면 일부 메서드를 제외하고 모두 `synchronized`가 붙어있는 것을 볼 수 있다.
이것은 무엇을 의미할까?
자바의 모든 인스턴스는 각각의 모니터 락을 보유하고 있다. 스레드가 `synchronized`가 적용된 메서드에 접근하려면 해당 인스턴스의 모니터 락을 획득해야 접근할 수 있고, 그동안 다른 스레드들은 블로킹된다. 심지어 읽기 메서드인 `get()`조차도 `synchronized`가 적용됐기 때문에 블로킹된다.
블로킹된 스레드들은 모니터 대기 큐(Entry Queue)에서 무한 대기하게 된다.
- 무한 대기 : 블로킹된 스레드들은 모니터 락을 획득할 때까지 무한 대기한다.
- 타임아웃 X
- 인터럽트 X
BLOCKED 상태로 아무 일도 못한 채 대기하게 되어 스레드의 유휴시간이 많아지고, 결과적으로 성능 저하가 발생한다.
따라서 HashTable은 동시성 문제를 해결함과 동시에 성능저하가 발생한다.
ConcurrentHashMap
JDK 1.5에 HashTable에서 성능이 개선된 클래스인 ConcurrentHashMap이 나왔다.
ConcurrentHashMap은 HashMap을 사용하면서 발생할 수 있는 동시성 문제를 해결하는 Thread-Safe한 HashMap이다.
Table
ConcurrentHashMap의 해시 테이블로, 키-값 쌍이 저장되는 노드(`Node<K, V>`) 들의 배열이다. 이 배열의 각 요소는 버킷(bucket)이다. 버킷에는 노드가 저장되며, 해시 충돌이 발생하면 노드들이 연결 리스트(체인)나 트리 구조로 구성된다.
HashMap와 동일한 Node 배열이다.
Node
주석에 나와있듯이 ConcurrentHashMap 내에서 엔트리를 나타내는 객체다.
- hash : 해시
- key : 키
- val : 값
- next : 다음 노드
next(다음 노드)는 버킷이 연결 리스트나 트리 구조를 구성할 때 사용된다.
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;
}
int h = spread(key.hashCode());- 해시 충돌을 줄여 해시 테이블 성능 최적화
e = tabAt(tab, (n - 1) & h)원자적으로 해시 인덱스에 해당하는 버킷의 노드를 읽어온다.
public final class Unsafe {
/**
* Fetches a reference value from a given Java variable, with **volatile**
* load semantics. Otherwise identical to {@link #getReference(Object, long)}
*/
@IntrinsicCandidate
public native Object getReferenceVolatile(Object o, long offset);
}Unsafe의 getReferenceVolatile()는 원자성과 가시성을 보장해준다.
- 원자성 : CPU 수준에서 원자성을 보장
- 가시성 : 메모리 배리어를 사용해 가시성을 보장
그 다음은 조건에 따라 분기된다.
tabAt()로 읽어온 노드의 해시와 파라미터로 전달받은 키로 만든 해시가 같을 때
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}노드의 키가 파라미터로 전달받은 키와 같은 인스턴스거나 == (동일성)
노드의 키가 파라미터로 전달받은 키와 같다면 equals (동등성)
노드의 값을 반환한다.
해시 충돌이 발생하지 않아 버킷에 노드가 한 개인 경우다. 대부분 이 경우에 속한다.
노드의 해시값이 음수일 때
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
아래 코드를 보면 음수 값을 가지는 `MOVED` `TREEBIN` 상수를 볼 수 있다.
static final int MOVED = -1; // hash for forwarding nodes
static final int TREEBIN = -2; // hash for roots of trees
static final class ForwardingNode<K,V> extends Node<K,V> {
...
}
static final class TreeNode<K,V> extends Node<K,V> {
...
}- ForwardingNode : 리사이징 중 새 테이블로 전송되는 것을 도와주는 노드
- TreeNode : 해시충돌이 많아지면서 임계점 초과 시 성능을 위해 버킷이 트리 구조로 변환됨
TreeNode, ForwardingNode는 해시를 저장하지 않고, 음수 해시 값을 가지고 있다.
따라서 노드의 해시값이 음수라는 것은 버킷의 구조가 트리라는 걸 의미한다.
그 후 트리 구조를 순회하면서 노드의 값을 반환한다.
해시 충돌이 발생하여 버킷에 노드가 여러 개일 때
while ((e = e.next) != null) {
if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
노드의 next를 따라가며 null이 아닐 때까지 순차적으로 탐색한다.
그리고 해시가 같고, 같은 인스턴스거나(동일성), equals()로 같다면(동등성) 노드의 값을 반환한다.
마지막으로 키에 해당하는 노드가 없을 경우 null을 반환한다.
그런데 HashTable의 `get()`와 달리 `synchronized`를 찾아볼 수 없는 데다가 다른 동기화 기법도 찾아볼 수 없다. 왜일까?
`get()`은 내부에 값을 담는 버킷 배열의 구조를 변경하지 않기 때문에 동기화 없이 여러 스레드에서 동시에 호출되어도 문제가 없다.2. ConcurrentHashMap은 Lock Striping(분할 잠금: 버킷 단위로 잠금을 사용하는 방식)을 사용하기 때문에 특정 버킷만 읽으면 되기 때문에 `get()`전체에 동기화를 할 필요가 없다.
1. 메모리 가시성 문제는 내부에 값을 담는 버킷 배열(`table`)을 `volatile`로 선언해 해결했다.
`synchronized`는 메모리 가시성을 보장해 준다.
이렇게 `synchronized`를 적용하지 않음으로써 읽기 성능을 최적화했다.
put()
public V put(K key, V value) {
return putVal(key, value, false);
}
클라이언트는 공개 인터페이스인 `put()`을 호출하지만, 내부적으로는 `putVal()`이 호출된다.
/** Implementation for put and putIfAbsent */
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();
// 버킷이 비어있으면 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
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else if (onlyIfAbsent // check first node without acquiring lock
&& fh == hash
&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
&& (fv = f.val) != null)
return fv;
// 버킷이 비어있지 않으면 버킷을 동기화하고 삽입
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;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
for (Node<K,V>[] tab = table;;) {특정 조건이 충족될 때까지 무한 반복한다.
- CAS 연산 실패 시 재시도하는 전략
if (key == null || value == null) throw new NullPointerException();HashMap과 달리 ConcurrentHashMap은 key와 value 모두 null을 허용하지 않는다.
그 다음은 조건에 따라 분기된다.
테이블이 없을 때
if (tab == null || (n = tab.length) == 0) tab = initTable();
버킷이 비어있을 때
else if ((f = *tabAt*(tab, i = (n - 1) & hash)) == null) {key의 해시인덱스에 해당하는 버킷이 비어있다면
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break; // no lock when adding to empty binCAS 연산으로 해당 버킷에 노드를 추가한다.
노드가 Forwarding Node일 때
else if ((fh = f.hash) == MOVED)static final int MOVED = -1; // hash for forwarding nodes
tab = helpTransfer(tab, f);그것은 현재 테이블이 리사이징 중이라는 의미이기 때문에 리사이징을 돕는 메서드를 호출한다.
노드가 비어있지 않을 때
else if (onlyIfAbsent && fh == hash &&
((fk = f.key) == key || (fk != null && key.equals(fk))) &&
(fv = f.val) != null)
return fv;`putIfAbsent()`를 호출하면 `onlyIfAbsent`가 true이기 때문에 이 조건을 검사하게 된다.
key에 해당하는 값이 없을 때만 put 하게 되고, 값이 있을 때는 그 값을 반환한다.
그 외 (버킷이 비어있지 않을 때)
버킷이 비어있지 않다면 버킷을 `synchronized`로 동기화한다.
- 버킷이 연결 리스트 구조일 때
- 버킷이 Red-Black 트리 구조일 때
// 해시가 음수면 트리 구조
if (fh >= 0) {
binCount = 1;
// 버킷을 순회한다.
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 동일한 key를 찾았을 때
// put() 일 경우 값 교체
// putIfAbsent()를 호출했을 경우 값 유지
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;
// key가 동일하지 않을 때 다음 노드가 없으면 노드 추가 (연결 리스트)
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value);
break;
}
}
}
버킷이 Red-Black 트리 구조일 때
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
// 노드가 추가되지 않았을 때
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
oldVal = p.val;
// put()를 호출했을 경우 값 교체
if (!onlyIfAbsent)
p.val = value;
}
}- null을 반환 : 노드가 추가됨
- null이 아닌 노드를 반환 : key에 해당하는 노드를 찾음
버킷을 동기화하고 노드를 추가하는 작업을 수행하고 노드 수를 확인한다.
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}노드를 추가하면서 `binCount`를 증가시키는데 `binCount`가 임계값(`TREEIFY_THRESHOLD`)을 넘기면 버킷의 구조를 변경한다.
버킷의 사이즈가 커질수록 검색 속도가 느려지기 때문에 성능을 위해서 아래 조건을 모두 충족할 경우 버킷의 구조를 연결 리스트 구조에서 Red-Black 트리 구조로 변경한다.
- 하나의 버킷에 저장된 노드 수가 8개 이상(`TREEIFY_THRESHOLD = 8`)일 경우
- 전체 배열 크기(`capacity`)가 64 이상(`MIN_TREEIFY_CAPACITY = 64`)일 경우
버킷에 저장된 노드 수(연결 리스트)가 8 이상이어도 전체 배열 크기(`table`)가 64 미만이면 리사이즈 작업을 수행한다.
반대로 Red-Black 트리에서 연결 리스트로 구조가 변경되는 경우도 있다.
- 버킷에 저장된 노드 수가 6개 이하(`UNTREEIFY_THRESHOLD = 6`)일 경우
왜 버킷의 구조를 변경하는 걸까?
각 키에 해당하는 버킷의 노드가 하나뿐이라면 O(1)의 성능을 가진다.
하지만, 해시 충돌이 발생하여 버킷에 여러 개의 노드가 저장되어 있다면?
버킷에 노드가 많아질수록 연결 노드를 다 순회하면서 탐색해야 하기 때문에 O(n)의 성능을 가진다.
노드가 많아지면 많아질수록 탐색 시간이 늘어나는 것이다.
`spread()`로 해시 충돌을 줄여 성능 최적화를 하더라도 한계가 있다.
그래서 성능 최적화를 위해 균형 이진 탐색 트리인 Red-Black 트리 구조로 변경한 것이다.
Red-Black 트리는 충돌이 아무리 많아도 탐색, 삽입, 삭제 모두 O(log n)으로 유지가 가능하다.
Red-Black 트리 구조가 항상 좋은 것은 아니다.위에서 버킷에 저장된 노드 수가 6개 이하일 경우 Red-Black 트리에서 연결 리스트로 구조로 변경된다고 했다. 이 경우 적은 수의 노드를 트리 구조로 구성하면 오히려 불필요한 오버헤드가 발생하기 때문에 일정 노드 수(6개)로 줄어든다면 연결 리스트로 변경하는 것이다.
addCount(1L, binCount);마지막으로 노드 개수를 증가시킨다.
해시테이블의 전체 노드 수를 증가시키고, 특정 조건이 만족되면 해시 테이블을 리사이징하는 역할을 한다.
Constructor
// Creates a new, empty map with the default initial table size (16).
public ConcurrentHashMap() {
}
// Creates a new, empty map with an initial table size accommodating
// the specified number of elements without the need to dynamically resize.
public ConcurrentHashMap(int initialCapacity) {
this(initialCapacity, LOAD_FACTOR, 1);
}
// Creates a new map with the same mappings as the given map.
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
this.sizeCtl = DEFAULT_CAPACITY;
putAll(m);
}
// Creates a new, empty map with an initial table size based on the given
// number of elements (initialCapacity) and initial table density (loadFactor)
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
// Creates a new, empty map with an initial table size based on the given
// number of elements (initialCapacity), initial table density (loadFactor),
// and number of concurrently updating threads (concurrencyLevel).
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}ConcurrentHashMap의 생성자는 총 5개다.
첫 번째 기본 생성자의 주석을 보면 해시 테이블의 기본 사이즈는 16이 된다.
그리고 모든 생성자의 코드를 보면 해시 테이블(`table`)에 대한 초기화 코드가 없는 것을 볼 수 있다.
이것은 지연 초기화 방식을 적용했기 때문이다.
실제로 `put()`으로 데이터를 삽입할 때 `initTable()`를 호출하여 해시테이블을 초기화한다.
생성자의 주요 파라미터
- initialCapacity
- 초기 용량을 결정한다. ConcurrentHashMap의 구현체들은 loadFactor를 고려하여 용량을 수용하기 위해 리사이징 작업을 수행한다.
- loadFactor
- 초기 해시 테이블의 크기를 설정하기 위해 사용되며, 해시테이블의 밀도를 나타낸다.
- 해시 테이블의 버킷 점유율 임계치를 나타낸다.
- (노드 수 / 버킷 수)가 loadFactor를 넘으면 리사이징 작업이 수행된다.
- concurrencyLevel
- 동시에 업데이트되는 스레드의 예상 수
- JDK 8 이상부터 `deprecated`
참고
https://curiousjinan.tistory.com/entry/java-concurrent-hash-map-cas
https://velog.io/@alsgus92/ConcurrentHashMap의-Thread-safe-원리#4-concurrenthashmap-생성자
잘못된 정보나 내용에 대해 피드백해주시면 감사하겠습니다!
'Java' 카테고리의 다른 글
| hashCode()와 equals()를 같이 오버라이딩해야 하는 이유 (0) | 2025.10.30 |
|---|---|
| 제네릭 타입 소거 (Type Erasure) (1) | 2025.07.03 |
| ArrayList는 왜 제네릭 타입 E[]가 아닌 Object[]으로 요소를 관리할까? (1) | 2025.06.12 |