10. HashMap과 TreeMap? HashMap과 Hashtable?

HashMap과 TreeMap

Map이란 key-value 형식을 기반으로 데이터를 저장할 수 있는 자료구조이다. 이때, Key는 데이터에 유일성을 가지고 있어야 한다. 필자 개인적으로 지금까지 Map 객체를 사용할 때 구현체로 HashMap을 주로 사용했는데 이 기회에 어떤 구현체가 있고 어떤 차이가 있는지 알아보자.

public interface Map<K,V> {
    int size();
    boolean isEmpty();
    boolean containsKey(Object key);
    boolean containsValue(Object value);

    V get(Object key);
    V put(K key, V value);
    V remove(Object key);
    void putAll(Map<? extends K, ? extends V> m);
}

HashMap

HashMap은 내부적으로 Entry Array로 구성되어 있다. Array의 인덱스를 hash함수에 넣고 나온 해시값을 계산한다.

 

그럼 위 그림처럼 내부적으로 Hash 값에 의해 어떤 Bucket에 담길지 결정이 된다. 만약 Hash가 같다면 같은 Bucket에 List로 연결될 것이다(LinkedList처럼 Entry안에 next Entry를 저장하는 변수가 있다). Hash 값을 이용하여 저장하기 때문에 순서를 보장하지 않는다는 특징이 있고 Hash값으로 해당 Array에 바로 접근하기 때문에 조회에 대해서 성능은 O(1)을 보장한다.

TreeMap

TreeMap은 HashMap과 다르게 Entry가 Tree 구조로 저장되어 있다.

Tree 구조 상 특정 Node를 조회하기 위해선 O(log n) 성능을 보인다. TreeMap은 SortedMap 인터페이스를 구현하고 있기 때문에 Key값을 기준으로 정렬되어 있는데, 이는 Comparator를 구현하여 정렬 순서를 변경할 수도 있다.

두 객체의 차이점

HashMap	TreeMap
조회성능 O(1)	조회성능 O(log n)
어떠한 순서도 보장하지 않음	순서를 보장하지만 정렬된 순서이다.
null 키와 null value저장이 가능하다	null value는 저장할 수 있지만 null 키는 저장할 수 없다.
비교를 위해 equals() 메소드를 사용한다.	순서를 유지하기 위해 compareTo() 메소드를 사용한다.
Map 인터페이스를 구현하고 있다.	NavigableMap 인터페이스를 구현하고 있다.

HashMap과 Hashtable

Hashtable은 Collection framework가 만들어지기 이전부터 존재하던 클래스이다. 따라서 Collection framework의 명명법(모든 Collection 클래스는 구현한 인터페이스 명이 포함되어야 한다)을 따르지 않고 있다. ← 동일한 이유로 명명법을 따르지 않는 클래스로 Vector, Stack, Properties 등이 있다. 이런 클래스는 상호 호환을 위해 설계를 변경하여 남겨두었지만 성능, 안정성 상의 이유로 사용을 권장하지 않는다.

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

    private float loadFactor;

    public Hashtable(int initialCapacity, float loadFactor) {

    }

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

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

HashMap과 Hashtable은 일반적으로 HahsMap과 사용법이 거의 동일하다. 기본 생성자로 생성할 시에 초기용량(버킷 수)은 11, 로드팩터는 0.75로 설정된다. 이는 수치는 생성자를 통해 객체를 생성할 때 수정이 가능하다.

두 객체의 차이점

1. Thread-safe 여부
   • Hashtable은 Thread-safe하고, HashMap은 Thread-safe 하지 않다는 특징을 가지고 있다. 따라서 멀티스레드 환경이 아니라면 HashTable은 HashMap보다 성능이 떨어진다는 단점을 가지고 있다.
2. Null값을 허용하는가?
   • HashTable은 key에 Null을 허용하지 않지만, HashMap은 key에 Null을 허용한다.
3. Enumeration 여부?
   • HashTable은 not fail-fast Enumeration을 제공하지만, HashMap은 Enumeration을 제공하지 않는다. (Enumeration = 순환 인터페이스 다만 Iterator는 thread-safe 하지 않고 Enumeration은 thread safe 함. 따라서 1번 차이점과 유사한 성질이다.)
4. HashMap은 보조해시를 사용하기 때문에 보조 해시 함수를 사용하지 않는 Hashtable에 비하여 해시 충돌 발생 가능성이 줄어든다.
5. Hashtable의 구조 개선은 이루어지지 않고 있지만, HashMap은 지속적으로 개선되고 잇다.

+ 조금 여담인데 Enumeration이나 Interator와 같은 순환 인터페이스를 사용하는 것은 Collection Class에서 제공하는 size를 통해 반복문으로 데이터에 접근하는 것보다 느리다. 인터페이스 구조상 List 데이터를 받아 새로운 구조로 다시 만들기 때문이다. 그럼에도 불구하고 순환 인터페이스를 사용하는 이유는 유지보수의 유연성 때문이다. 기존 컬렉션 클래스를 다른 컬렉션 클래스로 변경하는 경우 지원하는 메서드가 다르면 수정하는 부분이 많아질 수 있다. 하지만 순환 인터페이스를 사용한다면 이 부분의 구현부는 굳이 수정할 이유가 없게 된다.