[면접-java] Hashtable 이란?

저번에 HashMap에 대해서 정리한 적이 있다. 근데 Hashtable이란 것도 있는데, 그게 뭔지 정리하려한다.

그 전에 HashMap의 원리에 대해 정리한 사진이 있는데, 이 한장이면 커버 가능하다고 생각한다.

(전에 손으로 그린 것보다 100배 낫다 ^^)

 

1. 개요

HashMap만 주구장창 썼는데, HashTable은 또 뭘까?

HashTable 또한 java에서 제공하는 key-value 자료구조이다. 또한 Map 인터페이스 구현체이다. 다이어그램은 아래와 같다.

사실 기본적인 동작은 동일하다고 볼 수 있다. key 중복 허용 안 해서 덮어 쓰고, value는 중복이 가능한 key-value 자료구조다.

조금 더 들여다보기 전에, java doc을 보면 아래와 같다. (근데 불편한 게 HashTable이 아니라 Hashtable이다.)

HashMap & Hashtable doc를 통한 큰 차이점 비교

The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.

• HashMap은 key, value에 null을 허용하지만, Hashtable은 key와 value 둘 다 null이 불가능
• HashMap은 빠르지만 비동기적으로 동작하기 때문에 멀티스레드 환경에서 직접 동기화가 필요하지만, Hashtable은 동기화를 지원하기 때문에 상대적으로 느리다

그럼 이제 좀만 더 자세히 들어가보자!

2. 버전

1. Hashtable
   • jdk 1.0에 등장했으며, Dictionary 기반이다. 얘가 완전 레거시라는 것이다.
2. HashMap
   • jdk 1.2에 등장했으며, Collections Framework 일부로 새롭게 설계됐다. Map 인터페이스 기반으로 설계됐다.

jdk 1.2가 얼마나 오래됐는지 한 번 짚고 넘어가보자! 나중에 자바 버전별 큰 업데이트를 정리해봐야겠다.

• JDK 1.0
  • 1996 년에 나온 것이다.
  • 최초 버전이고, 이 때 Hashtable, Vector, Dictionary 등 클래스가 존재했다.
• JDK 1.2
  • 1998 년에 나온 것이다.
  • Collections Framework가 등장했다. Map, List, Set 등이 나오게 됐다.
• Java 5
  • JDK 1.5라고 볼 수 있다. 왜냐하면 JDK 1.3과 1.4도 있었지만 큰 업데이트는 없었고, 1.5부터는 Java 5라고 불렀기 때문이다.
• 그 이후, Java 7, 8, 9, 10, 11, ..... 쭉 나왔고, Java 8이 엄청 유명하다 들었는데(GC 관련해서도 되게 많이 바꼈다고 한다), 이 부분에 대해서 공부가 필요하다.

아무튼 Hashtable은 엄청나게 오래된 자료구조라는 것이다.

 

3. Hashtable 구현체

위 사진을 보면, 얘는 Dictionary 라는 추상 클래스를 상속받고 있다.

웃긴게 Dictionary를 직접 상속받은 클래스가 Hashtable 밖에 없었다.

그래서 대체 뭔가해서 봤더니 size, isEmpty, put 등 key-value 저장을 위한 최초의 추상클래스였다고한다.

근데 이놈은 결국 jdk 1.2에 등장한 Collections Framework에 완전히 대체됐다고 한다.

아 근데, 완전히 대체라고 하기엔 좀 그렇고, 섞여있다. Map 인터페이스도 상속받아서 구현돼있다.

 

그럼 만약 Dictionary를 상속받지 않는다면?

아주 잘 동작할 것이다. Dictionary는 레거시와 호환하기위한 용도이지, 요즘 key-value 자료구조들은 전부 Map 기반으로 구현됐기 때문이다.

 

사실 뭐 볼 게 별로 없어서 구현체 얘기는 이쯤 끝내도 될 것 같다.

 

4. Hashtable 특징(feat. HashMap)

위의 Java Doc을 다시 보면 Hashtable과 HashMap의 차이를 알 수 있다.

1. Rehash

# Hashtable
The exact details as to when and whether the rehash method is invoked are implementation-dependent

# HashMap
When the number of entries in the hash table exceeds loadFactor x currentCapacity, the table is rehashed(capacity doubled)

HashMap은 전에 정리했기 때문에 Rehash(Resize라고 이해하면 될 듯?)에 대해 알고 있지만, Hashtable은 이게 뭔 소린지 모르겠다 ㅋㅋ. 구현에 따라 rehash 메서드가 언제 일어날지 모른다니..... 그럼 나는 어떻게 알간? ㅠ

그래서 코드를 봤더니 아주 명확히 정의돼있다. 이부분에 대해 gpt에게 물어보니 "지금은 loadFactor 0.75에 맞춰 동작하지만, 미래에 JDK 구현자가 바꿀 수도 있으니 코드에서 이 규칙을 의존하지 말라는 뜻" 이라고 한다. 지금이랑 별 다른게 없는 것 같다.

흠... 지나갈게요

    /**
     * Increases the capacity of and internally reorganizes this
     * hashtable, in order to accommodate and access its entries more
     * efficiently.  This method is called automatically when the
     * number of keys in the hashtable exceeds this hashtable's capacity
     * and load factor.
     */
    @SuppressWarnings("unchecked")
    protected void rehash() {
        int oldCapacity = table.length;
        Entry<?,?>[] oldMap = table;

        // overflow-conscious code
        int newCapacity = (oldCapacity << 1) + 1;
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)
                // Keep running with MAX_ARRAY_SIZE buckets
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
        Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

        modCount++;
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        table = newMap;

        for (int i = oldCapacity ; i-- > 0 ;) {
            for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                Entry<K,V> e = old;
                old = old.next;

                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = (Entry<K,V>)newMap[index];
                newMap[index] = e;
            }
        }
    }

 

2. Sync

아래 코드를 보면 알 수 있듯이, Hashtable의 모든 메서드에는 synchronized가 붙어있다. 따라서 모든 접근에 lock을 걸기 때문에 병렬성이 떨어지고 느리다. 

반대로, Hashmap은 멀티스레드 환경에서 동시 접근하면 안전하지 않으므로, Collections.synchronizedMap()으로 감싸서 직접 동기화해야한다고한다. 이렇게되면 Hashtable이랑 동작이 완전 동일해진다. 메서드에 synchronized 블록을 걸기 때문이다. 따라서 한 번에 한 스레드만 map에 접근 가능하다.

 

또한 ConcurrentHashMap도 있는데,, 얘는 안 써봐서 잘 모르겠다. 

부분 락(jdk 8 이후 CAS + 버킷 단위)을 통해 여러 스레드가 동시 접근 가능하고,,

중간에 map이 변경돼도(데이터가 바껴도) 예외 발생 없이 순회하는 fail-safe 라고한다. 그치만 이것의 단점은 '일관성' 보장이 안 된다.

또한 key-value 모두 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;
    }

 

3. Iterator

Hashtable은 Enumeration을 통해 순회했다.

얘는 hasMoreElements, nextElement만 갖고 있어서 순회만 가능했다.

하지만 내부를 까보면 java 9 이후 아래와 같은 asIterator 메서드를 통해 Hashtable도 Iterator를 통해 순회할 수 있게됐다. 참고로 Iterator에는 순회뿐만 아니라 remove도 가능하다.

default Iterator<E> asIterator() {
    return new Iterator<>() {
        @Override public boolean hasNext() {
            return hasMoreElements();
        }
        @Override public E next() {
            return nextElement();
        }
    };
}

 

 

이정도면 충분할 것 같다. 아참 그리고 Hashtable은 버킷 충돌 많아도 HashMap처럼 tree 변환 없이 LinkedList를 통해 엔트리를 쭉 연결한다.