컬렉션 프레임워크(Collection Framework) (4) - 해시테이블(Hashtable), 해시맵(HashMap)

1. Hashtable vs HashMap

---

앞서 HashMap 클래스에 있는 메소드의 사용법에 대해 알아보았다.

 

2021.12.28 - [자바] - 컬렉션 프레임워크(Collection Framework) (3) - Map

컬렉션 프레임워크(Collection Framework) (3) - Map

 

컬렉션프레임워크가 등장하기전 자바에서 제공하는 데이터 구조체로 Hashtable 이 있다.

HashMap과 마찬가지로 Map 인터페이스를 구현하여 제공하는 기능은 같지만 차이점이 존재한다.

 

기능	HashMap	Hashtable
키값에 null 허용	가능	불가능
멀티 쓰레드 환경	불안전	안전
중복키 처리방법	나중에 입력한 값으로 변경	초기값 유지

 

HashMap은 키값에 null을 허용하며, 중복된 키를 입력했을 경우 나중에 입력한 값으로 변경되고,

Hashtable은 키값에 null을 허용하지 않으며, 메소드가 synchronized가 걸려있어 멀티쓰레드 환경에서 안전하다.

 

2021.12.24 - [자바] - 쓰레드(3) - Synchronized

쓰레드(3) - Synchronized

 

2. HashMap, Hashtable의 원리

---

키를 해시 처리한뒤 인덱싱을 관리하여 버킷에 저장하는 구조 

위 그림은 hash function을 사용하여 키(key)를 해시값으로 매핑하고, 이 해시값을 인덱싱하여 데이터(value)를 키(key)와 함께 저장한다.  

 

즉, key-value 가 1:1로 매핑되어있어 삽입, 삭제, 검색의과정에서 평균적으로 O(1)의 시간복잡도를 가진다는 장점이있다.

 

int index = A.hashCode() % M
// M 은 전체 데이터의 양

인덱싱을 하는 계산법은 hashCode()를 전체 데이터의 양으로 나눈 나머지로 계산된다.

이렇게 인덱싱을 하게 되면 1/M 의 확률로 같은 공간을 사용하게 되는데 그것을 해시 충돌 이라고 부른다.

 

해시충돌이 일어나는 경우 별도의 관리를 안해주면 탐색의 시간복잡도가 O(1) 에서 O(n) 으로 가까워지기 때문에

Open Addressing 방식과 Seperate Chaining 방식으로 자료구조를 관리한다. 

 

• Open Addressing 방식

Open Addressing 방식은 해시 충돌발생시 뒤에있는 버킷중 빈 버킷을 찾아 자료를 저장하는 방식이다. 

 

그림에서 Sandra의 인덱스는 152이다 하지만 John의 인덱스에 충돌이 발생하기 때문에 153 인덱스에 값을 저장한다.

 

이러한 방식으로 Sandra의 Key 검색이나 삭제를 할때에도 index가 152이고 Key가 일치하지 않으므로 뒤의 index를 검색해서 같은 Key가 나오거나 혹은 Key가 없을 때 까지 조회한다.

 

• Seperate Chaining

Seperate Chaining 방식은 JDK 내부에서도 사용하고있는 방식으로 LinkedList와 Tree를 사용한다.

(데이터가 6개 이하이면 LinkedList를 8개 이상이면 tree를 사용)

 

해시 충돌이 발생하면 인덱스가 가리키고 있는 LinkedList에 노드를 추가하여 값을 삽입한다.

데이터를 조회하거나 삭제할 때 키에 대한 인덱스가 가리키고 있는 LinkedList를 선형검색하여 작업을 수행한다.

 

Seperate Chaning & Open Addressing 효율 비교

데이터의 갯수가 적을때는 Open Addressing의 효율이 더 좋고, 반대의 경우 Seperate Chaning의 효율이 더 좋다.

 

3. HashMap, Hashtable의 리사이징(Resizing)

---

HashMap 클래스를 열어보면

/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

 

선언된 상수들을 보면 해시맵의 초기 용량은 16이고, 기본 load factor는 0.75로 HashMap의 용량이 75%가 채워지면 용량을 2배로 늘리는 작업을 수행한다.

 

이러한 작업은 더큰 버킷을 가지는 배열을 새로만든후, 새로만든 배열에 hash를 다시 계산해서 복사를 한다.

 

따라서 많은 용량을 처리하는 경우 초기 용량과 load factor HashMap 생성시 늘려준다면 불필요한 Resizing 작업을 수행하지 않을 것이다.

HashMap<String,Object> map  = new HashMap<>(16,1.5f);

 

그림 출처 : https://en.wikipedia.org/wiki/Hash_table

Hash table - Wikipedia

 

4. SynchronizedMap 과 ConcurrentHashMap

---

위에서 언급했다 싶히 Map은 동기화를 지원하지 않아 멀티쓰레드 환경에서는 안전하지 못하다고 설명하였다.

 

이를 보완하기위해 등장한 방법이 SynchronizedMap으로 래핑 해주어 동기화가 가능한 맵을 사용하는 것이다.

사용법은 다음과 같다.

 

Map<String ,Object> synMap =  Collections.synchronizedMap(new HashMap<>());

 

하지만 위의 방법을 사용하면 하나의 쓰레드가 접근하였을때 다른 쓰레드가 접근하지 못하게 락(Lock)을 걸어서 속도가 느리다는 단점이 존재한다.

 

따라서 Map의 기능을 부분적으로 동기화를 지원하는 기능을 가진 클래스 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;
    }

 

위의 코드를 전부다 해석할수는 없지만 읽는 기능을 수행할때는 모든 쓰레드의 접근이 가능하다는것을 확인할 수 있다.

 

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

 

하지만 쓰기 기능을 수행하는 과정에서는 동기화를 사용하여 쓰레드를 락(Lock) 하는 것을 확인할 수 있다.

 

ConcurrentHashMap은 HashMap 과 HashTable 보다 더 빠른 성능을 제공하며 쓰레드간의 동기화도 보장하기 때문에 멀티쓰레드 환경에서 장점을 가진다.