Hashtable에 관해서

개요

HashMap과 비슷한 Collection이지만, Thread-safe 한 특징이 있다.

Thread-safe 하게 동작을 보장하려면 여러가지 방법이 있지만, 그 중 가장 성능이 안좋은 synchronized block을 통해 객체 lock을 걸어 동기화를 보장하는 방법을 사용하고 있다.

 

한번 Hashtable을 살펴보자.

 

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
}

특이하게 Dictionary 라는 abstract class를 상속받고 있다.

다른데 쓰는곳이 있나해서 찾아보니, Hashtable에서만 사용하고 있다.

 

구조를 보다보니 일반적인 Map<K,V> 과 특징이 비슷해서 Map에게 밀린것인건가(?)

(라고 하기엔 @since 1.0 라고 코멘트 달린것으로 보아, 예전 JDK 초창기에 사용하려다가 deprecated 되고 있는 추상클래스이지 싶다)

 

여튼 일반적인 Map 인터페이스를 구현하고 있으므로, Map의 사용법과 동일하다

구현 내용을 들여다보자.

public synchronized int size() {
        return count;
    }

public synchronized boolean isEmpty() {
        return count == 0;
    }
...
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;
    }

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

 

보다시피 Map을 구현하긴 했지만.. 병렬환경에서의 Thread-safe 를 synchronized 키워드를 통해 보장하고 있다.

멀티쓰레드에서의 동작이 보장되나 확인해보자.

static Map<Integer, Integer> hashtable = new Hashtable<>();

    @Test
    void hashTableTest() throws InterruptedException {

        CountDownLatch countDownLatch = new CountDownLatch(3);

        Runnable thread1 = () -> {
            for (int i = 0; i < 10000; i++) {
                hashtable.put(i, i);
            }
            countDownLatch.countDown();
            log.info("thread1 finish");
        };

        Runnable thread2 = () -> {
            for (int i = 10000; i < 20000; i++) {
                hashtable.put(i, i);
            }
            countDownLatch.countDown();
            log.info("thread2 finish");
        };

        Runnable thread3 = () -> {
            for (int i = 20000; i < 30000; i++) {
                hashtable.put(i, i);
            }
            countDownLatch.countDown();
            log.info("thread3 finish");
        };

        new Thread(thread1).start();
        new Thread(thread2).start();
        new Thread(thread3).start();

        countDownLatch.await();

        log.info("hashtable size : {}", hashtable.size());
    }
// Console
thread3 finish
thread1 finish
thread2 finish
hashtable size : 30000

 

기대했던 size대로 잘 데이터가 들어갔다.

만약 thread-safe 보장이 안되는 HashMap을 사용해본다면 어떻게 될까.

static Map<Integer, Integer> hashtable = new HashMap<>();
...
hashtable size : 28023

 

예상한 3만개가 들어가지 않고 개수가 안맞는다.

put 테스트만 해본 결과고 만약 get 과 put을 동시에 호출하게 된다면 아래와 같은 Exception을 만날 수 있다.

// thread를 하나 더 만들어서 keySet을 순회해보자.
Runnable thread4 = () -> {
            Set<Integer> keys = hashtable.keySet();
            for (Integer key : keys) {
                hashtable.get(key);
            }
            countDownLatch.countDown();
            log.info("thread4 finish");
        };

 

ConcurrentModificationException 을 만날 수 있는데, 이는 thread-safe 하지 않은 Collection에 접근과 수정/삽입이 동시에 일어날 경우 발생한다.

Exception in thread "Thread-4" java.util.ConcurrentModificationException
    at java.base/java.util.HashMap$HashIterator.nextNode(HashMap.java:1584)
    at java.base/java.util.HashMap$KeyIterator.next(HashMap.java:1607)
    at dev.gompang.springstudy.SomeTest.lambda$hashTableTest$5(SomeTest.java:77)
    at java.base/java.lang.Thread.run(Thread.java:832)

 

해당 Exception이 발생하는 로직은 아래와 같다.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
... 데이터 삽입
++modCount;
        if (++size > threshold)
            resize();
...
}

 

이 때 modCount 라는게 있는데, 이를 활용해서 데이터를 조회하거나 수정할때 변경점이 있는지를 확인한다.

예를 들어 forEach를 살펴보면

public final void forEach(Consumer<? super K> action) {
            Node<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (Node<K,V> e : tab) {
                    for (; e != null; e = e.next)
                        action.accept(e.key);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }

 

Map에 들어간 element를 순회하기 전의 modCount와 순회한 뒤에 modCount가 같지 않으면 ConcurrentModificationException 를 발생시킨다.

(forEach 뿐만 아니라 Map Operation 곳곳에서 사용된다.)

 

ConcurrentModificationException 의 경우는 Thread-safe 하지 않은 Collection을 병렬 쓰레드에서 사용할 경우 자주 마주칠 수 있으니, 사용하는 환경에 따라 Thread-safe 한 Collection을 꼭 골라 쓰도록 하자.

 

java.util 패키지에 포함된 Collection 유틸성 클래스인 Collections 에는 이미 생성한 Collection을 Thread-safe 하게 변경해주는 기능을 제공한다.

Collections.synchronizedMap()
Collections.synchronizedCollection()
Collections.synchronizedList()
...

 

이들의 공통점은, 기존 생성된 Collection의 element를 다 복사한 후, synchronized 키워드가 붙은 Collection으로 변경(새로 생성) 해서 만들어준다는 것이다.

public E get(int index) {
    synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
    synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
    synchronized (mutex) {list.add(index, element);}
}
public E remove(int index) {
    synchronized (mutex) {return list.remove(index);}
}

 

동기화 키로 사용하는 lock object는 this 즉, 생성한 Collection Object를 지칭한다.

(모든 Operation이 발생할때마다 전역 lock을 이용해 동기화를 보장한다.)

SynchronizedCollection(Collection<E> c) {
            this.c = Objects.requireNonNull(c);
            mutex = this;
        }