HashTable
동시성을 보장하는 Map 자료구조 중 하나이다.
그러나 성능이 좋지 않은 오래된 녀석이라 잘 사용하지 않는다.
public synchronized int size() { return count; }
public synchronized V put(K key, V value) { ... }Java API 문서를 보면 알겠지만, synchronized 범벅을 통해 동시성을 보장한다.
동시성을 보장해주는 synchronized는 편리한 키워드지만
컬렉션의 get, put 등 모든 메소드에 사용하게 되면, 당연히 성능이 저하된다.
ConcurrentHashmap
결론적으로 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를 통해 동시성을 보장한다.
CAS는 어떻게 원자성을 보장할까?
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)를 저장한다.
이는 읽기, 쓰기 등의 모든 과정이 하나의 인스트럭션에서 이뤄지기 때문에 원자성을 보장해주는 것이다.
synchronized를 썻는데?!
성능이 좋지 않다고 한 HashTable처럼 synchronized를 사용했다.
중요한 건, 각 버킷마다 사용한 것이다.
각 버킷의 root 노드를 lock으로 사용했으므로, 해쉬 충돌이 발생하지 않는 경우에는 여러 쓰레드에서 접근이 가능하다.
때문에 컬렉션 대부분의 method에 synchronized를 사용한 것보다 훨씬 성능이 좋다.
해쉬 충돌이 자주 발생하면 hashTable로 수렴하겠지만,
내부적으로 spread 함수를 통해, 해쉬 충돌을 줄인다.
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}Fast-safe?
Java.Collection의 대부분은 Fast-fail이다. (HashMap, ArrayList ..)
당연하게도 이는 동시성을 보장해주지 않으므로, 공유 자원에 접근하는 경우에 사용하지 말라는 의미이다.
그래서 ConcurrentModificationException이 메소드 전반에 걸쳐 나타난다. (32개 정도..)
Fast-Fail, Fast-safe는 여기서 보면 될 것 같다.
아무튼, ConcurrentHashMap은 내부적으로 
iterator를 따로 구현했다.
때문에 remove() 메소드에서 ConcurrentModificationException이 발생하지 않는다.
동시성은 ConcurrentHashMap으로 종결?
이 부분은.. 동시성 프로그래밍 환경을 더 겪어봐야 알 것 같다.
그러나 hashMap 말고도 여러가지 멀티 스레드 환경에서 문제가 생기는 일은 많다.
때문에 어떻게 동시성을 보장하고, 내부적으로 구현되어 있는지 파악해둔다면
라이브러리 등을 써도 컨트롤이 가능하지 않을까싶다!
