동시성을 보장하는 Map 자료구조 중 하나이다.
그러나 성능이 좋지 않은 오래된 녀석이라 잘 사용하지 않는다.
public synchronized int size() { return count; }
public synchronized V put(K key, V value) { ... }
Java API 문서를 보면 알겠지만, synchronized
범벅을 통해 동시성을 보장한다.
동시성을 보장해주는 synchronized
는 편리한 키워드지만
컬렉션의 get, put 등 모든 메소드에 사용하게 되면, 당연히 성능이 저하된다.
결론적으로 ConcurrentHashmap
은 좋은 성능과 함께 동시성을 보장한다.
어떻게 그럴 수 있을까?
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의 경우 동시에 여러 쓰레드에서 접근이 가능하다.
tabAt() 메소드가 내부적으로 volatile
관련 함수로 되어 있긴하다.
putval()
메소드를 보자 (put과 같다)
final V putVal(K key, V value, boolean onlyIfAbsent) {
// null은 저장하지 않는다.
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;
// 최초 실행 시, table 생성
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 존재하지 않는 key(정확히는 hashCode) 값이라면 casTabAt 실행
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;
// 버킷의 root 노드를 lock 객체로 사용한다.
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
// 버킷의 LinkedList를 순회하며 값을 삽입 or 변경 해준다.
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;
}
}
}
// 버킷이 RB Tree로 구현되어 있는 경우
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;
}
굉장히 복잡해 보이지만 정리해보면 제법 단순하다.
저장하려는 key의 hashCode 값에 해당하는 버킷이 존재하나?
- 존재하지 않는다면, Compare And Swap를 이용해 저장한다.
f.hash == MOVED
와 같은 특수 상황을 제외하고 버킷이 존재하나?
버킷의 root 노드를 synchronized
의 lock 객체로 사용하고
LinkedList(Separate Chaining)을 순회하며 value를 삽입 or 수정한다.
만약 버킷이 Tree(RB Tree)로 구현되어 있다면, putTreeVal
을 실행한다.
단순화 하면, key가 없으면 CAS를 이용하고 이미 존재한다면 synchornized
를 통해 동시성을 보장한다.
Compare And Swap 해당 링크에 자세히 설명되어 있지만, 단순화 해보자면
실제 주소값에 저장된 값과 목표값을 비교하기 때문이다.
즉, 위의 경우에 casTabAt(tab, i, null, new Node<K,V>(hash, key, value))
저장된 Node<K, V>가 없으므로 null을 기대하고 실제로 그렇다면
new Node<K,V>(hash, key, value)
를 저장한다.
이는 읽기, 쓰기 등의 모든 과정이 하나의 인스트럭션에서 이뤄지기 때문에 원자성을 보장해주는 것이다.
성능이 좋지 않다고 한 HashTable처럼 synchronized
를 사용했다.
중요한 건, 각 버킷마다 사용한 것이다.
각 버킷의 root 노드를 lock으로 사용했으므로, 해쉬 충돌이 발생하지 않는 경우에는 여러 쓰레드에서 접근이 가능하다.
때문에 컬렉션 대부분의 method에 synchronized
를 사용한 것보다 훨씬 성능이 좋다.
해쉬 충돌이 자주 발생하면 hashTable로 수렴하겠지만,
내부적으로 spread 함수를 통해, 해쉬 충돌을 줄인다.
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
Java.Collection의 대부분은 Fast-fail이다. (HashMap, ArrayList ..)
당연하게도 이는 동시성을 보장해주지 않으므로, 공유 자원에 접근하는 경우에 사용하지 말라는 의미이다.
그래서 ConcurrentModificationException
이 메소드 전반에 걸쳐 나타난다. (32개 정도..)
Fast-Fail, Fast-safe는 여기서 보면 될 것 같다.
아무튼, ConcurrentHashMap
은 내부적으로
iterator를 따로 구현했다.
때문에 remove() 메소드에서 ConcurrentModificationException
이 발생하지 않는다.
이 부분은.. 동시성 프로그래밍 환경을 더 겪어봐야 알 것 같다.
그러나 hashMap 말고도 여러가지 멀티 스레드 환경에서 문제가 생기는 일은 많다.
때문에 어떻게 동시성을 보장하고, 내부적으로 구현되어 있는지 파악해둔다면
라이브러리 등을 써도 컨트롤이 가능하지 않을까싶다!