[Java] HashMap, HashTable, ConcurrentHashMap, CopyOnWriteArrayList, SynchronizedList 비교

Map 인터페이스의 구현체로는 HashMap , HashTable, ConcurrentHashMap 등이 있다. Map은 <Key, Value> 형태를 띄게 된다. 그럼 이 셋의 특징과 차이는 무엇이 있을까? 그리고 ArrayList 형태를 띄는 CopyOnWriteArrayList, SynchronizedList란 무엇일까? 한번 알아보자. 

 

📌HashMap

특징

• Key와 value에 null을 허용한다.
• 동기화를 보장하지 않는다.
• 싱글 쓰레드 환경에서 사용하는게 좋다.
• HashTable과 ConcurrentHashMap보다 데이터를 찾는 속도는 빠르다.

단점

• 동기화를 보장하지 않기 때문에 신뢰성과 안정성이 떨어진다.

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(key)) == null ? null : e.value;
    }
    
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
}

 

📌HashTable

특징

• Key와 value에 null을 허용하지 않는다.
• 동기화를 보장한다.(Thread-safe 하다)

단점

• 쓰레드간 동기화 락이 걸리기 때문에 여러 작업을 해야 할 때 병목현상이 발생한다. (멀티쓰레드 환경에서 살짝 느리다)
• Collection Framework가 나오기 이전부터 존재하는 클래스기 때문에 최근에는 잘 사용하지 않는다.

Hashtable은 모든 데이터 변경 메서드가 synchronzed로 선언이 되어있다. synchronized라는 것은 메서드를 호출하기 전에 쓰레드간 충돌이 일어나지 않게 락을 건다는 것이다. 그래서 멀티 쓰레드 환경에서 데이터의 무결성을 보장해준다.

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable {
    
    ...
    
    //조회할때도 synchronized
    public synchronized V get(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }
    
    //값을 집어 넣을때도 synchronized
     public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }
    
}

 

하지만 메서드마다 synchronized가 걸려있기 때문에 동시에 여러 작업을 할 때 병목현상이 발생한다.

 

📌ConcurrentHashMap

ConcurrentHashMap은 HashTable의 단점을 보완하며 Multi-thread환경에서 사용할 수 있도록 나온 클래스이다.

 

특징

• Key와 value에 null을 허용하지 않는다.
• 동기화를 보장한다.(Thread-safe 하다)

 Get 메서드에는 synchronized가 존재하지 않고, 어떤 Entry(키와 값으로 구성되는 데이터)를 조작하는 경우에만 해당 Entry에 대해서 락을 건다. 그래서 HashTable보다 데이터를 다루는 속도가 빠르다.

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> implements ConcurrentMap<K,V>, Serializable {
    
    ...
    
    public V put(K key, V value) {
        return putVal(key, value, false);
    }

    /** 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();
            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
                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;
    }   
}

 

 

📚 정리

	HashMap	HashTable	ConcurrentHashMap
key와 value에 null 허용	O	X	X
동기화 보장(Thread-safe)	X	O	O
추천 환경	싱글 쓰레드	멀티 쓰레드	멀티 쓰레드

싱글 쓰레드 환경 이면 HashTable, 멀티 쓰레드 환경이면 ConcurrentHashMap을 사용하자. 그 이유는 ConcurrentHashMap은 메서드 전체에 락을 거는 것이 아닌 Entry 별로 락을 걸어 데이터를 다루는 속도가 빠르기 때문이다.

---

📌CopyOnWriteArrayList

Map에서 Thread safe를 할 수 있듯이 ArrayList에서도 Thread Safe하게 설계할수 있는데 그것이 바로 이 CopyOnWriteArrayList이다.

 

특징

• 모든 쓰기 동작(add, set, remove, etc)시 복사본을 만들고 수행한다.
• 이 덕분에 읽기 시 lock에서 자유롭다.
• 수정할 일은 거의 없고, 읽기 동작이 많을때 사용한다.

📌SynchronizedList

SynchronizedList도 마찬가지로 Thread safe하게 ArrayList를 만들 수 있지만 CopyOnWriteArrayList 과의 차이가 존재한다.

 

특징

• 모든 읽기와 쓰기 동작 시 lock이 작용된다.
• 쓰기 동작이 많을 시 CopyOnWriteArrayList보다 동작이 빠르기 때문에 쓰기가 많을 경우 사용한다.

📚 정리

CopyOnWriteArrayList는 읽기 동작 시 성능이 좋지만 쓰기 동작 시 Overhead가 발생한다. 따라서 쓰기보다 읽기가 많고, 크기가 작은 리스트에 적용하는 것이 바람직하다.

SynchronizedLists는 모든 동작에 lock이 발생하므로 읽기보다 쓰기 동작이 많은 경우, 크기가 큰 리스트에 사용하는 것이 바람직하다.

 

 

 

📚 + 추가 참고 하기 

https://lealea.tistory.com/251

[기술면접] 자료구조 - 2/2