hashTable vs synchronizedMap vs ConcurrentHashMap

Java에서 Thread-safe 한 Map 자료구조를 생각하면 떠오르는 3가지에 대해서 알아보겠습니다.

HashTable

HashTable은 HashMap 이전에 사용하던 자료구조입니다. HashTable은 Thread-safe하게 동작하기 위해 내부가 다음과 같이 구현되어있습니다.

put 메서드 구현부입니다. 메소드에 synchronized가 붙어있어 스레드가 HashTable에 put을 할 때에는 다른 스레드가 접근하지 못해 Thread-safe하게 동작합니다. 또한 다른 메서드들도 synchronized가 붙어 Thread-safe합니다. 하지만 이러한 구조는 문제점을 안고 있습니다.

1. 메서드에 synchronized가 걸려있으면 class 전체에 Lock이 걸리기 때문에 HashTable의 기능 중 하나라도 사용하면 다른 스레드 들은 HashTable 자체에 접근이 불가능합니다.

2. get 메서드는 Lock을 걸지 않더라도 상관 없습니다. 하지만 get도 method Lock이걸려 불필요하게 성능 저하가 발생합니다.

위 같은 이유로 현재 HashTable은 Thread-safe한 구조로 개선할 때 좋은 선택지는 아닙니다.

SynchronizedMap

HashTable 다음은 SynchronizedMap입니다. Collections 클래스에 존재하며 구현은 다음과 같습니다.

mutex를 통하여 Lock을 획득하고 반납하는 방식으로 synchronized 블럭으로 감싸 상호배제를 구현했습니다. 이 방식은 메서드에 대한 단일 락 방식이지만 SynchronizedMap 클래스 자체에는 Lock이 걸리지 않기 때문에 Thread-safe 한 동시에 HashTable에 비해 성능이 좋습니다. 

 

이 방식은 Thread-safe한 구조로 개선할 때 좋은 선택지 처럼 보입니다.

ConcurrentHashMap

ConcurrentHashMap은 JDK 1.5 버전에서 나온 구조로 Concurrency 라이브러리에서 찾아볼 수 있습니다. 내부 구현은 다음과 같습니다.

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 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;
}

매우 복잡하게 구현 되어있지만 핵심은 synchronized 블럭이 존재하는 else { 이후 부분입니다. 1.5 초기 모델에선 Map 구조를 논리적으로 세분화 하여 여러 스레드가 엑세스 하여 작업할 수 있는 환경을 마련해주고 이 세분화된 구조엔 Lock이 걸려있어 별도의 Thread-safe 한 동작을 보장해줍니다. 

 

하지만 위 코드 처럼 Java 8 부터는 더욱 강력한 동시성 지원을 해주고 있습니다. 기존에 존재하던 세그먼트 락 방식이 제거 되고 노드 기반의 락이 적용 되었으며 위 코드는 key-value 쌍이 저장되야할 Node를 찾아가는 동안 Lock을 제공해주어 key-value를 찾는동안 다른 스레드가 업데이트나 삽입을 하지 못하게 막아줍니다. 

 

또한 사이즈를 증가시킨다거나 mappingCount 같은 메서드가 증감할 때 CAS 알고리즘을 사용하여 내부적으로 Lock 없이 동시성으로부터 안전한 동작을 보장해줍니다. 

결론

길진 않지만 Thread-safe 한 3개의 자료구조에 대해 알아보았습니다. 모두 Thread-safe한 구조였지만 막상 내부적으로 큰 차이가 있었고 실제로 HashTable은 성능면에서 굉장히 좋지 않았습니다. 반면에 ConcurrentHashMap은 진짜 Java의 깊은 고뇌 끝에 만들어진게 아닌가 싶을정도로 성능과 안정성 모두를 챙긴 구조였습니다. 

 

물론 대부분의 자바 개발자 분들은 ConcurrentHashMap을 쓰시겠지만 내부 구조를 알고보면 더더욱 매력있는 클래스가 아닌가 싶습니다. 

 

마침.