Java - ConcurrentHashMap

  ConcurrentHashmap 설명에 앞서 HashMap이 무엇인지 리마인드를 한번 하고 넘어가겠습니다.

---

1. HashMap과 HashTable

HashMap은 Java Collections Framework에 속한 구현체 클래스입니다. Collections Framework는 98년에 발표한 Java 2에서 정식으로 선보였으며, Java 5에서 Generic이 적용된 후 변화가 없지만 구현체 성능을 향상시키기 위해 변화해왔습니다.

 JDK 1.0부터 있던 API인 HashTable도 Map 인터페이스를 구현하고 있기 때문에 HashMap과 제공하는 기능은 같지만, HashMap은 보조 해시함수를 사용하기 때문에 HashTable에 비해 *해시 충돌(Hash Collision)이 덜 발생하여 성능 상의 이점을 가집니다. 

 *해시 충돌 : 해시 함수가 서로 다른 두 개의 입력 값에 대해 동일한 출력값을 내는 상황

// Hashtable
public class Hashtalbe<K, V>
	extends Dictionary<K, V>
    implements Map<K, V>, Cloneable, java.io.Serioalizable {
    
    public synchronized int size() { } 
    
    @SupressWarnings("unchecked")
    public synchronized V get(Object key)  { } 
    
    public synchronized V put(K key, V value)  { } 
}

//HashMap
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    public V get(Object key) {}
    public V put(K key, V value) {}
}

 API를 살펴보면, Hashtable 클래스는 메서드 전체에 synchronized 키워드가 존재하는 것을 확인할 수 있습니다. 그러나 동시에 작업을 한다고 한다면 객체마다 Lock을 하나 씩 가지고 있기 때문에 동시에 여러 작업을 해야할 때 병목현상이 발생하게 됩니다. 메서드 접근 시 다른 스레드가 Lock을 얻을 때까지 기다리게 되는 것입니다. Thread-safe하다는 특징이 있지만 위에서 말한 병목현상으로 멀티스레드 환경에서 사용하기는 느리다는 단점이 있습니다. 

 그리고 HashMap의 API를 살펴보면 table과 달리 synchronized 키워드를 볼 수 없습니다. 당연히 멀티스레드 환경에서는 사용할 수 없습니다. 

---

2. ConcurrentHashMap

 이 동시성 이슈를 고려하여 멀티 스레드 환경에서 사용할 수 있도록 나온 클래스가 ConcurrentHashMap입니다.

어떤 동기화 방식을 사용하는지 API를 살펴보고 HashTable의 대안이 될 수 있는지 확인해보겠습니다.

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {

    public V get(Object key) {}

    public boolean containsKey(Object key) { }

    public V put(K key, V value) {
        return putVal(key, value, false);
    }

    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;
            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, null)))
                    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) {
                        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, null);
                                    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;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }
}

 Hashtable과는 다르게 synchronized 키워드가 메서드 전체에 있지 않다는 것을 볼 수 있습니다. get()은 존재하지 않지만, put()에는 볼수가 있는데, 이는 읽기 작업에는 여러 스레드를 동시에 읽을 수 있지만, 쓰기 작업에 한해 특정 버킷에 대한 Lock을 사용한다는 것을 알 수 있습니다. 

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {

    private static final int DEFAULT_CAPACITY = 16;

 
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
}

 DEFAULT_CAPACITY, CONCURRENCY_LEVEL이 16으로 설정되어 있는데, HashMap에서의 버킷을 의미하고, LEVEL의 경우는 동시 작업 가능한 스레드의 수입니다. 버킷 단위로 Lock을 사용하기 때문에 같은 버킷만 아니라면 Lock을 기다릴 필요가 없기 때문에 ConcurrentHashMap에 동시에 데이터를 삽입, 참조하더라도 그 데이터가 다른 세그먼트에 위치하면 서로 Lock을 얻기 위해 경쟁하지 않습니다.

 

 이처럼 읽기 작업보다, 쓰기 작업에 성능이 중요한 상황에서는 같은 버킷이 아니라면 여러 스레드가 동시에 쓰는 작업이 가능한 ConcurrentHashMap을 사용하는 것을 고려하면 좋습니다. 

 

 

 

 

 

 

 

 

 

 

참조

https://d2.naver.com/helloworld/831311

https://devlog-wjdrbs96.tistory.com/269

[Java] ConcurrentHashMap 이란 무엇일까?

https://www.baeldung.com/java-synchronizedmap-vs-concurrenthashmap

Collections.synchronizedMap vs. ConcurrentHashMap | Baeldung