[Java] HashTable이 뭘까?

1. Hashtable 클래스를 왜 살펴보는데?

---

우리가 개발을 하다 보면 Map, Set을 자주 사용하게 된다. 근데 생각해 보면 그냥 Map, Set을 쓰기보단 HashMap, HashSet을 주로 사용한다. 그래서 나는 왜 그런지 궁금해서 자세히 알아보려고 java.util 패키지에 들어가 봤는데 내 눈에는 목적과는 다르게 다른 녀석이 눈에 띄었다. 바로 Hashtable이라는 클래스다.

 

이걸 보자마자 궁금증이 들었다. Hashtable은 대체 뭘 하는 녀석인가? 사실 이 녀석은 "면접 질문"으로 자주 나온다는 것을 들어서 유명하다는 것은 알고 있었지만 솔직히 그래서 이걸로 뭘 하는지를 모르겠고 사용해 본 적도 없었다.

 

그래서인지 나는 이 클래스를 조금이라도 이해하고 싶어졌다. 그래서 내부가 어떻게 생겼는지를 살펴봤다.

 

 

1. Hashtable이란?

• Hashtable은 Java에서 제공하는 해시 테이블 기반의 동기화된 데이터 구조다. Hashtable은 키-값 쌍(key-value pairs)을 저장하고, 각 키는 고유해야 하며, 키와 값 모두 null을 허용하지 않는다.

 

 

2. 주요 특징

• 동기화(Synchronized): Hashtable의 모든 메서드는 synchronized 키워드를 사용하여 동기화된다. 따라서 여러 스레드가 동시에 Hashtable에 접근하더라도 일관성이 보장된다. (아래 목차에서 메서드를 살펴보면 이해할 수 있다.)
  
  
• 동시성(Concurrency): Hashtable은 여러 스레드에서 동시에 읽기 및 쓰기를 안전하게 수행할 수 있다. 하지만, 모든 메서드가 동기화되어 있기 때문에 많은 스레드가 동시에 Hashtable을 사용하면 성능 저하가 발생할 수 있다.
  
  
• 빠른 검색: 해시 테이블을 사용하여 데이터를 저장하므로, 일반적으로 O(1)의 시간 복잡도로 데이터를 검색할 수 있다.

 

 

3. Hashtable의 용도와 현대 Java에서의 위치 (나는 왜 써본 적이 없을까?)

• 역사적 배경: Hashtable은 Java의 초기 버전부터 존재하던 클래스다. Hashtable은 Vector와 함께 Java 1.0 때부터 제공되었으며, 동기화된 데이터 구조를 제공하기 위해 만들어졌다. 당시에는 동기화된 컬렉션이 필요할 때 Hashtable이 표준으로 사용되었다고 한다.

 

 

4. 잘 사용되지 않는 이유

• 성능 문제: 앞서 설명한 것처럼, 모든 메서드가 synchronized로 동기화되어 있는 Hashtable은 동시성 제어를 위해 단일 락을 사용하므로, 성능이 저하될 수 있다. 높은 동시성이 요구되는 환경에서는 ConcurrentHashMap이 훨씬 더 나은 성능을 제공하기 때문에, Hashtable이 자주 사용되지 않는다. (사실 쓰는 걸 못 봤다.)
  
  
• 유연성 부족: Hashtable은 null 키와 값을 허용하지 않는다. 반면 HashMap은 null 키와 값을 허용하며, 일반적인 사용에서 더 유연하다.
  
  
• Java Collections Framework의 발전: Java 2가 도입되면서 Collections Framework가 추가되었고, HashMap, TreeMap, ConcurrentHashMap과 같은 더 나은 성능과 유연성을 제공하는 컬렉션 클래스들이 등장했다. 이로 인해 Hashtable의 사용은 점차 줄어들었다고 한다.
  
  
• 더 나은 대체재 존재: HashMap과 ConcurrentHashMap은 Hashtable의 기능을 대체할 수 있는 더 나은 선택지다. 따라서, 새로운 프로젝트나 코드에서는 거의 사용되지 않는다.
  
  

 

5. 그래서 결론이 뭔데?

• Hashtable은 동기화된 해시 테이블로 설계되어 멀티스레드 환경에서 안전하게 사용할 수 있지만, 모든 메서드가 동기화되어 있어 성능 저하의 문제가 있다. 그래서 현대 Java 개발에서는 Hashtable보다 HashMap과 ConcurrentHashMap이 더 선호된다.
  
  
• HashMap은 동기화가 필요하지 않은 경우 Hashtable보다 더 빠른 성능을 제공하며, ConcurrentHashMap은 멀티스레드 환경에서 Hashtable보다 훨씬 나은 성능과 동시성을 제공한다. 따라서, 새로운 프로젝트에서는 거의 사용되지 않으며, 주로 레거시 코드나 면접 질문에서만 등장한다. (이래서 볼 일이 없었구나..?)

 

ConcurrentHashMap이 뭔지 궁금하다면?

[Java] ConcurrentHashMap의 동작원리 (CAS 기법)

 

 

2. Hashtable의 필드부터 살펴보자

---

1. java.util 패키지의 Hashtable

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

    private transient Entry<?,?>[] table;

    private transient int count;

    private int threshold;

    private float loadFactor;

    private transient int modCount = 0;

    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    @java.io.Serial
    private static final long serialVersionUID = 1421746759512286392L;
    
    
    // 수많은 메서드가 존재한다.
    
}

transient Entry<?,?>[] table

• 이 필드는 해시 테이블 자체를 나타내는 배열이다. 각 배열의 요소는 key-value 쌍을 담고 있는 Entry 객체다. 여기서 사용되는 transient 키워드는 이 필드가 직렬화(Serialization) 과정에서 제외된다는 것을 의미한다.

 

transient int count

• 이 필드는 해시 테이블에 저장된 총 엔트리(키-값 쌍)의 개수를 나타낸다. 현재 테이블에 얼마나 많은 요소들이 있는지를 나타낸다. transient 키워드가 있으므로, 이 필드 또한 직렬화 시 제외된다.

 

int threshold

• 해시 테이블이 리해시(rehash)되기 전까지 저장할 수 있는 최대 엔트리 수를 나타낸다. 이 값은 (용량 * loadFactor)로 계산되며, 테이블의 성능을 최적화하는 데 사용된다. 해시 테이블이 이 임계값을 초과하면 테이블 크기가 증가한다.

 

float loadFactor

• 로드 팩터(load factor)는 해시 테이블이 얼마나 차 있는지를 나타내는 값이다. 로드 팩터가 낮을수록 해시 테이블이 더 자주 리해시(rehash)되어 충돌이 줄어들지만 메모리 사용량이 증가한다고 한다. 반대로 로드 팩터가 높으면 메모리를 더 효율적으로 사용하지만 충돌 가능성이 증가할 수 있다.
  
  
• 예를 들어, 로드 팩터가 0.75이면, 해시 테이블의 크기가 75%까지 차면 테이블의 크기를 두 배로 늘려서 더 많은 항목을 저장할 수 있게 하는 것이다.

 

transient int modCount

• modCount 필드는 Hashtable이 구조적으로 수정된 횟수를 추적하는 데 사용된다. 구조적 수정이란 Hashtable의 엔트리 수를 변경하거나 테이블의 내부 구조를 수정하는 작업을 의미한다. 이 필드는 Hashtable의 Collection-뷰에서 반복자(iterator)를 사용할 때 데이터의 일관성을 유지하기 위해 '빠르게 실패(fail-fast)'하도록 설계되었다.
  
  
• 즉, 반복자(iterator)가 순회하는 동안 Hashtable이 수정되면 ConcurrentModificationException 예외를 발생시켜 프로그램의 오류를 방지한다. 이 필드도 transient이므로 직렬화 시 제외된다.

 

|참고사항| Collection-뷰란?

• keySet(), values(), entrySet()을 의미한다. Hashtable의 데이터를 key, value, 또는 key-value 쌍의 형태로 보여주는 집합적인 형태라고 보면 된다. (collection 뷰로 만들어서 iterator를 사용한다고 생각하면 된다.)

 

serialVersionUID

• 이 필드는 직렬화된 객체의 클래스 간 버전 호환성을 확인하기 위해 사용된다. Java에서 직렬화(serialization)는 객체의 상태를 바이트 스트림으로 변환하여 파일에 저장하거나 네트워크를 통해 전송하는 과정이다.
  
  
• serialVersionUID가 왜 필요할까? 그 이유는 직렬화된 객체를 다시 역직렬화(deserialization)할 때, 원래 객체와 같은 클래스가 사용되었는지 확인하기 위해 사용한다. 만약 클래스의 serialVersionUID가 다르면 InvalidClassException 예외가 발생하게 된다. 이렇게 함으로써 직렬화된 데이터가 원래의 클래스 구조와 호환되지 않는 경우 발생할 수 있는 오류를 방지하는 것이다.

 

 

3. Hashtable이 가진 생성자를 살펴보자

---

1. Hashtable의 첫 번째 생성자 (제일 중요)

public Hashtable(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: " + loadFactor);

    if (initialCapacity == 0)
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    table = new Entry<?,?>[initialCapacity];
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

매개변수 (initialCapacity, loadFactor)

• 첫 번째 매개변수인 initialCapacity는 해시 테이블의 초기 용량을 지정한다. 이 용량은 해시 테이블이 생성될 때 내부 배열의 크기를 결정한다.
  
  
• 두 번째 매개변수인 loadFactor는 해시 테이블이 얼마나 차 있어도 되는지를 나타내는 로드 팩터 값이다. 이 값은 해시 테이블이 얼마나 많은 데이터를 저장할 수 있는지를 결정하는 비율이라고 보면 된다.

 

로직의 흐름

1. initialCapacity(해시 테이블의 초기 용량)가 0보다 작으면 IllegalArgumentException 예외를 던진다.
2. loadFactor(해시 테이블이 얼마나 찰지)가 0보다 작거나 NaN(Not a Number)이면 IllegalArgumentException 예외를 던진다.
3. initialCapacity가 0이면, 이를 1로 설정한다(내부적으로 0 크기의 배열은 무의미하기 때문이다).
4. 매개변수 loadFactor를 인스턴스의 필드로 저장하고, initialCapacity 크기의 Entry 배열을 생성하여 table 필드에 할당한다.
5. threshold는 (초기 용량 * 로드 팩터) 값과 최대 배열 크기(MAX_ARRAY_SIZE) 중 작은 값으로 설정된다. 이를 통해 테이블의 크기를 조정하는 임계값을 결정한다.

 

2. Hashtable의 두 번째 생성자

public Hashtable(int initialCapacity) {
    this(initialCapacity, 0.75f);
}

매개변수 (initialCapacity)

• 해시 테이블의 초기 용량을 매개변수로 받는다.

 

로직의 흐름

• 로드 팩터가 기본값인 0.75로 설정된 상태에서 지정된 초기 용량으로 해시 테이블을 초기화한다. 이는 다른 생성자를 호출하여 기본 로드 팩터로 생성하는 것을 의미한다. (이 값을 가지고 위에 정의된 첫 번째 생성자를 호출한다.)

 

3. Hashtable의 세 번째 생성자

public Hashtable() {
    this(11, 0.75f);
}

매개변수

• 없다.

 

로직의 흐름

• 기본 용량(11)과 기본 로드 팩터(0.75)를 사용하여 새로운 해시 테이블을 생성한다. 이는 일반적인 기본 설정을 사용하여 해시 테이블을 초기화한다. (이것도 첫 번째 생성자를 호출한다.)

 

4. Hashtable의 네 번째 생성자

public Hashtable(Map<? extends K, ? extends V> t) {
    this(Math.max(2*t.size(), 11), 0.75f);
    putAll(t);
}

매개변수 (Map<? extends K, ? extends V> t)

• t: 해시 테이블에 복사할 맵(Map) 객체다.
  
  

로직의 흐름

• 매개변수로 전달된 맵 t의 모든 key-value 쌍을 새로운 해시 테이블에 복사하여 초기화한다.
• 초기 용량은 맵 t의 크기의 두 배와 11 중 더 큰 값으로 설정하고, 로드 팩터는 기본값 0.75로 설정한다. (이것도 첫 번째 생성자를 호출한다.)
• 그런 다음 putAll(t) 메서드를 사용하여 t의 모든 항목을 새로 생성된 해시 테이블에 추가한다. (아직 소개되지 않은 메서드)

 

5. Hashtable의 네 번째 생성자

Hashtable(Void dummy) {}

매개변수

• dummy: 실제로 사용되지 않는 더미 매개변수다.
  
  

로직의 흐름

• 이 생성자는 내부적으로 특별한 용도로 사용되며 Hashtable의 필드를 초기화하지 않는다. 이것은 주로 Properties 클래스에서 사용된다. Properties 클래스는 Hashtable을 상속하지만, 그 사용에서 Hashtable의 필드를 사용하지 않기 때문에 이와 같은 생성자를 제공하여 기본적인 Hashtable의 초기화 과정을 생략한다고 보면 된다.

 

 

4. Hashtable이 가진 메서드를 살펴보자

---

메서드를 살펴보면서 가능한 모든 메서드를 정리하려고 했는데 너무 많았다. 그래서 정말 필요해 보이는 메서드만 9개 정도 뽑아서 정리해 봤다.

지금부터 살펴볼 메서드들의 중요한 점이 있다. 바로 메서드 앞쪽을 보면 대부분 synchronized를 가지고 있다는 것이다. 즉, 거의 모든 메서드가 동기화를 하고 있다는 것이다.

 

1. put(K key, V value)

public synchronized V put(K key, V value) {
    if (value == null) {
        throw new NullPointerException();
    }

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

• put 메서드는 해시 테이블에 새로운 key-value 쌍을 추가한다. 만약 키가 이미 존재한다면, 해당 키에 대한 값을 새 값으로 바꾸고 이전 값을 반환한다.
• key 또는 value가 null이면 NullPointerException을 던진다.
• 이 메서드는 동기화(synchronized)되어 있기 때문에 멀티스레드 환경에서도 안전하게 사용할 수 있다.
  
  

2. get(Object key)

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

• get 메서드는 주어진 키에 대응하는 값을 반환한다. 만약 해당 키가 없으면 null을 반환한다.
• 이 메서드는 해시 테이블에서 특정 키에 대한 값을 검색하는 가장 기본적인 방법이다.
  
  

3. remove(Object key)

public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>)tab[index];
    for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            if (prev != null) {
                prev.next = e.next;
            } else {
                tab[index] = e.next;
            }
            modCount++;
            count--;
            V oldValue = e.value;
            e.value = null;
            return oldValue;
        }
    }
    return null;
}

• remove 메서드는 지정된 키에 대한 key-value 쌍을 해시 테이블에서 제거한다. 제거된 키에 대한 값을 반환하며, 해당 키가 없으면 null을 반환한다.
• 이 메서드는 동기화(synchronized)되어 있으며, 멀티스레드 환경에서도 안전하다.
  
  

4. rehash()

protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            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;
        }
    }
}

• rehash 메서드는 해시 테이블의 크기를 늘리고 내부 데이터를 재구성한다. 이는 해시 테이블의 용량이 임계값을 초과할 때 자동으로 호출된다.
• rehash를 통해 테이블의 크기를 늘리면서 충돌을 줄이고, 검색 성능을 향상시킬 수 있다.
  
  

5. containsKey(Object key)

public synchronized boolean containsKey(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 true;
        }
    }
    return false;
}

• containsKey 메서드는 특정 키가 해시 테이블에 존재하는지를 검사한다.
• 만약 키가 존재하면 true를 반환하고, 없으면 false를 반환한다.
  
  

6. size()

public synchronized int size() {
    return count;
}

• size 메서드는 해시 테이블에 저장된 key-value 쌍의 총개수를 반환한다.
• 이 메서드는 동기화(synchronized)되어 있으므로 멀티스레드 환경에서도 안전하게 사용할 수 있다.
  
  

7. clear()

public synchronized void clear() {
    Entry<?,?> tab[] = table;
    for (int index = tab.length; --index >= 0; )
        tab[index] = null;
    modCount++;
    count = 0;
}

• clear 메서드는 해시 테이블의 모든 항목을 제거하고 초기화한다. 테이블은 비워지지만, 크기는 변경되지 않는다.
• 동기화(synchronized)된 메서드로, 멀티스레드 환경에서 안전하게 호출할 수 있다.
  
  

8. clone()

public synchronized Object clone() {
    Hashtable<?,?> t = cloneHashtable();
    t.table = new Entry<?,?>[table.length];
    for (int i = table.length ; i-- > 0 ; ) {
        t.table[i] = (table[i] != null)
            ? (Entry<?,?>) table[i].clone() : null;
    }
    t.keySet = null;
    t.entrySet = null;
    t.values = null;
    t.modCount = 0;
    return t;
}

• clone 메서드는 해시 테이블의 얕은 복사본을 반환한다. 테이블 자체의 구조는 복사되지만, 각 키와 값은 동일한 객체를 참조한다.
• 이 메서드는 Hashtable의 Cloneable 인터페이스 구현을 위한 것이다.
  
  

9. toString()

public synchronized String toString() {
    int max = size() - 1;
    if (max == -1)
        return "{}";

    StringBuilder sb = new StringBuilder();
    Iterator<Map.Entry<K,V>> it = entrySet().iterator();

    sb.append('{');
    for (int i = 0; ; i++) {
        Map.Entry<K,V> e = it.next();
        K key = e.getKey();
        V value = e.getValue();
        sb.append(key   == this ? "(this Map)" : key.toString());
        sb.append('=');
        sb.append(value == this ? "(this Map)" : value.toString());

        if (i == max)
            return sb.append('}').toString();
        sb.append(", ");
    }
}

• toString 메서드는 해시 테이블의 내용을 문자열로 반환한다.
• 테이블의 각 항목이 key=value 형식으로 출력된다.

 

최근에는 이렇게 자바의 기본적인 코드들을 직접 분석해보고 있다. 다음에는 ConcurrentHashMap, HashMap을 사용하는 게 Hashtable에 비해 어느 정도의 성능 차이를 가져다주는지 알아보고 정리할 예정이다.